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.

Related

Категории