Beyond the Array to the Linked List

I l @ ve RuBoard

Ideally, you'd like to be able to add data indefinitely (or until the program runs out of memory) without specifying in advance how many entries you'll make and without committing the program to allocating huge chunks of memory unnecessarily. You can do this by calling malloc() after each entry and allocating just enough space to hold the new entry. If the user enters three films , the program calls malloc() three times. If the user enters 300 films, the program calls malloc() 300 times.

This fine idea raises a new problem. To see what it is, compare calling malloc() once, asking for enough space for 300 film structures, and calling malloc() 300 times, each time asking for enough space for one film structure. The first case allocates the memory as one contiguous memory block and all you need to keep track of the contents is a single pointer-to- struct film variable that points to the first structure in the block. Simple array notation lets the pointer access each structure in the block, as shown in the preceding code segment. The problem with the second approach is that there is no guarantee that consecutive calls to malloc() yield adjacent blocks of memory. This means the structures won't necessarily be stored contiguously (see Figure 17.1). Therefore, instead of storing one pointer to a block of 300 structures, you need to store 300 pointers, one for each independently allocated structure!

Figure 17.1. Allocating structures in a block versus allocating them individually.

One solution, which we won't use, is to create a large array of pointers and assign values to the pointers one by one as new structures are allocated:

 #define TSIZE  45         /* size of array to hold titles    */ #define FMAX   500        /* maximum number of film titles   */ struct film {    char title[TSIZE];    int rating; }; ... struct film * movies[FMAX];   /* array of pointers to structures */ int i; ... movies[i] = (struct film *) malloc (sizeof (struct film));

This approach saves a lot of memory if you don't use the full allotment of pointers, because an array of 500 pointers takes much less memory than an array of 500 structures. It still wastes the space occupied by unused pointers, however, and it still imposes a 500-structure limit.

There's a better way. Each time you use malloc() to allocate space for a new structure, you can also allocate space for a new pointer. "But," you say, "then I need another pointer to keep track of the newly allocated pointer, and that needs a pointer to keep track of it, and so on." The trick to avoiding this potential problem is to redefine the structure so that each structure includes a pointer to the next structure. Then, each time you create a new structure, you can store its address in the preceding structure. In short, you need to redefine the film structure this way:

 #define TSIZE  45      /* size of array to hold titles  */ struct film {    char title[TSIZE];    int rating;    struct film * next; };

True, a structure can't contain in itself a structure of the same type, but it can contain a pointer to a structure of the same type. Such a definition is the basis for defining a linked list ”a list in which each item contains information describing where to find the next item.

Before looking at C code for a linked list, let's take a conceptual walk through such a list. Suppose a user enters Modern Times as a title and 10 as a rating. The program would allocate space for a film structure, copy the string Modern Times into the title member, and set the rating member to 10 . To indicate that no structure follows this one, the program would set the next member pointer to NULL . ( NULL , recall, is a symbolic constant defined in the stdio.h file and representing the null pointer.) Of course, you need to keep track of where the first structure is stored. You can do this by assigning its address to a separate pointer that we'll refer to as the head pointer . The head pointer points to the first item in a linked list of items. Figure 17.2 represents how this structure looks. (The empty space in the title member is suppressed to save space in the figure.)

Figure 17.2. First item in a linked list.

Now suppose the user enters a second movie and rating, for example, Titanic and 8 . The program allocates space for a second film structure, storing the address of the new structure in the next member of the first structure (overwriting the NULL previously stored there) so that the next pointer of one structure points to the following structure in the linked list. Then the program copies Titanic and 8 to the new structure and sets its next member to NULL , indicating that it is now the last structure in the list. Figure 17.3 shows this list of two items.

Figure 17.3. A badly unbalanced binary search tree.

Each new movie will be handled the same way. Its address will be stored in the preceding structure, the new information goes into the new structure, and its next member is set to NULL , setting up a linked list like that shown in Figure 17.4.

Figure 17.4. Linked list with several items.

Suppose you want to display the list. Each time you display an item, you can use the address stored in the corresponding structure to locate the next item to be displayed. For this scheme to work, however, you need a pointer to keep track of the very first item in the list because no structure in the list stores the address of the first item. Fortunately, you've already accomplished this with the head pointer.

Using a Linked List

Now that you have a picture of how a linked list works, let's implement it. Listing 17.2 modifies Listing 17.1 so that it uses a linked list instead of an array to hold the movie information.

Listing 17.2 The `films2.c` program.

 /* films2.c -- using a linked list of structures */ #include <stdio.h> #include <stdlib.h>      /* has the malloc prototype      */ #include <string.h>      /* has the strcpy prototype      */ #define TSIZE    45      /* size of array to hold title   */ struct film {    char title[TSIZE];    int rating;    struct film * next;   /* points to next struct in list */ }; int main(void) {    struct film * head = NULL;    struct film * prev, * current;    char input[TSIZE];    puts("Enter first movie title:");    while (gets(input) != NULL && input[0] != `  /* films2.c -- using a linked list of structures */ #include <stdio.h> #include <stdlib.h> /* has the malloc prototype */ #include <string.h> /* has the strcpy prototype */ #define TSIZE 45 /* size of array to hold title */ struct film { char title[TSIZE]; int rating; struct film * next; /* points to next struct in list */ }; int main(void) { struct film * head = NULL; struct film * prev, * current; char input[TSIZE]; puts("Enter first movie title:"); while (gets(input) != NULL && input[0] != `\0') { current = (struct film *) malloc(sizeof(struct film)); if (head == NULL) /* first structure */ head = current; else /* subsequent structures */ prev->next = current; current->next = NULL; strcpy(current->title, input); puts("Enter your rating <0-10>:"); scanf("%d", &current->rating); while( getchar () != `\n') continue; puts("Enter next movie title (empty line to stop):"); prev = current; } if (head == NULL) printf("No data entered. "); else printf ("Here is the movie list:\n"); current = head; while (current != NULL) { printf("Movie: %s Rating: %d\n", current->title, current->rating); current = current->next; } printf("Bye!\n"); return 0; } 
 ')    {       current = (struct film *) malloc(sizeof(struct film));       if (head == NULL)         /* first structure       */          head = current;       else                      /* subsequent structures */          prev->next = current;       current->next = NULL;       strcpy(current->title, input);       puts("Enter your rating <0-10>:");       scanf("%d", &current->rating);       while(getchar() != `\n')          continue;       puts("Enter next movie title (empty line to stop):");       prev = current;    }    if (head == NULL)       printf("No data entered. ");    else       printf ("Here is the movie list:\n");    current = head;    while (current != NULL)    {       printf("Movie: %s  Rating: %d\n", current->title, current->rating);       current = current->next;    }    printf("Bye!\n");    return 0; }

The program performs two tasks using the linked list. First, it constructs the list and fills it with the incoming data. Second, it displays the list. Displaying is the simpler task, so let's look at it first.

Displaying a List

The idea is to begin by setting a pointer (call it current ) to point to the first structure. Because the head pointer (call it head ) already points there, this code suffices:

 current = head;

Then you can use pointer notation to access the members of that structure:

 printf("Movie: %s Rating: %d\n", current->title, current->rating);

The next step is to reset the current pointer to point to the next structure in the list. That information is stored in the next member of the structure, so this code accomplishes the task:

 current = current->next;

After this is accomplished, repeat the whole process. When the last item in the list is displayed, current will be set to NULL , for that's the value of the next member of the final structure. You can use that fact to terminate the printing. Here's all the code films2.c uses to display the list:

 while (current != NULL) {    printf("Movie: %s  Rating: %d\n", current->title, current->rating);    current = current->next; }

Why not just use head instead of creating a new pointer current to march through the list? Because using head would change the value of head , and the program would no longer have a way to find the beginning of the list.

Creating the List

Creating the list involves three steps:

Use malloc() to allocate enough space for a structure.
Store the address of the structure.
Copy the correct information into the structure.

There's no point in creating a structure if none is needed, so the program uses temporary storage (the input array) to get the user's choice for a movie name . If the user simulates EOF from the keyboard or enters an empty line, the input loop quits:

 while (gets(input) != NULL && input[0] != `  while (gets(input) != NULL && input[0] != `\0') 
 ')

If there is input, the program requests space for a structure and assigns its address to the pointer variable current :

 current = (struct film *) malloc(sizeof(struct film));

The address of the very first structure should be stored in the pointer variable head . The address of each subsequent structure should be stored in the next member of the structure that precedes it. Therefore, the program needs a way to know whether it's dealing with the first structure or not. A simple way is to initialize the head pointer to NULL when the program starts. Then the program can use the value of head to decide what to do.

 if (head == NULL)    /* first structure    */    head = current; else                 /* subsequent structures */    prev->next = current;

In this code, prev is a pointer that points to the structure allocated the previous time.

Next, you have to set the structure members to the proper values. In particular, you should set the next member to NULL to indicate that the current structure is the last one in the list. You should copy the film title from the input array to the title member, and you should get a value for the rating member. The following code does these things:

 current->next = NULL; strcpy(current->title, input); puts("Enter your rating <0-10>:"); scanf("%d", &current->rating);

Finally, you should prepare the program for the next cycle of the input loop. In particular, you need to set prev to point to the current structure, for it will become the previous structure after the next movie name is entered and the next structure is allocated. The program sets this pointer at the end of the loop:

 prev = current;

Does it work? Here is a sample run:

 Enter first movie title:  The Full Monty  Enter your rating <0-10>:  7  Enter next movie title (empty line to stop):  The Duelists  Enter your rating <0-10>:  8  Enter next movie title (empty line to stop):  Devil Dog: The Hound of Hell  Enter your rating <0-10>:  1  Enter next movie title (empty line to stop): Here is the movie list: Movie: The Full Monty  Rating: 7 Movie: The Duelists  Rating: 8 Movie: Devil Dog: The Hound of Hell  Rating: 1 Bye!

Afterthoughts

The films2.c program is a bit skimpy. For example, it fails to check whether malloc() finds the requested memory, and it doesn't have any provisions for deleting items from the list. These failings can be fixed, however. For instance, you can add code that checks whether malloc() 's return value is NULL (the sign it failed to obtain the memory you wanted). If the program needs to delete entries, you can write some more code to do that. This approach to solving problems and adding features as the need arises isn't the best programming method. In particular, it tends to intermingle coding details and the conceptual model. For instance, in the sample program, the conceptual model is that you add items to a list. The program obscures that interface by pushing details such as malloc() and the current->next pointer into the foreground. It would be nice if you could write a program in a way that made it obvious you're adding something to a list and in which bookkeeping details, such as calling memory-management functions and setting pointers, were hidden. By making a fresh start, you can meet these goals. Let's see how.

I l @ ve RuBoard

Beyond the Array to the Linked List