Chapter 6: What Is a Linked List?

Sports fans probably don t realize that the coach uses a linked list all the time during the game when switching players. In fact, the coach probably doesn t realize it either. Many teams have three strings of players. For example, in football, there s the starting quarterback, a backup quarterback, and a third string quarterback. The coach has a list of their numbers . If the starter takes a hard hit, the coach looks at the list for the number of the next quarterback. When the backup quarterback can t do the job, the coach looks at the list again and chooses either the previous quarterback (the starter) or the next quarterback (third string).

As you probably surmised, the list the coach uses is a linked list because it links quarterbacks to the order in which they are called upon to play in the game. A linked list is a list of elements that point to the current data (current quarterback), the previous data (quarterback who just left the game), and the next data (quarterback who hasn t entered the game). In this chapter, you ll learn about single linked lists and doubly linked lists and how linked lists work. In the next two chapters, you ll learn common uses for linked lists.

A Linked List

A linked list is a data structure that makes it easy to rearrange data without having to move data in memory. Sound a little confusing? If so, picture a classroom of students who are seated in no particular order. A unique number identifies each seat, as shown in Figure 6-1. We ve also included the relative height of each student, which we ll use in the next exercise.

Figure 6-1: Students are seated in a classroom in random order.

Let s say that a teacher needs to place students names in alphabetical order so she can easily find a name on the list. One option is to have students change their seats so that Adam sits in seat 1, Bob sits in seat 2, and Mary in seat 3. However, this can be chaotic if there are a lot of students in the class.

Another option is to leave students seated and make a list of seat numbers that corresponds to the alphabetical order of students. The list would look something like this: 3, 1, and 2, as shown in Figure 6-1. The student in seat 3 is the first student who appears in alphabetical order, followed by the student seated in seat 1, and so on. Notice how this option doesn t disrupt the class.

Suppose you want to rearrange students in size order. There s a pretty good chance that you won t move students about the classroom. Instead, you d probably create another list of seat numbers that reflect each student s height. Here s the list: 1, 3, and 2, which is illustrated in Figure 6-1. The list can be read from bottom to top for the shortest to tallest or vice versa for tallest to shortest.

Once the list is created, the teacher can simply go down the list to see which seat contains the next student. To quiz students in alphabetical order, the teacher would use the alphabetical list to see that the student sitting in seat 3 is alphabetically first, followed by seat 1. The teacher can be tricky and call on the previous student by looking at the list to determine the student s seat.

Programmers call this sort of list a linked list because each item on the list is linked to the previous item and the next item. That is, the seat of the current student is linked to the seat of the previous student and to the seat of the next student by the list.

The Real World and Linked Lists

It is very important to keep the real world in mind as you learn how to use a linked list; otherwise , you ll fall into the trap of thinking that a linked list is an abstract concept that has little use in the real world. Actually, linked lists play a critical role in applications that help companies and governments manage data dynamically.

There are two versions of a linked list, a single link and a double link. A single link list enables a program to move through the list in one direction, which is usually from the front of the list moving to the end of the list. A doubly linked list enables the program to move through the list in both directions. We ll focus on the doubly linked list for most of the examples in this chapter and then discuss the single link list toward the end of the chapter.

Although we ve mentioned that an entry in a linked list contains data and pointers to the previous and next entries in the list, this is an oversimplification. The data we re talking about is typically a set of data such as customer information. Customer information could be a customer ID, customer first name, customer last name, customer street address, customer city, customer state, customer ZIP, and so on. Programmers call this a record. This means that an entry in a linked list may contain several data elements. In our example, however, we ll store only a single value of an integer so that we can focus on the principle of how a linked list works. In reality, you can add as many additional attributes to each node as you need.

Programmers choose linked lists over an array because linked lists can grow or shrink in size during runtime. Another entry can be placed at the end of the last entry on the linked list simply by assigning reference to the new entry in the last entry on the linked list.

Likewise, the last entry can be removed from the linked list by simply removing reference to it in the next element of the second-to-last entry on the linked list. This is more efficient than using an array and resizing at runtime.

If you change the size of the array, the operating system tries to increase the array by using memory alongside the array. If this location is unavailable, then the operating system finds another location large enough to hold elements of the array and new array elements. Elements of the array are then copied to the new location.

If you change the size of a linked list, the operating system changes references to the previous item and the next item on the list, which is fewer steps than changing the size of an array.