Saturday, November 13, 2010

Memory Allocation and Linked Lists

Memory Allocation

Memory allocation allows the programmer to allocate a block of memory of a desired size, and then store data into the block, along with initializing a pointer pointing to this block of memory. In order to do so, I'll explain the use of malloc(), realloc()free(), and calloc().

malloc() will allocate a block of memory, although it will not initialize it, and returns a pointer to the block of memory allocated. The prototype of malloc() looks like: void malloc(size_t size);size_t is an integer type defined in the C library, which is an unsigned integer. So, size is just an integer and represents the amount of bytes to be allocated. Since malloc() will return a pointer to a block of allocated memory, you need a pointer in order to make use of a call to malloc(), like so:

//Memory allocation for a character array of n number of elements

char *p;
p = malloc(n + 1);

//you could also do:

p = (char *) malloc(n + 1);

Since a character in C is one byte the, numerical argument for malloc() ends up just being a simple integer. However, if you were allocating memory for any other type of data you would need to use the sizeof() function to determine how much memory to allocate.

int *p;
p = malloc(sizeof(int));

//you could also do:

p = (char *) malloc(sizeof(int));

Just as a reminder, if you ever need to figure out how many elements an array has, use the following idiom: num_Elements = (sizeof(array) / sizeof(array[0])). That will take the size of all the elements divided by the size of a single element, giving you an integer resultant.

realloc() will change the size of a previously allocated block of memory. The prototype for realloc() is: void *realloc(void *ptr, size_t size);ptr must point to a block of memory that was previously used in a call to malloc() or realloc(). The size parameter can be either larger or smaller than the original block.

calloc() is similar to malloc() in all ways except in that it initializes the bytes to 0 within the block.

free() is very easy to use; simply pass a pointer that points to a memory block we no longer need, and it will be available for reuse later on.

Linked Lists

A linked list is a chain of structures (called nodes), where each node contains a pointer to the next node in the chain. The last node in the list would contain a null pointer. The advantages of using a linked list over an array, is that you can add in nodes anywhere in the list you want, and you can delete nodes anywhere you want. You can also create many types of data structures like graphs and trees using linked lists.

Here are the barebones of a basic node:

struct node {
  //... here would be the node's data
  struct node *next;

To access a member of a structure through a pointer to a structure there is a "shortcut" operator called the right arrow selection operator ->. The right arrow selection operator allows you to access the member of a value pointed by a pointer. The following are equal:

(*node).data = 10;

//this is the same as:

node->data = 10;

In order to add a node to the beginning of the linked list, all you need to do is create a temporary variable to hold your new node, assign the value of your new node to the variable, and modify your new node to point to the old first node. Since adding a new node to the beginning of a list is such a common task, I'll show a sample function on how to do so. In order for a function to directly add a new node to a list, you need to be able to pass a pointer to the function and make it point elsewhere. Since arguments are passed by value, you can't simply pass a pointer to a function, since the function will then only be able to modify a copy of the pointer passed to it. Instead, you would need to pass a pointer to a pointer, then, you can make the pointer point elsewhere.

void add(struct node **list, int n)
  struct node *new_node;

  new_node = malloc(sizeof(struct node));
  if (new_node == NULL) //the macro NULL is defined in stdlib.h
    printf("Error: Malloc failed to allocate necessary space.");
  new_node->value = n;
  new_node->mext = *list;
  *list = new_node; //modifies the value pointed by list, which is a pointer

In the above example, list is a pointer to the first node in a linked list. Since we pass a pointer to a pointer (when we call this function we would use &first in the first argument, being the address of the first node), we are able to update the list pointer to point to our newly added node.

In order to search through a list, from beginning to end, you would usually use a for loop. The idiom is actually very simple. You scan the value and make your comparison on the first node, then make your iteration point to the next node:

for (p = first; p != NULL; p -> next)
  ... //whatever code you want to loop

Remember how I mentioned that the last node in the list contains a null pointer? The NULL macro defined in stdlib.h has the value of a NULL pointer, and as such the loop will stop on the last node of the list.

The idea behind deleting a node is to search for your desired deletion and make the previous node point to the node directly ahead of your node to be deleted. One method of doing so, is to keep a "trailing pointer". You scan through each node and keep a pointer to the node previously scanned, so that you can delete the current node and make the previous node point the next one in the list. Here is a sample function that searches for a node with a value inside of it (this value could be the node's ID, or whatever you are searching for) and deletes the node using free().

struct node *delete(struct node *list, val)
  struct node *current, *previous;

  for (current = list, previous = NULL;
       current != NULL && current -> data_Member != val;
       previous = current, current = current -> next)

  if (current == NULL)  //val was not found, end of list reached
    return list
  if (previous == NULL) //val was in the first node
    list = list -> next;
  else                  //val was found within a node
    prev -> next;
  return list;

The for loop in this function actually just has a null statement, because all the actions are done in the iteration portion of the for loop; the previous node is set to the currently being scanned, and the currently being scanned is set to the next node. The for loop stops once the value you are searching for is found, or if the end of the list is found. The two if and the else statements catch all the possible outcomes of the for loop. If the first node in the list is going to be deleted (if previous equals NULL), you need to make your list pointer point to the second node.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.