|
|
|
|
|
|
|
When insertions and deletions are frequent, there is a better data representation for a list: the linked list. A linked list is a collection of items, called nodes, that can be scattered about in memory, not necessarily in consecutive memory locations. Each node, typically implemented as a struct, consists of two members: |
|
|
|
|
|
|
|
|
1. A component member, which contains one of the data values in the list |
|
|
|
|
|
|
|
|
2. A link member, which gives the location of the next node in the list |
|
|
|
|
|
|
|
|
Figure 18-2 shows an abstract diagram of a linked list. An arrow is used in the link member of each node to indicate the location of the next node. The slash (/) in the link member of the last node signifies the end of the list. The separate variable head is not a node in the linked list; its purpose is to give the location of the first node. |
|
|
|
|
|
|
|
|
Accessing the items in a linked list is a little like playing the children's game of treasure hunt-each child is given a clue to the hiding place of the next clue, and the chain of clues eventually leads to the treasure. |
|
|
|
|
|
|
|
|
As you look at Figure 18-2, you should observe two things. First, we have deliberately arranged the nodes in random positions. We have done this to emphasize the fact that the items in a linked list are not necessarily in adjacent memory locations (as they are in the array representation of Figure 18-1a). Second, you may already be thinking of pointers when you see the arrows in the figure because we drew pointer variables this way in Chapter 17. But so far, we have carefully avoided using the word pointer; we said only that the link member of a node gives the location of the next node. As we will see, there are two ways in which to implement a linked list. One way is to store it in an array of structs, a technique that does not use pointers at all. The second way is to use dynamic data and pointers. Let's begin with the first of these two techniques. |
|
|
|
|
|
|
|
|
Figure 18-2
A Linked List |
|
|
|
|
|
