A List is a List

Not only can we have recursion in the code, we can have recursion in the data as well. Recursion in the data usually means that we have structures that point to the same type of structure. For example, let's look at how we might implement a list according to the definition we saw in Part 8-1.
  1. A list may be empty.
  2. A list may be an item followed by a list.
With the strings we implemented the empty string with a pointer to the null byte. Here we will represent the empty list with the null pointer. For example we could initialize a list to be: 

head = NULL ;

We often refer to the beginning of a list as the head of the list. Similarly, we often refer to the end of the list as the tail. The value NULL is defined in stdio.h and is guaranteed to be different from any valid pointer. This way, we can be assured that whenever we are testing a pointer to see if it's equal to NULL, we won't mistakenly think a real pointer is NULL.

Designating the pointer identifying our list as the head implies that we will represent non-empty lists by a pointer to their first element. This is true. It also establishes how we will represent the rest of the list that follows the first element. We will have a pointer to its first element as well. So along with each element we will have a pointer to the next element. We can put that into a structure as follows: 

struct list_element {
   int data ;
   struct list_element *next ;
} ;

Notice here that we have a structure that contains a pointer to the same type of structure. This is a recursive data structure.

So let's say we want to add a new element to the head of the list. The basic strategy is to create the new list element, put the data into it, make its next pointer point to the old list and make our list head point to the new element. We can do this will the following code assuming that the data we want in the new first element is in the variable num: 

p = (struct list_element *)malloc( sizeof( struct list_element )) ;
p->data = num ;
p->next = head ;
head = p ;

Carefully study this code fragment. You may want to draw a picture to keep track of where the pointers are going. Does it work correctly when the list is initially empty? That is, if head is NULL do we get a list that has one element in it?

Moving through the list takes advantage of the generality of C's for statement. For example we could implement a function to print out the elements of a list as: 

void print_list( struct list_element *list )
{
   struct list_element *p ;

   for( p = list; p != NULL; p = p->next )
      printf( "%d\n", p->data ) ;
}

As before, it will be beneficial for you to trace through this code on an example list.

Just as we did with strings, we can use recursive definitions to write recursive code. For example, we could implement the print_list() function recursively as in: 

void print_list( struct list_element *list )
{
   if( list != NULL ) {
      printf( "%d\n", list->data ) ;
      print_list( list->next ) ;
   }
}

which really isn't all that much simpler than the iterative approach above. However, what if we wanted to print the list in reverse order? Recursively, we could do it like this: 

void rev_print_list( struct list_element *list )
{
   if( list != NULL ) {
      rev_print_list( list->next ) ;
      printf( "%d\n", list->data ) ;
   }
}

Try that iteratively using the data structure we've defined. Make sure you understand how these two recursive functions work. Why does the first one print the list in order and the second in reverse order?

We can also ask for the length of a list recursively. For example, we could do it much like we did for strings: 
int list_length( struct list_element *list )
{
   if( list == NULL )
      return( 0 ) ;
   else
      ...
}
What line should go in the ... ?