Linked Lists
A linked list is a linear collection (i.e., a sequence) of self-referential-class objects, called nodes, connected by reference linkshence, the term "linked" list. Typically, a program accesses a linked list via a reference to the first node in the list. The program accesses each subsequent node via the link reference stored in the previous node. By convention, the link reference in the last node is set to null to mark the end of the list. Data is stored in a linked list dynamicallythe program creates each node as necessary. A node can contain data of any type, including references to objects of other classes. Stacks and queues are also linear data structures and, as we will see, are constrained versions of linked lists. Trees are non-linear 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 in the data structure is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary. The size of a "conventional" Java array, however, cannot be altered, because the array size is fixed at the time the program creates the array. "Conventional" arrays can become full. Linked lists become full only when the system has insufficient memory to satisfy dynamic storage allocation requests. Package java.util contains class LinkedList for implementing and manipulating linked lists that grow and shrink during program execution. We discuss class LinkedList in Chapter 19.
Performance Tip 17.1
|
An array can be declared to contain more elements than the number of items expected, but this wastes memory. Linked lists provide better memory utilization in these situations. Linked lists allow the program to adapt to storage needs at runtime. |
Performance Tip 17.2
|
Insertion into a linked list is fastonly two references have to be modified (after locating the insertion point). All existing node objects remain at their current locations in memory. |
Linked lists can be maintained in sorted order simply by inserting each new element at the proper point in the list. (It does, of course, take time to locate the proper insertion point.) Existing list elements do not need to be moved.
Performance Tip 17.3
|
Insertion and deletion in a sorted array can be time consumingall the elements following the inserted or deleted element must be shifted appropriately. |
Linked list nodes normally are not stored contiguously in memory. Rather, they are logically contiguous. Figure 17.2 illustrates a linked list with several nodes. This diagram presents a singly linked listeach node contains one reference to the next node in the list. Often, linked lists are implemented as doubly linked listseach node contains a reference to the next node in the list and a reference to the previous node in the list. Java's LinkedList class is a doubly linked list implementation.
Figure 17.2. Linked list graphical representation.
Performance Tip 17.4
|
Normally, the elements of an array are contiguous in memory. This allows immediate access to any array element, because its address can be calculated directly as its offset from the beginning of the array. Linked lists do not afford such immediate access to their elementsan element can be accessed only by traversing the list from the front (or from the back in a doubly linked list). |
The program of Fig. 17.3Fig. 17.5 uses an object of our List class to manipulate a list of miscellaneous objects. The program consists of four classesListNode (Fig. 17.3, lines 637), List (Fig. 17.3, lines 40147), EmptyListException (Fig. 17.4) and ListTest (Fig. 17.5). The List, ListNode and EmptyListException classes are placed in package com.deitel.jhtp6.ch17, so they can be reused throughout this chapter. Encapsulated in each List object is a linked list of ListNode objects. [Note: Many of the classes in this chapter are declared in the package com.deitel.jhtp6.ch17. Each such class should be compiled with the -d command-line option to javac. When compiling the classes that are not in this package and when running the programs, be sure to use the - classpath option to javac and java, respectively.]
Figure 17.3. ListNode and List class declarations.
(This item is displayed on pages 823 - 826 in the print version)
|
1 // Fig. 17.3: List.java 2 // ListNode and List class definitions. 3 package com.deitel.jhtp6.ch17; 4 5 // class to represent one node in a list 6 class ListNode 7 { 8 // package access members; List can access these directly 9 Object data; 10 ListNode nextNode; 11 12 // constructor creates a ListNode that refers to object 13 ListNode( Object object ) 14 { 15 this ( object, null ); 16 } // end ListNode one-argument constructor 17 18 // constructor creates ListNode that refers to 19 // Object and to next ListNode 20 ListNode( Object object, ListNode node ) 21 { 22 data = object; 23 nextNode = node; 24 } // end ListNode two-argument constructor 25 26 // return reference to data in node 27 Object getObject() 28 { 29 return data; // return Object in this node 30 } // end method getObject 31 32 // return reference to next node in list 33 ListNode getNext() 34 { 35 return nextNode; // get next node 36 } // end method getNext 37 } // end class ListNode 38 39 // class List definition 40 public class List 41 { 42 private ListNode firstNode; 43 private ListNode lastNode; 44 private String name; // string like "list" used in printing 45 46 // constructor creates empty List with "list" as the name 47 public List() 48 { 49 this( "list" ); 50 } // end List no-argument constructor 51 52 // constructor creates an empty List with a name 53 public List( String listName ) 54 { 55 name = listName; 56 firstNode = lastNode = null; 57 } // end List one-argument constructor 58 59 // insert Object at front of List 60 public void insertAtFront( Object insertItem ) 61 { 62 if ( isEmpty() ) // firstNode and lastNode refer to same object 63 firstNode = lastNode = new ListNode( insertItem ); 64 else // firstNode refers to new node 65 firstNode = new ListNode( insertItem, firstNode ); 66 } // end method insertAtFront 67 68 // insert Object at end of List 69 public void insertAtBack( Object insertItem ) 70 { 71 if ( isEmpty() ) // firstNode and lastNode refer to same Object 72 firstNode = lastNode = new ListNode( insertItem ); 73 else // lastNode's nextNode refers to new node 74 lastNode = lastNode.nextNode = new ListNode( insertItem ); 75 } // end method insertAtBack 76 77 // remove first node from List 78 public Object removeFromFront() throws EmptyListException 79 { 80 if ( isEmpty() ) // throw exception if List is empty 81 throw new EmptyListException( name ); 82 83 Object removedItem = firstNode.data; // retrieve data being removed 84 85 // update references firstNode and lastNode 86 if ( firstNode == lastNode ) 87 firstNode = lastNode = null; 88 else 89 firstNode = firstNode.nextNode; 90 91 return removedItem; // return removed node data 92 } // end method removeFromFront 93 94 // remove last node from List 95 public Object removeFromBack() throws EmptyListException 96 { 97 if ( isEmpty() ) // throw exception if List is empty 98 throw new EmptyListException( name ); 99 100 Object removedItem = lastNode.data; // retrieve data being removed 101 102 // update references firstNode and lastNode 103 if ( firstNode == lastNode ) 104 firstNode = lastNode = null; 105 else // locate new last node 106 { 107 ListNode current = firstNode; 108 109 // loop while current node does not refer to lastNode 110 while ( current.nextNode != lastNode ) 111 current = current.nextNode; 112 113 lastNode = current; // current is new lastNode 114 current.nextNode = null; 115 } // end else 116 117 return removedItem; // return removed node data 118 } // end method removeFromBack 119 120 // determine whether list is empty 121 public boolean isEmpty() 122 { 123 return firstNode == null; // return true if List is empty 124 } // end method isEmpty 125 126 // output List contents 127 public void print() 128 { 129 if ( isEmpty() ) 130 { 131 System.out.printf( "Empty %s ", name ); 132 return; 133 } // end if 134 135 System.out.printf( "The %s is: ", name ); 136 ListNode current = firstNode; 137 138 // while not at end of list, output current node's data 139 while ( current != null ) 140 { 141 System.out.printf( "%s ", current.data ); 142 current = current.nextNode; 143 } // end while 144 145 System.out.println( " " ); 146 } // end method print 147 } // end class List |
Figure 17.4. EmptyListException class declaration.
(This item is displayed on page 826 in the print version)
|
1 // Fig. 17.4: EmptyListException.java 2 // Class EmptyListException definition. 3 package com.deitel.jhtp6.ch17; 4 5 public class EmptyListException extends RuntimeException 6 { 7 // no-argument constructor 8 public EmptyListException() 9 { 10 this( "List" ); // call other EmptyListException constructor 11 } // end EmptyListException no-argument constructor 12 13 // one-argument constructor 14 public EmptyListException( String name ) 15 { 16 super( name + " is empty" ); // call superclass constructor 17 } // end EmptyListException one-argument constructor 18 } // end class EmptyListException |
Figure 17.5. Linked list manipulations.
(This item is displayed on pages 827 - 828 in the print version)
|
1 // Fig. 17.5: ListTest.java 2 // ListTest class to demonstrate List capabilities. 3 import com.deitel.jhtp6.ch17.List; 4 import com.deitel.jhtp6.ch17.EmptyListException; 5 6 public class ListTest 7 { 8 public static void main( String args[] ) 9 { 10 List list = new List(); // create the List container 11 12 // insert integers in list 13 list.insertAtFront( -1 ); 14 list.print(); 15 list.insertAtFront( 0 ); 16 list.print(); 17 list.insertAtBack( 1 ); 18 list.print(); 19 list.insertAtBack( 5 ); 20 list.print(); 21 22 // remove objects from list; print after each removal 23 try 24 { 25 Object removedObject = list.removeFromFront(); 26 System.out.printf( "%s removed ", removedObject ); 27 list.print(); 28 29 removedObject = list.removeFromFront(); 30 System.out.printf( "%s removed ", removedObject ); 31 list.print(); 32 33 removedObject = list.removeFromBack(); 34 System.out.printf( "%s removed ", removedObject ); 35 list.print(); 36 37 removedObject = list.removeFromBack(); 38 System.out.printf( "%s removed ", removedObject ); 39 list.print(); 40 } // end try 41 catch ( EmptyListException emptyListException ) 42 { 43 emptyListException.printStackTrace(); 44 } // end catch 45 } // end main 46 } // end class ListTest
|
Class ListNode (Fig. 17.3, lines 637) declares package-access fields data and nextNode. The data field is an Object reference, so it can refer to any object. ListNode member nextNode stores a reference to the next ListNode object in the linked list (or null if the node is the last one in the list).
Lines 4243 of class List (Fig. 17.3, lines 40147) declare references to the first and last ListNodes in a List (firstNode and lastNode, respectively). The constructors (lines 4750 and 5357) initialize both references to null. The most important methods of class List are insertAtFront (lines 6066), insertAtBack (lines 6975), removeFromFront (lines 7892) and removeFromBack (lines 95118). Method isEmpty (lines 121124) is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is null). Predicate methods typically test a condition and do not modify the object on which they are called. If the list is empty, method isEmpty returns TRue; otherwise, it returns false. Method print (lines 127146) displays the list's contents. A detailed discussion of List's methods follows Fig. 17.5.
Method main of class ListTest (Fig. 17.5) inserts objects at the beginning of the list using method insertAtFront, inserts objects at the end of the list using method insertAtBack, deletes objects from the front of the list using method removeFromFront and deletes objects from the end of the list using method removeFromBack. After each insert and remove operation, ListTest calls List method print to display the current list contents. If an attempt is made to remove an item from an empty list, an EmptyListException (Fig. 17.4) is thrown, so the method calls to removeFromFront and removeFromBack are placed in a try block that is followed by an appropriate exception handler. Notice in lines 13, 15, 17 and 19 that the applications passes literal primitive int values to methods insertAtFront and insertAtBack, even though each of these methods was declared with a parameter of type Object (Fig. 17.3, lines 60 and 69). In this case, the JVM autoboxes each literal value in an Integer object and that object is actually inserted into the list. This, of course, is allowed because Object is an indirect superclass of Integer.
Now we discuss each method of class List (Fig. 17.3) in detail and provide diagrams showing the reference manipulations performed by methods insertAtFront, insertAtBack, removeFromFront and removeFromBack. Method insertAtFront (lines 6066 of Fig. 17.3) places a new node at the front of the list. The steps are:
|
1. |
Call isEmpty to determine whether the list is empty (line 62).
|
|
2. |
If the list is empty, assign firstNode and lastNode to the new ListNode that was initialized with insertItem (line 63). The ListNode constructor at lines 1316 calls the ListNode constructor at lines 2024 to set instance variable data to refer to the insertItem passed as an argument and to set reference nextNode to null, because this is the first and last node in the list.
|
|
3. |
If the list is not empty, the new node is "linked" into the list by setting firstNode to a new ListNode object and initializing that object with insertItem and firstNode (line 65). When the ListNode constructor (lines 2024) executes, it sets instance variable data to refer to the insertItem passed as an argument and performs the insertion by setting the nextNode reference of the new node to the ListNode passed as an argument, which previously was the first node.
|
In Fig. 17.6, part (a) shows a list and a new node during the insertAtFront operation and before the program links the new node into the list. The dotted arrows in part (b) illustrate Step 3 of the insertAtFront operation that enables the node containing 12 to become the new first node in the list.
Figure 17.6. Graphical representation of operation insertAtFront.
(This item is displayed on page 829 in the print version)
Method insertAtBack (lines 6975 of Fig. 17.3) places a new node at the back of the list. The steps are:
|
1. |
Call isEmpty to determine whether the list is empty (line 71).
|
|
2. |
If the list is empty, assign firstNode and lastNode to the new ListNode that was initialized with insertItem (line 72). The ListNode constructor at lines 1316 calls the constructor at lines 2024 to set instance variable data to refer to the insertItem passed as an argument and to set reference nextNode to null.
|
|
3. |
If the list is not empty, line 74 links the new node into the list by assigning to lastNode and lastNode.nextNode the reference to the new ListNode that was initialized with insertItem. ListNode's constructor (lines 1316), sets instance variable data to refer to the insertItem passed as an argument and sets reference nextNode to null, because this is the last node in the list.
|
In Fig. 17.7, part (a) shows a list and a new node during the insertAtBack operation and before the program links the new node into the list. The dotted arrows in part (b) illustrate Step 3 of method insertAtBack, which adds the new node to the end of a list that is not empty.
Figure 17.7. Graphical representation of operation insertAtBack.
Method removeFromFront (lines 7892 of Fig. 17.3) removes the first node of the list and returns a reference to the removed data. The method throws an EmptyListException (lines 8081) if the list is empty when the program calls this method. Otherwise, the method returns a reference to the removed data. The steps are:
|
1. |
Assign firstNode.data (the data being removed from the list) to reference removedItem (line 83).
|
|
2. |
If firstNode and lastNode refer to the same object (line 86), the list has only one element at this time. So, the method sets firstNode and lastNode to null (line 87) to remove the node from the list (leaving the list empty).
|
|
3. |
If the list has more than one node, then the method leaves reference lastNode as is and assigns the value of firstNode.nextNode to firstNode (line 89). Thus, firstNode references the node that was previously the second node in the list.
|
|
4. |
Return the removedItem reference (line 91).
|
In Fig. 17.8, part (a) illustrates the list before the removal operation. The dashed lines and arrows in part (b) show the reference manipulations.
Figure 17.8. Graphical representation of operation removeFromFront.
Method removeFromBack (lines 95118 of Fig. 17.3) removes the last node of a list and returns a reference to the removed data. The method throws an EmptyListException (lines 9798) if the list is empty when the program calls this method. The steps are:
|
1. |
Assign lastNode.data (the data being removed from the list) to removedItem (line 100).
|
|
2. |
If the firstNode and lastNode refer to the same object (line 103), the list has only one element at this time. So, line 104 sets firstNode and lastNode to null to remove that node from the list (leaving the list empty).
|
|
3. |
If the list has more than one node, create the ListNode reference current and assign it firstNode (line 107).
|
|
4. |
Now "walk the list" with current until it references the node before the last node. The while loop (lines 110111) assigns current.nextNode to current as long as current.nextNode (the next node in the list) is not lastNode.
|
|
5. |
After locating the second-to-last node, assign current to lastNode (line 113) to update which node is last in the list.
|
|
6. |
Set the current.nextNode to null (line 114) to remove the last node from the list and terminate the list at the current node.
|
|
7. |
Return the removedItem reference (line 117).
|
In Fig. 17.9, part (a) illustrates the list before the removal operation. The dashed lines and arrows in part (b) show the reference manipulations.
Figure 17.9. Graphical representation of operation removeFromBack.
Method print (lines 127146) first determines whether the list is empty (lines 129133). If so, print displays a message indicating that the list is empty and returns control to the calling method. Otherwise, print outputs the list's data. Line 136 creates ListNode current and initializes it with firstNode. While current is not null, there are more items in the list. Therefore, line 141 outputs a string representation of current.data. Line 142 moves to the next node in the list by assigning the value of reference current.nextNode to current. This printing algorithm is identical for linked lists, stacks and queues.