head = NULL;
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; };
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 ;
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); }
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); } }
void rev_print_list(struct list_element *list) { if(list != NULL) { rev_print_list(list->next); printf("%d\n", list->data); } }