Generic Lists in C

Due: March 16, 2012

Write and test a set of generic linked list functions in C. These functions should be in a file of their own with no main() function. The functions required are:

initialize

initialize an empty list

inhead

insert a node at the beginning of a list

intail

insert a node at the end of a list

delhead

delete a node at the beginning of a list returning a pointer to that node

deltail

delete a node at the end of a list returning a pointer to that node

delnode

given a pointer to a node, find it in an unordered list and delete it

insorder

insert a node into a sorted list (descending order) using a user supplied function for comparison

delorder

given a pointer to a node, find it in an ordered list using a user supplied function for comparison, and deleted. Note that this can be trivially done using delnode and ignoring the user supplied function, but that is not what I want you to do.

walk

traverse a list, passing a pointer to each node to a user supplied function

I will give you some specific tips here and perhaps more in class. Feel free to follow my suggestions, or do it your own way.

First I would define a structure to manage linking so that the user isn't required to worry about embedding pointers in their data representation.

struct listnode {
   void *datum;
   struct listnode *next;
}

For each item the user inserts into a list, we'll allocate one of these structures, use the datum field to point to the user data, and use the next field to point to the next item in the linked list.

Next, I would define a list structure to hold the head and tail pointer for our list.

struct list {
   struct listnode *head;
   struct listnode *tail;
}

With these definitions, we can now write our initialize function:

void initialize(struct list * ourlist) {
   ourlist->head = NULL;
   ourlist->tail = NULL;
}

And here is an implementation of inhead:

void inhead(struct list * ourlist, void * ourdata) {
   struct listnode *newnode;

   newnode = new(sizeof(struct listnode));
   newnode->data = ourdata;

   if (ourlist->head == NULL) { /* list is empty */ 
      ourlist->head = newnode;
      ourlist->tail = newnode;
      newnode->next = NULL;
   } else { /* list is not empty */
      newnode->next = list->head;
      ourlist->head = newnode;
   }
}

Be sure to deallocate everything you have allocated, for example, here is delhead:

void delhead(struct list * ourlist) {
   struct listnode *temp;

   if (ourlist->head == NULL) /* list is empty, do nothing */
      return;
   
   temp = ourlist->head;
   ourlist->head = temp->next;
   delete(temp);
   if (ourlist->head == NULL) /* deleted last element, list now empty */
      ourlist->tail = NULL;
}

You will be shown in class how to use function pointers for the sorted list routines and the walk routine.

I know that most of you have never programmed in C, so I am perfectly willing (and hopefully able) to offer assistance when you need it.