Hour 19. Storing Information in Linked Lists

Linked Lists and Other Structures

Arrays are much like Tupperware products. They are great containers, but they are each a fixed size. If you pick a container that is too large, you waste space in your storage area. If you pick one that is too small, there’s not enough room to hold what you need to store.

One way to solve this problem is with a linked list. A linked list is a data structure that consists of small containers that connect together. Containers, in this context, are classes that contain the objects to be held in the list. The idea is to write a class that holds one object of your data—such as one Cat or one Rectangle—and knows how to point to the next container in the list. You create one container for each object and chain them together.

These linked 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 to the next one forward, but not backward. To find a particular node, you start at the top and go from node to node in sequence. A doubly linked list enables you to move backward and forward to the next node and previous node. A tree is a complex structure built from nodes, each of which can point in two or three directions. Figure 19.1 shows these three fundamental structures.

Figure 19.1 Linked lists.

Computer scientists have created even more complex and clever data structures, most of which rely on interconnecting nodes.

Linked List Case Study

In this section, we examine a linked list in detail as a case study into how to use inheritance, polymorphism, and encapsulation to manage large projects. It’s also a chance to explore how to create complex structures in C++.

Delegation of Responsibility

A fundamental premise of object-oriented programming is that each object does one thing very well and delegates to other objects anything that is not part of its mission.

An automobile is an example of this idea. The engine’s job is to produce the power. Distribution of that power is not the engine’s job; that is up to the transmission. Turning is not the job of the engine or the transmission; that is delegated to the wheels.

A well-designed machine has lots of small, well-understood parts, each doing its own job and working together to accomplish a greater good. A well-designed program is much the same: Each class sticks to its own assignment, but together they create a functioning program.

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 and tail node to manage those parts of the list 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 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 does little work, simply delegating to the nodes.

The LinkedList program in Listing 19.1 is covered in detail. The source code is heavily commented to better explain how each part works.

Listing 19.1 The Full Text of LinkedList.cpp

---

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

---

When you run the LinkedList program, enter a series of numeric values one at a time. These values are used as the data stored in each linked list node. After you have entered as many values as you want, choose 0 to end input. The nodes in the linked list are displayed in ascending numeric order, as in this example:

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 (line 12), which provides three constant values: kIsSmaller, kIsLarger, and kIsSame. Every object that might be held in this linked list must support a compare() member function. These constants are the result value returned by this function.

The Data class is created on lines 18–27, and the compare() function is implemented on lines 31–39. A Data object holds a value and can compare itself with other Data objects. It also supports a show() member function 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 187, the main program is declared; on line 189, a pointer to a Data object is declared; and on line 191, a linked list is defined.

When the linked list is created, the constructor on line 175 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 (line 177).

This allocation of a HeadNode invokes the HeadNode constructor shown on line 146. This in turn allocates a TailNode and assigns its address to the head node’s next pointer. The creation of the TailNode calls the TailNode constructor shown on line 116, an inline function that 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.

Figure 19.2 The linked list after its creation.

Continuing in the main() function, line 195 uses while(true) for an infinite loop. The user is prompted for values to add to the linked list. The code on line 199 evaluates the value entered. If the value is 0, execution of the program breaks out of the loop.

If the value is not 0, a new Data object is created and inserted into the list (lines 201–202).

For illustration purposes, assume the user runs the program and enters the value 15. This invokes the insert() member function on line 202.

The linked list immediately delegates responsibility for inserting the object to its head node. This invokes the function insert() on line 153. The head node immediately passes the responsibility to whatever node its next variable points to. In this first case, it is pointing to the tail node. (When the head node was born, it created a link to a tail node.) This invokes the function insert() on line 125.

TailNode::insert() knows that the object it has been handed must be inserted immediately before itself, so the new object will be placed in the list right before the tail node. Therefore, on line 127 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 78.

The InternalNode constructor does nothing more than initialize its Data pointer with the address of the Data object it was passed and its next pointer with the node’s address it was passed. In this case, the node it points to is the tail node. (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 127, and that address is in turn returned from the TailNode::insert() member function.

This returns us to HeadNode::insert(), where the address of the InternalNode is assigned to the HeadNode’s next pointer (on line 155). Finally, the HeadNode’s address is returned to the linked list on line 183, although this value is not stored in a variable. 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? The insert() function 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 get a compiler error; it is simpler just to return the HeadNode and let the linked list do nothing with it.

Let’s review 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 next pointer to point to the new node.

Presto! The data is in the list in the right place, as illustrated in Figure 19.3.

Figure 19.3 The linked list after the first node is inserted.

After inserting the first node, program control resumes at line 195. 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 201 and inserted into the list on line 202.

Once again, on line 183 the list passes the data to its HeadNode. The HeadNode::insert() function in turn passes the new value to whatever its next 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() function on line 87.

On line 90, the InternalNode uses its data pointer to tell its Data object (the one whose value is 15) to call its compare() member function, passing in the new Data object (whose value is 3). This invokes the compare() function shown on line 31.

The two values are compared; and, because value is 15 and otherData.value is 3, the returned value is kIsLarger. This causes program flow to jump to line 97.

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() function 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.

Figure 19.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 should be inserted between the two existing nodes. Progress is exactly 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() function to branch to line 106. Instead of creating a new node and inserting it, the InternalNode passes the new data on to the Insert function of whatever its next 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 now 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 107.

The net effect is that the new node is inserted into the list at the right location.

The end result of all of this is that you have a sorted list of data items—no matter the order in which you enter the data.

Linked Lists as Objects

In object-oriented programming, each individual object is given a narrow and well-defined set of responsibilities. The linked list is responsible for maintaining the head node. The HeadNode immediately passes any new data on to whatever it currently points to, without regard for what that might be.

The TailNode, whenever it is handed data, creates a new node and inserts it. It knows only one thing: If this came to me, it gets inserted right before me.

Internal nodes are marginally more complicated; they ask their existing object to compare itself with the new object. Depending on the result, either they then insert or they just pass it along.

Note that the InternalNode has no idea how to do the comparison; that is properly left to the object itself. All the InternalNode knows is to ask the objects to compare themselves and to expect one of three possible answers. Given one answer, it inserts; otherwise, it just passes it along, not knowing or caring where it will end up.

So who’s in charge? In a well-designed object-oriented program, no one is in charge. Each object does its own little job, and the net effect is a well-running machine.

The beauty of a linked list is that you can put any data type you would like in the Data of this class. In this case, it contained an integer. It could contain multiple built-in data types or even other objects (including other linked lists).

The use of dynamic memory allows linked lists to use very little memory when small, and lots of memory if they grow large. The important thing is that they only use enough to hold the data they now contain. Arrays, on the other hand, are allocated to a specific size, which is both wasteful and limiting.

Summary

Because there’s so much to learn in C++, the projects undertaken in this book have often been short and illustrative. That makes it easier to focus on their functionality.

As you begin your own programming projects, you will find that the classes you create are never quite so simple.

The linked list case study during this hour consisted of five classes: Data, HeadNode, TailNode, InternalNode, and LinkedList. True to object-oriented programming methodology, each class took care of its own work and relied on the other objects to do theirs.

By understanding how these objects work together, you can develop a better sense of how to manage the relationships between objects.

Q&A

Q. Why should you create a linked list if an array will work?

A. An array must have a fixed size, whereas a linked list can be sized dynamically at runtime.

Q. Why do you separate the data object from the node?

A. Once you get your node objects working properly, you can reuse that code for any number of objects that might want to live in a list.

Q. If you want to add other objects to the list, do you have to create a new list type and a new node type?

A. For now, yes. We’ll solve that when we get to Hour 23, “Creating Templates.”

Q. What was the name of the Greek who carried a lantern and was looking for an honest man?

A. That was Diogenes, a philosopher who died around 320 B.C. Diogenes stressed self-sufficiency and the rejection of luxury, and his teachings caused him to be sent into exile away from his birthplace of Sinope, Paphlygonia. (I guess he didn’t have tenure.)

In addition to his search for an honest man, which Diogenes conducted with a lit lantern in broad daylight, there are other apocryphal stories associated with him.

He slept in public buildings, lived in poverty, begged for food and was strongly antifamily. Diogenes believed that men and women should be promiscuous and that any resulting children should be raised by the community instead of individual families.

Workshop

Now that you’ve learned how to implement a complex data structure, answer a few questions and perform a couple of exercises to link it all together.

Quiz

1. What’s the first node in a linked list called?

A. The origin

B. The head

C. The top

2. What two things does a linked list node contain?

A. Behavior and data

B. Functions and variables

C. Data and a node pointer

3. How many pointers are needed each node in a doubly linked list?

A. 2

B. 1

C. Either a or b

Answers

1. B. As the name implies, it contains the head of the linked list. It is very important to know where the list starts so it can be accessed.

2. C. The data can be any type of object. The pointer indicates the next member of the linked list.

3. A. Each node in a doubly linked list has two pointers, one for next and one for previous, so that you can start at either end and work your way toward the opposite end.

Activities

1. Rewrite the LinkedList program (Listing 19.1) to hold Tricycle objects rather than integers.

2. Add a function to the LinkedList class (Listing 19.1) that displays a count of the number of nodes the list contains.

To see solutions to these activities, visit this book’s website at http://cplusplus.cadenhead.org.