On Day 13, “Managing Arrays and Strings,” you learned about arrays. You also learned what a linked list is. A linked list is a data structure that consists of small containers that are designed to link together as needed. The idea is to write a class that holds one object of your data that can point at the next container of the same type. You create one container for each object that you need to store, and you chain them together as needed.
The containers are called nodes. The first node in the list is called the head, and the last node in the list is called the tail.
Lists come in three fundamental forms. From simplest to most complex, they are
• Singly linked
• Doubly linked
• Trees
In a singly linked list, each node points forward to the next one, but not backward. To find a particular node, start at the top and go from node to node, as in a treasure hunt (“The next node is under the sofa”). A doubly linked list enables you to move backward and forward in the chain. A tree is a complex structure built from nodes, each of which can point in two or more directions. Figure E.1 shows these three fundamental structures.
Figure E.1. Linked lists.
In this appendix, you examine a linked list in detail as a case study of how you create complex structures and, more importantly, how you use them.
The linked lists you create will consist of nodes. The node class itself will be abstract; you’ll use three subtypes to accomplish the work. There will be a head node whose job is to manage the head of the list, a tail node (guess what its job is!), and zero or more internal nodes. The internal nodes will keep track of the actual data to be held in the list.
Note that the data and the list are quite distinct. You can, in theory, save any type of data you like in a list. It isn’t the data that is linked together; it is the node that holds the data.
The driver program doesn’t know about the nodes; it works with the list. The list, however, does little work; it simply delegates to the nodes.
Listing E.1 shows the code; you’ll examine it in excruciating detail in the rest of this appendix.
Listing E.1. Linked List
What value? (0 to stop): 5
What value? (0 to stop): 8
What value? (0 to stop): 3
What value? (0 to stop): 9
What value? (0 to stop): 2
What value? (0 to stop): 10
What value? (0 to stop): 0
2
3
5
8
9
10
The first thing to note is the enumerated constant defined on line 24, which provides three constant values: kIsSmaller
, kIsLarger
, and kIsSame
. Every object that might be held in this linked list must support a Compare()
method. These constants will be the result value returned by the Compare()
method.
For illustration purposes, the class Data
is created on lines 30–39, and the Compare()
method is implemented on lines 43–51. A Data
object holds a value and can compare itself with other Data
objects. It also supports a Show()
method to display the value of the Data
object.
The easiest way to understand the workings of the linked list is to step through an example of using one. On line 203, a driver program is declared; on line 206, a pointer to a Data
object is declared; and on line 208, a local linked list is defined.
You can see the LinkList
class on lines 177–186. When the linked list is created, the constructor on line 192 is called. The only work done in the constructor is to allocate a HeadNode
object and to assign that object’s address to the pointer held in the linked list on line 185.
This allocation of a HeadNode
invokes the HeadNode
constructor shown on lines 163–166. This, in turn, allocates a TailNode
and assigns its address to the head node’s myNext
pointer. The creation of the TailNode
calls the TailNode
constructor shown on line 131, which is inline and which does nothing.
Thus, by the simple act of allocating a linked list on the stack, the list is created, a head and a tail node are created, and their relationship is established, as illustrated in Figure E.2.
Figure E.2. The linked list after it is created.
Back in the driver program, line 212 begins an infinite loop. The user is prompted for values to add to the linked list. He can add as many values as he likes, entering 0
when he is finished. The code on line 216 evaluates the value entered; if it is 0
, it breaks out of the loop.
If the value is not 0
, a new Data
object is created on line 218, and that is inserted into the list on line 219. For illustration purposes, assume the user enters the value 15
. This invokes the Insert
method on line 198.
The linked list
immediately delegates responsibility for inserting the object to its head node. This invokes the method Insert
on line 170. The head node immediately passes the responsibility to whatever node its myNext
is pointing to. In this (first) case, it is pointing to the tail node (remember, when the head node was born, it created a link to a tail node). This, therefore, invokes the method Insert
on line 142.
TailNode::Insert
knows that the object it has been handed must be inserted immediately before itself—that is, the new object will be in the list right before the tail node. Therefore, on line 144 it creates a new InternalNode
object, passing in the data and a pointer to itself. This invokes the constructor for the InternalNode
object, shown on line 90.
The InternalNode
constructor does nothing more than initialize its Data
pointer with the address of the Data
object it was passed and its myNext
pointer with the node’s address it was passed. In this case, the node it points to is the tail node (remember, the tail node passed in its own this
pointer).
Now that the InternalNode
has been created, the address of that internal node is assigned to the pointer dataNode
on line 144, and that address is in turn returned from the TailNode::Insert()
method. This returns us to HeadNode::Insert()
, where the address of the InternalNode
is assigned to the HeadNode
’s myNext
pointer (on line 172). Finally, the HeadNode
’s address is returned to the linked list where, on line 200, it is thrown away (nothing is done with it because the linked list already knows the address of the head node).
Why bother returning the address if it is not used? Insert
is declared in the base class, Node
. The return value is needed by the other implementations. If you change the return value of HeadNode::Insert()
, you receive a compiler error; it is simpler just to return the HeadNode
and let the linked list throw its address on the floor.
So what happened? The data was inserted into the list. The list passed it to the head. The head, blindly, passed the data to whatever the head happened to be pointing to. In this (first) case, the head was pointing to the tail. The tail immediately created a new internal node, initializing the new node to point to the tail. The tail then returned the address of the new node to the head, which reassigned its myNext
pointer to point to the new node. Hey! Presto! The data is in the list in the right place, as illustrated in Figure E.3.
Figure E.3. The linked list after the first node is inserted.
After inserting the first node, program control resumes at line 214. Once again, the value is evaluated. For illustration purposes, assume that the value 3
is entered. This causes a new Data
object to be created on line 218 and to be inserted into the list on line 219.
Once again, on line 200, the list passes the data to its HeadNode
. The HeadNode::Insert()
method, in turn, passes the new value to whatever its myNext
happens to be pointing to. As you know, it is now pointing to the node that contains the Data
object whose value is 15
. This invokes the InternalNode::Insert()
method on line 99.
On line 103, the InternalNode
uses its myData
pointer to tell its Data
object (the one whose value is 15
) to call its Compare()
method, passing in the new Data
object (whose value is 3
). This invokes the Compare()
method shown on line 43.
The two values are compared, and, because myValue
will be 15
and theOtherData.myValue
will be 3
, the returned value will be kIsLarger
. This causes program flow to jump to the kIsLarger
case on line 110.
A new InternalNode
is created for the new Data
object. The new node points to the current InternalNode
object, and the new InternalNode
’s address is returned from the InternalNode::Insert()
method to the HeadNode
. Thus, the new node, whose object’s value is smaller than the current node’s object’s value, is inserted into the list, and the list now looks like Figure E.4.
Figure E.4. The linked list after the second node is inserted.
In the third invocation of the loop, the customer adds the value 8
. This is larger than 3
but smaller than 15
, and so it should be inserted between the two existing nodes. Progress is like the previous example, except that when the node whose object’s value is 3
does the compare, rather than returning kIsLarger
, it returns kIsSmaller
(meaning that the object whose value is 3
is smaller than the new object, whose value is 8
). This causes the InternalNode::Insert()
method to branch to the kIsSmaller
case on line 118. Rather than creating a new node and inserting it, the InternalNode
just passes the new data on to the Insert
method of whatever its myNext
pointer happens to be pointing to. In this case, it invokes InsertNode
on the InternalNode
whose Data
object’s value is 15
.
The comparison is done again, and a new InternalNode
is created. This new InternalNode
points to the InternalNode
whose Data
object’s value is 15
, and its address is passed back to the InternalNode
whose Data
object’s value is 3
, as shown on line 119.
The net effect is that the new node is inserted into the list at the right location.
If at all possible, you’ll want to step through the insertion of a number of nodes in your debugger. You should be able to watch these methods invoke one another and the pointers be properly adjusted.
3.139.97.40