|
|
 |
|
|
|
|
Linked List A list in which the order of the components is determined by an explicit link member in each node, rather than by the sequential order of the components in memory. |
|
|
|
|
|
|
|
|
Array Representation of a Linked List |
|
|
|
|
|
|
|
|
A linked list can be represented as an array of structs. For a linked list of int components, we use the following declarations: |
|
|
|
|
|
|
|
|
struct NodeType
{
int component;
int link;
};
NodeType list[1000]; // Max. 1000 nodes
int head; |
|
|
|
|
|
|
|
|
The nodes all reside in an array named list. Each node has two members: component (in this example, an int data value) and link, which contains the array index of the next node in the list. The last node in the list will have a link member of -1. Because -1 is not a valid array index in C++, it is suitable as a special "end-of-list" value. The variable head contains the array index of the first node in the list. Figure 18-3 illustrates an array representation of the linked list of Figure 18-2. |
|
|
|
|
|
|
|
|
Compare Figures 18-1 and 18-3. Figure 18-1 shows a list represented directly as an array. Figure 18-3 shows a list represented as a linked list, which, in turn, is represented as an array (of structs). We said that when insertions and deletions occur frequently, it is better to use a linked list to represent a list than it is to use an array directly. Let's see why. |
|
|
|
|
|
|
|
|
Figure 18-1 showed the effect of inserting 25 into the list; we had to shift array elements 2, 3, 4, ... down to insert the value 25 into element 2. If the list is long, we might have to move hundreds or thousands of numbers. In contrast, inserting the value 25 into the linked list of Figure 18-3 requires no movement of existing data. We simply find an unused slot in the array, store 25 into the component member, and adjust the link member of the node containing 16 (see Figure 18-4). |
|
|
|
|
|
|
|
|
Before we introduce the second technique for implementing a linked list-the use of dynamic data and pointers-let's step back and look at the big picture. We are interested in the list as an ADT. Because it is an ADT, we |
|
|
|
|
|