Lecture 13

Linked Lists

Rather than use a single contiguous block of memory for the list, use individual blocks for each item. Memory is allocated using malloc. In order to connect up the items into a list they must be linked. This is done using a pointer within each item that points to the next item. A NULL pointer ( contains 0 in C ) is used for the pointer from the last item.

To insert an item in the list change the pointer for the item before it and make its pointer point to the next item.

To remove an item change the pointer for the item before it to point to the next item.

Lets write a program in C to manipulate a list.

First some declarations: 

#include <stdio.h>
#define newptr(x,y) (x *)malloc((int)sizeof(x)*y)

typedef struct _list_item {
         char name[64];
         struct _list_item *next;
} list_item;

typedef list_item * list;
typedef list_item * item_ptr;
The 'newptr' macro is just an easy way of using malloc.

The structure will be used to hold a list item. In this case each item is a name containing up to 63 characters.

The typedefs will make the rest of the program easier to follow.

Now a function to add a name to the list so that the list stays in alphabetical order: 

list add_to_list(list l, char *name)  {
   item_ptr before;                       // the item before the one we are adding
   item_ptr new_item = newptr(list_item, 1); // allocate space for the new item

   strcpy(new_item->name,name);           // and copy the name to it.

   if(l==NULL || strcmp(name,l->name)<0) {// do we need to put it at
      new_item->next=l;                   // the start of the list?
      return new_item;                    // if so, it becomes the new head pointer.
   }
   before=l;
   while(before->next && strcmp(name,before->next->name)>0) 
      before=before->next;      // find the item before the one we are adding

   new_item->next=before->next; // change the pointers
   before->next=new_item;

   return l;      // head pointer does not change.
}
Memory for the new list item is allocated using malloc and the name is copied into the new structure. If the new item is to be put into the list at the start, this is done by setting its 'next' pointer to be the rest of the list and returning a pointer to it as the new start of the list. Otherwise it is necessary to find the items in the list before and after the one we are inserting and change the pointers as described earlier.

Now a function to delete a name from the list: 

list delete_from_list(list l, char *name)  {

   item_ptr delete;   // the item we will delete
   item_ptr before;     // the item before it

   if(!l) return NULL; // if the list is empty do nothing

   if(!strcmp(l->name, name)) { // if the item to delete is the first one
      delete=l;                 // change the head pointer to skip over it
      l=l->next;                
      free(delete);             // free its memory
      return l;                 // return the new head pointer
   }       

   before=l;
   while ( before->next && !strcmp(before->next->name, name))
      before =  before->next;   // find the item before the one we want to delete

   if(before->next)  {        // if it has been found
      delete=before->next;   
      before->next = delete -> next; // change pointers
      free(delete);        // free memory
   }
   return l;   // head pointer does not change
}
If the item to be deleted is at the top of the list then we delete it and return a pointer to the rest of the list.
If not, we locate the item before the one to be deleted, then the pointer from this is made to point to the item after the one to be deleted. In both cases, memory for the deleted item is freed.

Now to print the entire list: 

void print_list(list l)  {
   puts("The list is:");
   while(l)  {
      printf("%s\n",l->name);
      l=l->next;
   }
}
For each item in the list, the printf statement is used to print it. (note that while(l) will execute the loop until l is NULL)

Now a main function to test our list. 

void main() {
   list l=NULL;

   l=add_to_list(l,"Florence");
   l=add_to_list(l,"Dougal");
   l=add_to_list(l,"Dylan");
   l=add_to_list(l,"Zebedee");
   l=add_to_list(l,"Mr Rusty");
   l=add_to_list(l,"Mr McHenry");
   l=add_to_list(l,"Brian");

   print_list(l);

   l=delete_from_list(l,"Brian");
   l=delete_from_list(l,"Dylan");
   l=delete_from_list(l,"Zebedee");
   l=delete_from_list(l,"Dougal");
   l=delete_from_list(l,"Martin");

   print_list(l);
}
The complete program is:
 
When run, the program produces the following output: