Linked Lists

A linked list is a linear collection of self-referential class objects, called nodes, connected by pointer linkshence, the term "linked" list. A linked list is accessed via a pointer to the first node of the list. Each subsequent node is accessed via the link-pointer member stored in the previous node. By convention, the link pointer in the last node of a list is set to null (0) to mark the end of the list. Data is stored in a linked list dynamicallyeach node is created as necessary. A node can contain data of any type, including objects of other classes. If nodes contain base-class pointers to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use virtual function calls to process these objects polymorphically. Stacks and queues are also linear data structures and, as we will see, can be viewed as constrained versions of linked lists. Trees are nonlinear data structures.

Lists of data can be stored in arrays, but linked lists provide several advantages. A linked list is appropriate when the number of data elements to be represented at one time is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary. The size of a "conventional" C++ array, however, cannot be altered, because the array size is fixed at compile time. "Conventional" arrays can become full. Linked lists become full only when the system has insufficient memory to satisfy dynamic storage allocation requests.

---

Performance Tip 21.1

An array can be declared to contain more elements than the number of items expected, but this can waste memory. Linked lists can provide better memory utilization in these situations. Linked lists allow the program to adapt at runtime. Note that class template vector (introduced in Section 7.11) implements a dynamically resizable array-based data structure.

Linked lists can be maintained in sorted order by inserting each new element at the proper point in the list. Existing list elements do not need to be moved.

Performance Tip 21.2

Insertion and deletion in a sorted array can be time consumingall the elements following the inserted or deleted element must be shifted appropriately. A linked list allows efficient insertion operations anywhere in the list.

Performance Tip 21.3

The elements of an array are stored contiguously in memory. This allows immediate access to any array element, because the address of any element can be calculated directly based on its position relative to the beginning of the array. Linked lists do not afford such immediate "direct access" to their elements. So accessing individual elements in a linked list can be considerably more expensive than accessing individual elements in an array. The selection of a data structure is typically based on the performance of specific operations used by a program and the order in which the data items are maintained in the data structure. For example, it is typically more efficient to insert an item in a sorted linked list than a sorted array.

Linked list nodes are normally not stored contiguously in memory. Logically, however, the nodes of a linked list appear to be contiguous. Figure 21.2 illustrates a linked list with several nodes.

Figure 21.2. A graphical representation of a list.

Performance Tip 21.4

Using dynamic memory allocation (instead of fixed-size arrays) for data structures that grow and shrink at execution time can save memory. Keep in mind, however, that pointers occupy space and that dynamic memory allocation incurs the overhead of function calls.

---

Linked List Implementation

The program of Figs. 21.321.5 uses a List class template (see Chapter 14 for information on class templates) to manipulate a list of integer values and a list of floating-point values. The driver program (Fig. 21.5) provides five options: 1) Insert a value at the beginning of the list, 2) insert a value at the end of the list, 3) delete a value from the beginning of the list, 4) delete a value from the end of the list and 5) end the list processing. A detailed discussion of the program follows. Exercise 21.20 asks you to implement a recursive function that prints a linked list backward, and Exercise 21.21 asks you to implement a recursive function that searches a linked list for a particular data item.

Figure 21.3. ListNode class-template definition.

(This item is displayed on pages 1003 - 1004 in the print version)

 1 // Fig. 21.3: Listnode.h
 2 // Template ListNode class definition.
 3 #ifndef LISTNODE_H
 4 #define LISTNODE_H
 5
 6 // forward declaration of class List required to announce that class 
 7 // List exists so it can be used in the friend declaration at line 13
 8 template< typename NODETYPE > class List; 
 9
10 template< typename NODETYPE>
11 class ListNode
12 {
13 friend class List< NODETYPE >; // make List a friend
14
15 public:
16 ListNode( const NODETYPE & ); // constructor
17 NODETYPE getData() const; // return data in node
18 private:
19 NODETYPE data; // data
20 ListNode< NODETYPE > *nextPtr; // next node in list
21 }; // end class ListNode
22
23 // constructor
24 template< typename NODETYPE>
25 ListNode< NODETYPE >::ListNode( const NODETYPE &info )
26 : data( info ), nextPtr( 0 )
27 {
28 // empty body
29 } // end ListNode constructor
30
31 // return copy of data in node
32 template< typename NODETYPE >
33 NODETYPE ListNode< NODETYPE >::getData() const
34 {
35 return data;
36 } // end function getData
37
38 #endif

The program uses class templates ListNode (Fig. 21.3) and List (Fig. 21.4). Encapsulated in each List object is a linked list of ListNode objects. Class template ListNode (Fig. 21.3) contains private members data and nextPtr (lines 1920), a constructor to initialize these members and function getdata to return the data in a node. Member data stores a value of type NODETYPE, the type parameter passed to the class template. Member nextPtr stores a pointer to the next ListNode object in the linked list. Note that line 13 of the ListNode class template definition declares class List< NODETYPE > as a friend. This makes all member functions of a given specialization of class template List friends of the corresponding specialization of class template ListNode, so they can access the private members of ListNode objects of that type. Because the ListNode template parameter NODETYPE is used as the template argument for List in the friend declaration, ListNodes specialized with a particular type can be processed only by a List specialized with the same type (e.g., a List of int values manages ListNode objects that store int values).

---

Figure 21.4. List class-template definition.

(This item is displayed on pages 1004 - 1007 in the print version)

 1 // Fig. 21.4: List.h
 2 // Template List class definition.
 3 #ifndef LIST_H
 4 #define LIST_H
 5
 6 #include 
 7 using std::cout;
 8
 9 #include "listnode.h" // ListNode class definition
10
11 template< typename NODETYPE >
12 class List
13 {
14 public:
15 List(); // constructor
16 ~List(); // destructor
17 void insertAtFront( const NODETYPE & );
18 void insertAtBack( const NODETYPE & ); 
19 bool removeFromFront( NODETYPE & ); 
20 bool removeFromBack( NODETYPE & ); 
21 bool isEmpty() const; 
22 void print() const; 
23 private:
24 ListNode< NODETYPE > *firstPtr; // pointer to first node
25 ListNode< NODETYPE > *lastPtr; // pointer to last node 
26
27 // utility function to allocate new node
28 ListNode< NODETYPE > *getNewNode( const NODETYPE & );
29 }; // end class List
30
31 // default constructor
32 template< typename NODETYPE >
33 List< NODETYPE >::List()
34 : firstPtr( 0 ), lastPtr( 0 )
35 {
36 // empty body
37 } // end List constructor
38
39 // destructor
40 template< typename NODETYPE >
41 List< NODETYPE >::~List()
42 {
43 if ( !isEmpty() ) // List is not empty
44 {
45 cout << "Destroying nodes ...
";
46
47 ListNode< NODETYPE > *currentPtr = firstPtr;
48 ListNode< NODETYPE > *tempPtr;
49
50 while ( currentPtr != 0 ) // delete remaining nodes
51 {
52 tempPtr = currentPtr;
53 cout << tempPtr->data << '
';
54 currentPtr = currentPtr->nextPtr;
55 delete tempPtr;
56 } // end while
57 } // end if
58
59 cout << "All nodes destroyed

";
60 } // end List destructor
61
62 // insert node at front of list
63 template< typename NODETYPE >
64 void List< NODETYPE >::insertAtFront( const NODETYPE &value )
65 {
66 ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node
67
68 if ( isEmpty() ) // List is empty
69 firstPtr = lastPtr = newPtr; // new list has only one node
70 else // List is not empty
71 {
72 newPtr->nextPtr = firstPtr; // point new node to previous 1st node
73 firstPtr = newPtr; // aim firstPtr at new node
74 } // end else
75 } // end function insertAtFront
76
77 // insert node at back of list
78 template< typename NODETYPE >
79 void List< NODETYPE >::insertAtBack( const NODETYPE &value )
80 {
81 ListNode< NODETYPE > *newPtr = getNewNode( value ); // new node
82
83 if ( isEmpty() ) // List is empty
84 firstPtr = lastPtr = newPtr; // new list has only one node
85 else // List is not empty
86 {
87 lastPtr->nextPtr = newPtr; // update previous last node
88 lastPtr = newPtr; // new last node
89 } // end else
90 } // end function insertAtBack
91
92 // delete node from front of list
93 template< typename NODETYPE >
94 bool List< NODETYPE >::removeFromFront( NODETYPE &value )
95 {
96 if ( isEmpty() ) // List is empty
97 return false; // delete unsuccessful
98 else
99 {
100 ListNode< NODETYPE > *tempPtr = firstPtr; // hold tempPtr to delete
101
102 if ( firstPtr == lastPtr )
103 firstPtr = lastPtr = 0; // no nodes remain after removal
104 else
105 firstPtr = firstPtr->nextPtr; // point to previous 2nd node
106
107 value = tempPtr->data; // return data being removed
108 delete tempPtr; // reclaim previous front node
109 return true; // delete successful
110 } // end else
111 } // end function removeFromFront
112
113 // delete node from back of list
114 template< typename NODETYPE >
115 bool List< NODETYPE >::removeFromBack( NODETYPE &value )
116 {
117 if ( isEmpty() ) // List is empty
118 return false; // delete unsuccessful
119 else
120 {
121 ListNode< NODETYPE > *tempPtr = lastPtr; // hold tempPtr to delete
122
123 if ( firstPtr == lastPtr ) // List has one element
124 firstPtr = lastPtr = 0; // no nodes remain after removal
125 else
126 {
127 ListNode< NODETYPE > *currentPtr = firstPtr;
128
129 // locate second-to-last element
130 while ( currentPtr->nextPtr != lastPtr )
131 currentPtr = currentPtr->nextPtr; // move to next node
132
133 lastPtr = currentPtr; // remove last node
134 currentPtr->nextPtr = 0; // this is now the last node
135 } // end else
136
137 value = tempPtr->data; // return value from old last node
138 delete tempPtr; // reclaim former last node
139 return true; // delete successful
140 } // end else
141 } // end function removeFromBack
142
143 // is List empty?
144 template< typename NODETYPE >
145 bool List< NODETYPE >::isEmpty() const
146 {
147 return firstPtr == 0;
148 } // end function isEmpty
149
150 // return pointer to newly allocated node
151 template< typename NODETYPE >
152 ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
153 const NODETYPE &value )
154 {
155 return new ListNode< NODETYPE >( value );
156 } // end function getNewNode
157
158 // display contents of List
159 template< typename NODETYPE >
160 void List< NODETYPE >::print() const
161 {
162 if ( isEmpty() ) // List is empty
163 {
164 cout << "The list is empty

";
165 return;
166 } // end if
167
168 ListNode< NODETYPE > *currentPtr = firstPtr;
169
170 cout << "The list is: ";
171
172 while ( currentPtr != 0 ) // get element data
173 {
174 cout << currentPtr->data << ' ';
175 currentPtr = currentPtr->nextPtr;
176 } // end while
177
178 cout << "

";
179 } // end function print
180
181 #endif

Figure 21.5. Manipulating a linked list.

(This item is displayed on pages 1007 - 1010 in the print version)

 1 // Fig. 21.5: Fig21_05.cpp
 2 // List class test program.
 3 #include 
 4 using std::cin;
 5 using std::cout;
 6 using std::endl;
 7
 8 #include 
 9 using std::string;
10
11 #include "List.h" // List class definition
12
13 // function to test a List
14 template< typename T >
15 void testList( List< T > &listObject, const string &typeName )
16 {
17 cout << "Testing a List of " << typeName << " values
";
18 instructions(); // display instructions
19
20 int choice; // store user choice
21 T value; // store input value
22
23 do // perform user-selected actions
24 {
25 cout << "? ";
26 cin >> choice;
27
28 switch ( choice )
29 {
30 case 1: // insert at beginning
31 cout << "Enter " << typeName << ": ";
32 cin >> value;
33 listObject.insertAtFront( value );
34 listObject.print(); 
35 break;
36 case 2: // insert at end
37 cout << "Enter " << typeName << ": ";
38 cin >> value;
39 listObject.insertAtBack( value );
40 listObject.print(); 
41 break;
42 case 3: // remove from beginning
43 if ( listObject.removeFromFront( value ) )
44 cout << value << " removed from list
";
45
46 listObject.print();
47 break;
48 case 4: // remove from end
49 if ( listObject.removeFromBack( value ) )
50 cout << value << " removed from list
";
51
52 listObject.print();
53 break;
54 } // end switch
55 } while ( choice != 5 ); // end do...while
56
57 cout << "End list test

";
58 } // end function testList
59
60 // display program instructions to user
61 void instructions()
62 {
63 cout << "Enter one of the following:
"
64 << " 1 to insert at beginning of list
"
65 << " 2 to insert at end of list
"
66 << " 3 to delete from beginning of list
"
67 << " 4 to delete from end of list
"
68 << " 5 to end list processing
";
69 } // end function instructions
70
71 int main()
72 {
73 // test List of int values
74 List< int > integerList;
75 testList( integerList, "integer" );
76
77 // test List of double values
78 List< double > doubleList;
79 testList( doubleList, "double" );
80 return 0;
81 } // end main

 

 Testing a List of integer values
 Enter one of the following:
 1 to insert at beginning of list
 2 to insert at end of list
 3 to delete from beginning of list
 4 to delete from end of list
 5 to end list processing
 ? 1
 Enter integer: 1
 The list is: 1

 ? 1
 Enter integer: 2
 The list is: 2 1

 ? 2
 Enter integer: 3
 The list is: 2 1 3

 ? 2
 Enter integer: 4
 The list is: 2 1 3 4

 ? 3
 2 removed from list
 The list is: 1 3 4

 ? 3
 1 removed from list
 The list is: 3 4

 ? 4
 4 removed from list
 The list is: 3

 ? 4
 3 removed from list
 The list is empty

 ? 5
 End list test

 Testing a List of double values
 Enter one of the following:
 1 to insert at beginning of list
 2 to insert at end of list
 3 to delete from beginning of list
 4 to delete from end of list
 5 to end list processing
 ? 1
 Enter double: 1.1
 The list is: 1.1

 ? 1
 Enter double: 2.2
 The list is: 2.2 1.1

 ? 2
 Enter double: 3.3
 The list is: 2.2 1.1 3.3

 ? 2
 Enter double: 4.4
 The list is: 2.2 1.1 3.3 4.4

 ? 3
 2.2 removed from list
 The list is: 1.1 3.3 4.4

 ? 3
 1.1 removed from list
 The list is: 3.3 4.4

 ? 4
 4.4 removed from list
 The list is: 3.3

 ? 4
 3.3 removed from list
 The list is empty

 ? 5
 End list test

 All nodes destroyed

 All nodes destroyed

 

Lines 2425 of the List class template (Fig. 21.4) declare private data members firstPtr (a pointer to the first ListNode in a List) and lastPtr (a pointer to the last ListNode in a List). The default constructor (lines 3237) initializes both pointers to 0 (null). The destructor (lines 4060) ensures that all ListNode objects in a List object are destroyed when that List object is destroyed. The primary List functions are insertAtFront (lines 6375), insertAtBack (lines 7890), removeFromFront (lines 93111) and removeFromBack (lines 114141).

Function isEmpty (lines 144148) is called a predicate functionit does not alter the List; rather, it determines whether the List is empty (i.e., the pointer to the first node of the List is null). If the List is empty, true is returned; otherwise, false is returned. Function print (lines 159179) displays the List's contents. Utility function getNewNode (lines 151156) returns a dynamically allocated ListNode object. This function is called from functions insertAtFront and insertAtBack.

Error-Prevention Tip 21.1

Assign null (0) to the link member of a new node. Pointers should be initialized before they are used.

The driver program (Fig. 21.5) uses function template testList to enable the user to manipulate objects of class List. Lines 74 and 78 create List objects for types int and double, respectively. Lines 75 and 79 invoke the testList function template with these List objects.

Member Function insertAtFront

Over the next several pages, we discuss each of the member functions of class List in detail. Function insertAtFront (Fig. 21.4, lines 6375) places a new node at the front of the list. The function consists of several steps:

1. Call function getNewNode (line 66), passing it value, which is a constant reference to the node value to be inserted.
2. Function getNewNode (lines 151156) uses operator new to create a new list node and return a pointer to this newly allocated node, which is assigned to newPtr in insertAtFront (line 66).
3. If the list is empty (line 68), then both firstPtr and lastPtr are set to newPtr (line 69).
4. If the list is not empty (line 70), then the node pointed to by newPtr is threaded into the list by copying firstPtr to newPtr->nextPtr (line 72), so that the new node points to what used to be the first node of the list, and copying newPtr to firstPtr (line 73), so that firstPtr now points to the new first node of the list.

Figure 21.6 illustrates function insertAtFront. Part (a) of the figure shows the list and the new node before the insertAtFront operation. The dashed arrows in part (b) illustrate Step 4 of the insertAtFront operation that enables the node containing 12 to become the new list front.

---

Figure 21.6. Operation insertAtFront represented graphically.

 

Member Function insertAtBack

Function insertAtBack (Fig. 21.4, lines 7890) places a new node at the back of the list. The function consists of several steps:

1. Call function getNewNode (line 81), passing it value, which is a constant reference to the node value to be inserted.
2. Function getNewNode (lines 151156) uses operator new to create a new list node and return a pointer to this newly allocated node, which is assigned to newPtr in insertAtBack (line 81).
3. If the list is empty (line 83), then both firstPtr and lastPtr are set to newPtr (line 84).
4. If the list is not empty (line 85), then the node pointed to by newPtr is threaded into the list by copying newPtr into lastPtr->nextPtr (line 87), so that the new node is pointed to by what used to be the last node of the list, and copying newPtr to lastPtr (line 88), so that lastPtr now points to the new last node of the list.

Figure 21.7 illustrates an insertAtBack operation. Part (a) of the figure shows the list and the new node before the operation. The dashed arrows in part (b) illustrate Step 4 of function insertAtBack that enables a new node to be added to the end of a list that is not empty.

Figure 21.7. Operation insertAtBack represented graphically.

(This item is displayed on page 1013 in the print version)

 

Member Function removeFromFront

Function removeFromFront (Fig. 21.4, lines 93111) removes the front node of the list and copies the node value to the reference parameter. The function returns false if an attempt is made to remove a node from an empty list (lines 9697) and returns TRue if the removal is successful. The function consists of several steps:

---

1. Assign tempPtr the address to which firstPtr points (line 100). Eventually, tempPtr will be used to delete the node being removed.
2. If firstPtr is equal to lastPtr (line 102), i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to zero (line 103) to dethread that node from the list (leaving the list empty).
3. If the list has more than one node prior to removal, then leave lastPtr as is and set firstPtr to firstPtr->nextPtr (line 105); i.e., modify firstPtr to point to what was the second node prior to removal (and is now the new first node).
4. After all these pointer manipulations are complete, copy to reference parameter value the data member of the node being removed (line 107).
5. Now delete the node pointed to by tempPtr (line 108).
6. Return true, indicating successful removal (line 109).

Figure 21.8 illustrates function removeFromFront. Part (a) illustrates the list before the removal operation. Part (b) shows the actual pointer manipulations for removing the front node from a nonempty list.

Figure 21.8. Operation removeFromFront represented graphically.

(This item is displayed on page 1014 in the print version)

 

Member Function removeFromBack

Function removeFromBack (Fig. 21.4, lines 114141) removes the back node of the list and copies the node value to the reference parameter. The function returns false if an attempt is made to remove a node from an empty list (lines 117118) and returns true if the removal is successful. The function consists of several steps:

---

1. Assign to tempPtr the address to which lastPtr points (line 121). Eventually, tempPtr will be used to delete the node being removed.
2. If firstPtr is equal to lastPtr (line 123), i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to zero (line 124) to dethread that node from the list (leaving the list empty).
3. If the list has more than one node prior to removal, then assign currentPtr the address to which firstPtr points (line 127) to prepare to "walk the list."
4. Now "walk the list" with currentPtr until it points to the node before the last node. This node will become the last node after the remove operation completes. This is done with a while loop (lines 130131) that keeps replacing currentPtr by currentPtr->nextPtr, while currentPtr->nextPtr is not lastPtr.
5. Assign lastPtr to the address to which currentPtr points (line 133) to dethread the back node from the list.
6. Set currentPtr->nextPtr to zero (line 134) in the new last node of the list.
7. After all the pointer manipulations are complete, copy to reference parameter value the data member of the node being removed (line 137).
8. Now delete the node pointed to by tempPtr (line 138).
9. Return true (line 139), indicating successful removal.

Figure 21.9 illustrates removeFromBack. Part (a) of the figure illustrates the list before the removal operation. Part (b) of the figure shows the actual pointer manipulations.

Figure 21.9. Operation removeFromBack represented graphically.

(This item is displayed on page 1015 in the print version)

 

Member Function print

Function print (lines 159179) first determines whether the list is empty (line 162). If so, it prints "The list is empty" and returns (lines 164165). Otherwise, it iterates through the list and outputs the value in each node. The function initializes currentPtr as a copy of firstPtr (line 168), then prints the string "The list is: " (line 170). While currentPtr is not null (line 172), currentPtr->data is printed (line 174) and currentPtr is assigned the value of currentPtr->nextPtr (line 175). Note that if the link in the last node of the list is not null, the printing algorithm will erroneously print past the end of the list. The printing algorithm is identical for linked lists, stacks and queues (because we base each of these data structures on the same linked list infrastructure).

---

Linear and Circular Singly Linked and Doubly Linked Lists

The kind of linked list we have been discussing is a singly linked listthe list begins with a pointer to the first node, and each node contains a pointer to the next node "in sequence." This list terminates with a node whose pointer member has the value 0. A singly linked list may be traversed in only one direction.

A circular, singly linked list (Fig. 21.10) begins with a pointer to the first node, and each node contains a pointer to the next node. The "last node" does not contain a 0 pointer; rather, the pointer in the last node points back to the first node, thus closing the "circle."

Figure 21.10. Circular, singly linked list.

---

A doubly linked list (Fig. 21.11) allows traversals both forward and backward. Such a list is often implemented with two "start pointers"one that points to the first element of the list to allow front-to-back traversal of the list and one that points to the last element to allow back-to-front traversal. Each node has both a forward pointer to the next node in the list in the forward direction and a backward pointer to the next node in the list in the backward direction. If your list contains an alphabetized telephone directory, for example, a search for someone whose name begins with a letter near the front of the alphabet might begin from the front of the list. Searching for someone whose name begins with a letter near the end of the alphabet might begin from the back of the list.

Figure 21.11. Doubly linked list.

In a circular, doubly linked list (Fig. 21.12), the forward pointer of the last node points to the first node, and the backward pointer of the first node points to the last node, thus closing the "circle."

Figure 21.12. Circular, doubly linked list.