The Component Parts

The linked list will consist of nodes. The node class itself will be abstract; we'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 that is linked.

The program doesn't actually know about the nodes; it only works with the list. The list, however, does little work; it simply delegates to the nodes.

Listing 19.1 shows the code; we'll examine it in excruciating detail:

Listing 19.1. Linked List

0:  // ***********************************************
1:  //    FILE:        Listing 19.1
2:  //
3:  //    PURPOSE:    Demonstrate ilinked list
4:  //    NOTES:
5:  //
6:  //  COPYRIGHT:  Copyright (C) 1997 Liberty Associates, Inc.
7:  //                All Rights Reserved
8:  //
9:  // Demonstrates an object-oriented approach to
10:  // linked lists. The list delegates to the node.
11:  // The node is an abstract data type. Three types of
12:  // nodes are used, head nodes, tail nodes and internal
13:  // nodes. Only the internal nodes hold data.
14:  //
15:  // The Data class is created to serve as an object to
16:  // hold in the linked list.
17:  //
18:  // ***********************************************
19:  #include <iostream>
20:
21:  enum { kIsSmaller, kIsLarger, kIsSame};
22:
23:  // Data class to put into the linked list
24:  // Any class in this linked list must support two methods:
25:  // Show (displays the value) and Compare
26:  // (returns relative position)
27:  class Data
28:  {
29:  public:
30:      Data(int val):myValue(val){}
31:      ~Data(){}
32:      int Compare(const Data &);
33:      void Show() { std::cout << myValue << std::endl; }
34:  private:
35:      int myValue;
36:  };
37:
38:  // Compare is used to decide where in the list
39:  // a particular object belongs.
40:  int Data::Compare(const Data & theOtherData)
41:  {
42:      if (myValue < theOtherData.myValue)
43:          return kIsSmaller;
44:      if (myValue > theOtherData.myValue)
45:          return kIsLarger;
46:      else
47:          return kIsSame;
48:  }
49:
50:  // forward declarations
51:  class Node;
52:  class HeadNode;
53:  class TailNode;
54:  class InternalNode;
55:
56:  // ADT representing the node object in the list
57:  // Every derived class must override Insert and Show
58:  class Node
59:  {
60:  public:
61:      Node(){}
62:      virtual ~Node(){}
63:      virtual Node * Insert(Data * theData)=0;
64:      virtual void Show() = 0;
65:  private:
66:  };
67:
68:  // This is the node which holds the actual object
69:  // In this case the object is of type Data
70:  // We'll see how to make this more general when
71:  // we cover templates
72:  class InternalNode: public Node
73:  {
74:  public:
75:      InternalNode(Data * theData, Node * next);
76:      virtual ~InternalNode(){ delete myNext; delete myData; }
77:      virtual Node * Insert(Data * theData);
78:      virtual void Show()
79:          { myData->Show(); myNext->Show(); } // delegate!
80:
81:  private:
82:      Data * myData;  // the data itself
83:      Node * myNext;    // points to next node in the linked list
84:  };
85:
86:  // All the constructor does is to initialize
87:  InternalNode::InternalNode(Data * theData, Node * next):
88:  myData(theData),myNext(next)
89:  {
90:  }
91:
92:  // the meat of the list
93:  // When you put a new object into the list
94:  // it is passed ot the node which figures out
95:  // where it goes and inserts it into the list
96:  Node * InternalNode::Insert(Data * theData)
97:  {
98:
99:      // is the new guy bigger or smaller than me?
100:      int result = myData->Compare(*theData);
101:
102:
103:      switch(result)
104:      {
105:      // by convention if it is the same as me it comes first
106:      case kIsSame:      // fall through
107:      case kIsLarger:    // new data comes before me
108:          {
109:              InternalNode * dataNode =
110:                  new InternalNode(theData, this);
111:              return dataNode;
112:          }
113:
114:          // it is bigger than I am so pass it on to the next
115:          // node and let HIM handle it.
116:      case kIsSmaller:
117:          myNext = myNext->Insert(theData);
118:          return this;
119:      }
120:      return this;  // appease MSC
121:  }
122:
123:
124:   // Tail node is just a sentinel
125:   class TailNode : public Node
126:  {
127:  public:
128:      TailNode(){}
129:      virtual ~TailNode(){}
130:      virtual Node * Insert(Data * theData);
131:      virtual void Show() { }
132:  private:
133:  };
134:
135:  // If data comes to me, it must be inserted before me
136:  // as I am the tail and NOTHING comes after me
137:  Node * TailNode::Insert(Data * theData)
138:  {
139:      InternalNode * dataNode = new InternalNode(theData, this);
140:      return dataNode;
141:  }
142:
143:  // Head node has no data, it just points
144:  // to the very beginning of the list
145:  class HeadNode : public Node
146:  {
147:  public:
148:      HeadNode();
149:      virtual ~HeadNode() { delete myNext; }
150:      virtual Node * Insert(Data * theData);
151:      virtual void Show() { myNext->Show(); }
152:  private:
153:      Node * myNext;
154:  };
155:
156:  // As soon as the head is created
157:  // it creates the tail
158:  HeadNode::HeadNode()
159:  {
160:      myNext = new TailNode;
161:  }
162:
163:  // Nothing comes before the head so just
164:  // pass the data on to the next node
165:  Node * HeadNode::Insert(Data * theData)
166:  {
167:      myNext = myNext->Insert(theData);
168:      return this;
169:  }
170:
171:  // I get all the credit and do none of the work
172:  class LinkedList
173:  {
174:  public:
175:      LinkedList();
176:      ~LinkedList() { delete myHead; }
177:      void Insert(Data * theData);
178:      void ShowAll() { myHead->Show(); }
179:  private:
180:      HeadNode * myHead;
181:  };
182:
183:  // At birth, i create the head node
184:  // It creates the tail node
185:  // So an empty list points to the head which
186:  // points to the tail and has nothing between
187:  LinkedList::LinkedList()
188:  {
189:      myHead = new HeadNode;
190:  }
191:
192:  // Delegate, delegate, delegate
193:  void LinkedList::Insert(Data * pData)
194:  {
195:      myHead->Insert(pData);
196:  }
197:
198:  // test driver program
199:  int main()
200:  {
201:      Data * pData;
202:      int val;
203:      LinkedList ll;
204:
205:      // ask the user to produce some values
206:      // put them in the list
207:      for (;;)
208:      {
209:          std::cout << "What value? (0 to stop): ";
210:          std::cin >> val;
211:          if (!val)
212:              break;
213:          pData = new Data(val);
214:          ll.Insert(pData);
215:      }
216:
217:      // now walk the list and show the data
218:      ll.ShowAll();
219:      return 0;  // ll falls out of scope and is destroyed!
220:  }

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, which provides three constant values: kIsSmaller, kIsLarger, and kIsSame. Every object that may 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 27–36, and the Compare() method is implemented on lines 40–48. 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 199 the main program is declared, on line 201 a pointer to a Data object is declared, and on line 203 a local linked list is defined.

When the linked list is created, the constructor on line 187 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 180.

This allocation of a HeadNode invokes the HeadNode constructor shown on line 158. 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 128, which is inline and 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 19.2.

Line 207 begins an infinite loop. The user will be 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 211 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 213, and that is inserted into the list on line 214. For illustration purposes, assume the user enters the value 15. This invokes the Insert method on line 193.

The linked list immediately delegates responsibility for inserting the object to its head node. This invokes the method Insert on line 165. 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 137.

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 139 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 87.

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 will point 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 139, 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 167). Finally, the HeadNode's address is returned to the linked list where, on line 195, 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 will get 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 19.3.

After inserting the first node, program control resumes at line 209. 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 213 and to be inserted into the list on line 214.

Once again, on line 195 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 96.

On line 100, 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 40.

The two values are compared; and, because myValue will be 15 and theOtherData.myValue will be 3, the returned value will be kIsLarger. This will cause program flow to jump to line 107.

A new InternalNode is created for the new Data object. The new node will point 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 19.4.

In the third invocation of the loop, the customer adds the value 8. This is larger than 3 but smaller than 15, and so should be inserted between the two existing nodes. Progress will be exactly like the previous example except that when the node whose object's value is 3 does the compare, rather than returning kIsLarger, it will return kIsSmaller (meaning that the object whose value is 3 is smaller than the new object, whose value is 8).

This will cause the InternalNode::Insert() method to branch to line 116. Rather than creating a new node and inserting it, the InternalNode will just pass the new data on to the Insert method of whatever its myNext pointer happens to be pointing to. In this case, it will invoke InsertNode on the InternalNode whose Data object's value is 15.

The comparison will be done again, and now a new InternalNode will be created. This new InternalNode will point to the InternalNode whose Data object's value is 15, and its address will be passed back to the InternalNode whose Data object's value is 3, as shown on line 118.

The net effect is that the new node will be 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.