19.3 Linked Lists

A linked list is a linear collection of self-referential class objects, called nodes, connected by pointer links—hence, the term “linked” list. A linked list is accessed via a pointer to the list’s first node. 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 nullptr to mark the end of the list. Data is stored in a linked list dynamically—each node is created and destroyed 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 process them polymorphically using virtual function calls. Stacks and queues are also linear data structures and, as we’ll see, can be viewed as constrained versions of linked lists. Trees are nonlinear data structures.

Linked lists provide several advantages over array objects and built-in arrays. 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 an array object or built-in array, however, cannot be altered, because the array size is fixed at compile time. An array object or built-in array can become full. Linked lists become full only when the system has insufficient memory to satisfy additional dynamic storage allocation requests.

Performance Tip 19.1

An array object or built-in 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 can grow and shrink as necessary at runtime. Class template vector (Section 7.10) 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. Pointers merely need to be updated to point to the correct node.

Performance Tip 19.2

Insertion and deletion in a sorted array object or built-in array can be time consuming—all 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 19.3

The elements of an array object or built-in array are stored contiguously in memory. This allows immediate access to any element, because an element’s address can be calculated directly based on its position relative to the beginning of the array object or built-in array. Linked lists do not afford such immediate direct access to their elements, so accessing individual elements can be considerably more expensive. 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, if you have a pointer to the insertion location, it’s typically more efficient to insert an item in a sorted linked list than a sorted array object or built-in array.

Linked-list nodes typically are not stored contiguously in memory, but logically they appear to be contiguous. Figure 19.2 illustrates a linked list with several nodes.

Fig. 19.2 A graphical representation of a list.

Performance Tip 19.4

Using dynamic memory allocation for data structures that grow and shrink at execution time can save memory.

19.3.1 Testing Our Linked List Implementation

The program of Figs. 19.3–19.5 uses a List class template to manipulate a list of integer values and a list of floating-point values. The driver program (Fig. 19.3) has five options:

  • insert a value at the beginning of the List

  • insert a value at the end of the List

  • delete a value from the beginning of the List

  • delete a value from the end of the List

  • end the List processing

The linked list implementation we present here does not allow insertions and deletions anywhere in the linked list. We ask you to implement these operations in Exercise 19.25. Exercise 19.20 asks you to implement a recursive function that prints a linked list backwards, and Exercise 19.21 asks you to implement a recursive function that searches a linked list for a particular data item.

In Fig. 19.3, Lines 66 and 70 create List objects for types int and double, respectively. Lines 67 and 71 invoke the testList function template to manipulate objects.




Fig. 19.3 Manipulating a linked list.

Alternate View 

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

";
62   }
63
64   int main() {
65      // test List of int values
66      List<int> integerList;
67      testList(integerList, "integer");
68
69      // test List of double values
70      List<double> doubleList;
71      testList(doubleList, "double");
72   }


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

19.3.2 Class Template ListNode

Figure 19.3 uses class templates ListNode (Fig. 19.4) and List (Fig. 19.5). Encapsulated in each List object is a linked list of ListNode objects. Class template ListNode (Fig. 19.4) contains private members data and nextPtr (lines 20–21), a constructor (lines 15–16) to initialize these members and function getData (line 18) 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. Line 12 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. We do this for performance and because these two classes are tightly coupled—only class template List manipulates objects of class template ListNode. 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). To use the type name List<NODETYPE> in line 12, the compiler needs to know that class template List exists. Line 8 is a so-called forward declaration of class template List. A forward declaration tells the compiler that a type exists, even if it has not yet been defined.

Error-Prevention Tip 19.1

Assign nullptr to the link member of a new node. Pointers must be initialized before they’re used.

Fig. 19.4 ListNode class-template definition.

Alternate View 

 1   // Fig. 19.4: ListNode.h
 2   // ListNode class-template 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 12
 8   template<typename NODETYPE> class List;                              
 9
10   template<typename NODETYPE>
11   class ListNode {
12      friend class List<NODETYPE>; // make List a friend
13
14   public:
15      explicit ListNode(const NODETYPE& info) // constructor
16         : data{info}, nextPtr{nullptr} {}
17
18      NODETYPE getData() const {return data;} // return data in node
19   private:
20      NODETYPE data; // data
21      ListNode<NODETYPE>* nextPtr; // next node in list
22   };
23
24   #endif

19.3.3 Class Template List

Lines 132–133 of the List class template (Fig. 19.5) declare and initialize to nullptr the private data members firstPtr and lastPtr—pointers to the List’s first and last ListNodes. The destructor (lines 13–29) destroys all of the List’s ListNode objects when the List is destroyed. The primary List functions are insertAtFront (lines 32–42), insertAtBack (lines 45–55), removeFromFront (lines 58–76) and removeFromBack (lines 79–105). We discuss each of these after Fig. 19.5.

Function isEmpty (lines 108–110) is a predicate function that determines whether the List is empty. Function print (lines 113–129) displays the List’s contents. Utility function getNewNode (lines 136–138) returns a dynamically allocated ListNode object. This function is called from functions insertAtFront and insertAtBack.



Fig. 19.5 List class-template definition.

Alternate View 

 1    // Fig. 19.5: List.h
 2    // List class-template definition.
 3    #ifndef LIST_H
 4    #define LIST_H
 5
 6    #include <iostream>
 7    #include "ListNode.h" // ListNode class definition
 8
 9    template<typename NODETYPE>
10    class List {
11    public:
12       // destructor
13       ~List() {
14          if (!isEmpty()) { // List is not empty
15             std::cout << "Destroying nodes ...
";
16
17             ListNode<NODETYPE>* currentPtr{firstPtr};
18             ListNode<NODETYPE>* tempPtr{nullptr};
19
20             while (currentPtr != nullptr) { // delete remaining nodes
21                tempPtr = currentPtr;
22                std::cout << tempPtr->data << "
";
23                currentPtr = currentPtr->nextPtr;
24                delete tempPtr;
25             }
26          } 
27
28          std::cout << "All nodes destroyed

";
29       }
30
31       // insert node at front of list
32       void insertAtFront(const NODETYPE& value) {
33          ListNode<NODETYPE>* newPtr{getNewNode(value)}; // new node
34
35          if (isEmpty()) { // List is empty
36             firstPtr = lastPtr = newPtr; // new list has only one node
37          } 
38          else { // List is not empty
39             newPtr->nextPtr = firstPtr; // point new node to old 1st node
40             firstPtr = newPtr; // aim firstPtr at new node
41          }
42       }
43
44       // insert node at back of list
45       void insertAtBack(const NODETYPE& value) {
46          ListNode<NODETYPE>* newPtr{getNewNode(value)}; // new node
47
48          if (isEmpty()) { // List is empty
49             firstPtr = lastPtr = newPtr; // new list has only one node
50          } 
51          else { // List is not empty
52             lastPtr->nextPtr = newPtr; // update previous last node
53             lastPtr = newPtr; // new last node
54          }
55       }
56
57       // delete node from front of list
58       bool removeFromFront(NODETYPE& value){
59          if (isEmpty()) { // List is empty
60             return false; // delete unsuccessful
61          } 
62          else {
63             ListNode<NODETYPE>* tempPtr{firstPtr}; // hold item to delete
64
65             if (firstPtr == lastPtr) {
66                firstPtr = lastPtr = nullptr; // no nodes remain after removal
67             } 
68             else {
69                firstPtr = firstPtr->nextPtr; // point to previous 2nd node
70             } 
71
72             value = tempPtr->data; // return data being removed
73             delete tempPtr; // reclaim previous front node
74             return true; // delete successful
75          }
76       }
77
78       // delete node from back of list
79       bool removeFromBack(NODETYPE& value)  {
80          if (isEmpty()) { // List is empty
81             return false; // delete unsuccessful
82          }
83          else {
84             ListNode<NODETYPE>* tempPtr{lastPtr}; // hold item to delete
85
86             if (firstPtr == lastPtr) { // List has one element
87                firstPtr = lastPtr = nullptr; // no nodes remain after removal
88             }
89             else {
90                ListNode<NODETYPE>* currentPtr{firstPtr};
91
92                // locate second-to-last element
93                while (currentPtr->nextPtr != lastPtr) {
94                   currentPtr = currentPtr->nextPtr; // move to next node
95                }
96
97                lastPtr = currentPtr; // remove last node
98                currentPtr->nextPtr = nullptr; // this is now the last node
99             } 
100
101            value = tempPtr->data; // return value from old last node
102            delete tempPtr; // reclaim former last node
103            return true; // delete successful
104         } 
105      } 
106
107      // is List empty?
108      bool isEmpty() const {
109         return firstPtr == nullptr;
110      }
111
112      // display contents of List
113      void print() const
114         if (isEmpty()) { // List is empty
115            std::cout << "The list is empty

";
116            return;
117         } 
118
119         ListNode<NODETYPE>* currentPtr{firstPtr};
120
121         std::cout << "The list is: ";
122
123         while (currentPtr != nullptr) { // get element data
124            std::cout << currentPtr->data << " ";
125            currentPtr = currentPtr->nextPtr;
126         } 
127
128         std::cout << "

";
129      }
130
131   private:
132      ListNode<NODETYPE>* firstPtr{nullptr}; // pointer to first node
133      ListNode<NODETYPE>* lastPtr{nullptr}; // pointer to last node  
134
135      // utility function to allocate new node
136      ListNode<NODETYPE>* getNewNode(const NODETYPE& value) {
137         return new ListNode<NODETYPE>{value};
138      }
139   };
140
141   #endif

19.3.4 Member Function insertAtFront

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

  1. Call function getNewNode (line 33), passing it value, which is a constant reference to the node value to be inserted.

  2. Function getNewNode (lines 136–138) uses operator new to create a new list node and return a pointer to this newly allocated node, which is used to initialize newPtr in insertAtFront (line 33).

  3. If the list is empty (line 35), firstPtr and lastPtr are set to newPtr (line 36)—i.e., the first and last node are the same node.

  4. If the list is not empty, then the node pointed to by newPtr is threaded into the list by copying firstPtr to newPtr->nextPtr (line 39), so that the new node points to what used to be the first node of the list, and copying newPtr to firstPtr (line 40), so that firstPtr now points to the new first node of the list.

Figure 19.6 illustrates the function insertAtFront’s operation. Part (a) shows the list and the new node before calling insertAtFront. 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.

Fig. 19.6 Operation insertAtFront represented graphically.

19.3.5 Member Function insertAtBack

Function insertAtBack (Fig. 19.5, lines 45–55) places a new node at the back of the list. The function consists of several steps:

  1. Call function getNewNode (line 46), passing it value, which is a constant reference to the node value to be inserted.

  2. Function getNewNode (lines 136–138) uses operator new to create a new list node and return a pointer to this newly allocated node, which is used to initialize newPtr in insertAtBack (line 46).

  3. If the list is empty (line 48), then both firstPtr and lastPtr are set to newPtr (line 49).

  4. If the list is not empty, then the node pointed to by newPtr is threaded into the list by copying newPtr into lastPtr->nextPtr (line 52), 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 53), so that lastPtr now points to the new last node of the list.

Figure 19.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’s not empty.

19.3.6 Member Function removeFromFront

Function removeFromFront (Fig. 19.5, lines 58–76) 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 59–61) and returns true if the removal is successful. The function consists of several steps:

  1. Initialize tempPtr with the address to which firstPtr points (line 63). Eventually, tempPtr will be used to delete the node being removed.

    Fig. 19.7 Operation insertAtBack represented graphically.

  2. If firstPtr is equal to lastPtr (line 65), i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to nullptr (line 66) 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 69; 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 72).

  5. Now delete the node pointed to by tempPtr (line 73).

  6. Return true, indicating successful removal (line 74).

Figure 19.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.

19.3.7 Member Function removeFromBack

Function removeFromBack (Fig. 19.5, lines 79–105) 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 80–82) and returns true if the removal is successful. The function consists of several steps:

  1. Initialize tempPtr with the address to which lastPtr points (line 84). Eventually, tempPtr will be used to delete the node being removed.

  2. If firstPtr is equal to lastPtr (line 86), i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to nullptr (line 87) to dethread that node from the list (leaving the list empty).

    Fig. 19.8 Operation removeFromFront represented graphically.

  3. If the list has more than one node prior to removal, then initialize currentPtr with the address to which firstPtr points (line 90) 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 93–95) that keeps replacing currentPtr by currentPtr->nextPtr, while currentPtr->nextPtr is not lastPtr.

  5. Assign lastPtr to the address to which currentPtr points (line 97) to dethread the back node from the list.

  6. Set currentPtr->nextPtr to nullptr (line 98) 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 101).

  8. Now delete the node pointed to by tempPtr (line 102).

  9. Return true (line 103), indicating successful removal.

Figure 19.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.

19.3.8 Member Function print

Function print (Fig. 19.5, lines 113–129) first determines whether the list is empty (line 114). If so, it prints "The list is empty" and returns (lines 115–116). Otherwise, it outputs the value in each node. The function initializes currentPtr with firstPtr (line 119), then prints the string "The list is: " (line 121). While currentPtr is not nullptr (line 123), currentPtr->data is printed (line 124) and currentPtr is assigned the value of currentPtr->nextPtr

Fig. 19.9 Operation removeFromBack represented graphically.

(line 125). Note that if the link in the last node of the list does not have the value nullptr, the printing algorithm will erroneously attempt to print past the end of the list. Our printing algorithm here is identical for linked lists, stacks and queues (because we base each of these data structures on the same linked list infrastructure).

19.3.9 Circular Linked Lists and Double Linked Lists

The kind of linked list we’ve been discussing is a singly linked list—the 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 nullptr. A singly linked list may be traversed in only one direction.

A circular, singly linked list (Fig. 19.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 nullptr; rather, the pointer in the last node points back to the first node, thus closing the “circle.”

Fig. 19.10 Circular, singly linked list.

A doubly linked list (Fig. 19.11)—such as the Standard Library list class template—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 best begin from the front of the list. Searching for someone whose name begins with a letter near the end of the alphabet might best begin from the back of the list.

Fig. 19.11 Doubly linked list.

In a circular, doubly linked list (Fig. 19.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.”

Fig. 19.12 Circular, doubly linked list.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset