Programming in C

250 Chapter 11 Pointers

Before developing some functions to work with linked lists, two more issues must be

discussed. Usually associated with a linked list is at least one pointer to the list. Often, a

pointer to the start of the list is kept. So, for your original three-element list, which con-

sisted of n1,n2,and n3,you can define a variable called list_pointerand set it to point

to the beginning of the list with the statement

struct entry *list_pointer = &n1;

assuming that n1has been previously defined. A pointer to a list is useful for sequencing

through the entries in the list, as you see shortly.

The second issue to be discussed involves the idea of having some way to identify the

end of the list.This is needed so that a procedure that searches through the list, for

example, can tell when it has reached the final element in the list. By convention, a con-

stant value of 0 is used for such a purpose and is known as the nullpointer.You can use

the null pointer to mark the end of a list by storing this value in the pointer field of the

last entry of the list.^1

In your three-entry list, you can mark its end by storing the null pointer in n3.next:

n3.next = (struct entry *) 0;

You see in Chapter 13, “The Preprocessor,” how this assignment statement can be made

a bit more readable.

The type cast operator is used to cast the constant 0 to the appropriate type (“pointer

to struct entry”). It’s not required, but makes the statement more readable.

Figure 11.8 depicts the linked list from Program 11.6, with a struct entrypointer

called list_pointerpointing to the start of the list and the n3.nextfield set to the null

pointer.

Program 11.7 incorporates the concepts just described.The program uses a whileloop

to sequence through the list and display the valuemember of each entry in the list.

Program 11.7 Traversing a Linked List

// Program to traverse a linked list

#include <stdio.h>

int main (void)

{

struct entry

{

int value;

struct entry *next;

};

1. A null pointer is not necessarily internally represented as the value 0 .However, the compiler
   must recognize assignment of the constant 0 to a pointer as assigning the null pointer.This also
   applies to comparing a pointer against the constant 0:The compiler interprets it as a test to see if
   the pointer is null.