Introduction to Linked Lists

The problem with static arrays (like the array of structures in our previous example) is that they can have only a finite number of elements. This value is set during compilation, meaning that when you write the program, you must know and set the maximum number of elements to ever be stored. In Chapter 10, “Managing Memory,” you learned how to make a dynamically sized array using realloc(), which increased the amount of available memory as needed. Linked lists allow you to combine these two concepts, creating a growing list of structures.

A linked list takes structures one step further by making them self-referential. This is accomplished by defining a structure as containing both data (the actual information being stored) and a pointer to the next item in the list (Figure 13.10).

The basic definition of a linked list is

struct my_list {
   char data[100];
   struct my_list *next;
};

You can have as many members in the structure as you like, and of any type, as long as you include one pointer member. That pointer must be of the struct my_list type (the same type as the structure itself).

To begin a linked list, the first item in the list should be declared as a pointer and initialized to NULL (Figure 13.11):

struct my_list *item = NULL;

With only the one item in the list, this widget is both the start (sometimes called the head) and end (or tail) of the entire linked list. As the ending item, its value—or specifically its pointer's value—should be NULL (so you know no other items follow it).

The next step is to allocate the necessary memory to store all of the structure's data. The malloc() function will do this. That syntax is

item = (struct my_list *) malloc
 (sizeof(struct my_list));

That line of code says that the required number of bytes for the structure (sizeof(struct my_list)) needs to be allocated. This should be casted as a pointer of type struct my_list. For detailed explanation of this process you can review Chapter 10, but all that is really happening here is that memory is being allocated for a structure instead of any array, number, or character.

Now that there is room in memory for item, the data can then be assigned to this first member of the structure, using the special pointer->field syntax, introduced in the sidebar “Structures and Pointers”:

strncpy(item->data, "This is a record.",
 99);
item->next = NULL;

At this point, there is one structure in memory, containing some data and a NULL pointer (Figure 13.12).

To create another item, allocate the proper amount of memory:

struct my_list *new_item = NULL;
 new_item = (struct my_list *) malloc 
 (sizeof(my_list));

This next item can then be assigned a value (Figure 13.13):

strncpy(new_item->data, "This is another
 record.", 99);
new_item->next = NULL;

You could repeat this process, making as many new pointers as you want, for each added structure. But then you'll still be limited to the number of items set during compilation. To make this process limitless, you must be able to free up new_item so that it can be used again. To do that while still being able to find the new_item data, we need to store the address in memory where this information can be found. So, you assign new_item's memory address to item's pointer member.

This is done simply enough (Figure 13.14):

item->next = new_item;

Now you have a linked list. The new_item variable can be reused (to add another link) but you can still access every stored value as long as you retain the first item.

The concept behind linked lists can be confusing, so we'll paraphrase the idea. Simply put, a linked list stores blocks of information in memory. Each block holds both the data itself, and the address to where the next block is stored (this is the pointer). To access all of the stored data, all the C application needs to know is the address of the first block. There it can find the data and the address of the second block. At the second block it finds more data and the address to the third block. This continues until the address stored in a block is NULL, indicating there are no more records.

In this chapter's final example, we rewrite the grades application so that it can take any number of records. We include several illustrations here to help you visualize the process.

To use linked lists

1.	Create a new file or project in your text editor or IDE.
2.	Type the standard beginning lines of code (Script 13.4): /* grades_list.c - Script 13.4 - remake of grades.c (Script 13.3) */ #include <stdio.h>
3.	Include the string.h and stdlib.h library files: #include <string.h> #include <stdlib.h> In order to use the strncpy() function, we must include the string.h file. Since this application uses the malloc() function for dynamic memory allocation, the standard library is necessary as well.
4.	Define one macro constant: #define STR_LEN 20 The maximum string length is still necessary but the NUM_STUDENTS constant (used in the previous example) is unnecessary with this dynamically growing list.
5.	Begin the main function: int main (void) {
6.	Define the structure: struct student_grade { char first_name[STR_LEN]; char last_name[STR_LEN]; float grade; struct student_grade *next; }; The structure is the same as it was before except for the addition of the pointer. The pointer is of type struct student_grade, since it will point to another structure (and pointers must match the data type they point to). The pointer itself is called next, appropriately enough.
7.	Use typedef to rename the structure syntax: typedef struct student_grade sg; Again, the typedef simplifies the process of referring to a structure. This will be very useful in this example, where the text struct student_grade would be necessary in several places.
8.	Define three structure pointers: sg *first = NULL; sg *new = NULL; sg *temp = NULL; The one pointer will always point to the first item in the list. The second will be used to add other items. The third will be used during the process of freeing up all the used memory.
9.	Create the other variables: int num; float g; char classname[12], fn[STR_LEN], ln[STR_LEN]; All of these variables are the same as in the previous example. Two have been dropped. The i variable was used in a for loop before, but it's not necessary here as this application will use a while loop. The count variable is also no longer required as we don't need to count the number of items being stored.
10.	Prompt the user and read in the class name: printf ("Enter the classname (without spaces): "); scanf ("%11s", classname);
11.	Prompt the user and read in the input: printf ("Enter the student's name and their grade. Enter 0 0 0 to quit. (First Last ##.#): "); num = scanf ("%11s %11s %f", fn, ln, &g); The while loop in this application (see Step 12) will keep running as long as the user keeps entering valid records. To enter that while, the user must be prompted to enter the first record. Hence, this prompt is outside the loop structure.
12.	Define the while loop and create a conditional to check the validity of the input: while (fn[0] != '0') { if (num == 3) { The while loop checks if the first character of the first string is 0. As long as it isn't, the loop will be entered and the user can add another record. The conditional checks the validity of the input.
13.	Allocate memory for a new structure: new = (sg *) malloc(sizeof(sg)); Following the example in the introductory text, this creates a memory block capable of storing one structure. The returned value is then type-cast to be of the same type as the structure itself. Note also that this combination of malloc() and sizeof for the struct is a very common pattern that you will see and use again and again when working with dynamically allocated structures. Finally, you could (and should) perform a check here to see that the memory was properly allocated, but that check has been skipped in the interest of simplicity. See Chapter 10 for details.
14.	Assign the input to the structure: strncpy(new->first_name, fn, STR_LEN-1); new->first_name[STR_LEN-1] = ''; strncpy(new-last_name, ln, STR_LEN-1); new->last_name[STR_LEN-1] = ''; new->grade = g; The structure_var->member syntax is used to assign values to the structure. These lines store the inputted data in the allotted memory block.
15.	Adjust the pointers accordingly: new->next = first; first = new; The first time this loop is entered, first has no value but space has been allotted for a structure called new and data has been stored there (Step 14). The first line here assigns the next pointer member of new the value of first, which is NULL. This is desired since new is currently the tail of the list. The second line assigns the address of the new item (where the data is stored in memory) to first, since that's the first item in the list. Figure 13.15 shows the result after the initial iteration of the loop. Figure 13.15. The structure of the linked list after running through the loop for the first time. The second time this loop is entered, first has a value (it points to the first item in the list) and space has been allotted for a new structure (where data has been stored). The first line of code here will then assign the value of first to the new item's pointer member, so that the new item now points to the existing list. The second line then assigns the address of the new item to first, so that the first variable continues to point to the head of the list (Figure 13.16). Figure 13.16. The structure of the linked list after adding another item (to the head of the list).
16.	Complete the num conditional and the loop: } else { printf ("The data was not in the proper format. "); } If the value returned by scanf()—num—is not equal to 3, the data wasn't entered properly and a message is printed. There's no need to break the loop because the user can be prompted again.
17.	Re-prompt the user, read in the input, and complete the while loop: printf ("Enter the student's name and their grade. Enter 0 0 0 to quit. (First Last ##.#): "); num = scanf ("%11s %11s %f", fn, ln, &g); } /* End of while loop. */ Now that the record has been stored in memory, the user should be prompted again. After these lines, the while loop will recheck the value of fn to see whether another record is being entered.
18.	Begin printing all of the records: printf ("Students and grades for the class '%s': ", classname); This is the first line outside of the main while loop, which read in and stored all of the records.
19.	Define a loop for accessing every list element: new = first; while (new != NULL) { The first line takes the new pointer—which is no longer being used for anything—and assigns it the value of first. Now new can be used to access each list item. The while loop checks that new is not equal to NULL. Within the loop, new will be assigned the pointer value to the next element; if there is no next element, it will be null. At that point, the end of the list has been reached.
20.	Print the stored values: printf("%s %s %0.1f ", new- new- >first_name, new->last_name, new->grade); Because new now represents a list item, its values can be printed easily.
21.	Set temp to the next item: temp = new->next; To avoid problems on some systems, a temporary variable is assigned the value of the next list item (the memory address of that item).
22.	Free up the memory being used: free(new); It's very, very, very (very!) important that you free up all memory an application reserved with malloc(). Since you don't have pointers for each individual block of memory that was set aside, each block must be released while going through the entire list. If you omit this process, it will lead to a memory leak.
23.	Set new to the next item: new = temp; To continue through the list, the new pointer is set to the address of the next list item. When the loop reaches the tail of the list, new will be assigned a value of NULL here (which is the value of the pointer member in the final list item).
24.	Complete the while loop and the main function: } getchar(); getchar(); return 0; }
25.	Save the file as grades_list.c, compile, and debug as necessary.
26.	Run the application, varying the number of entries (Figure 13.17). Figure 13.17. The application can now take as many records as there is memory space for. The entire list is then redisplayed, in inverse order. [View full size image]