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

 

The list is: -1

The list is: 0 -1

The list is: 0 -1 1

The list is: 0 -1 1 5

0 removed
The list is: -1 1 5

-1 removed
The list is: 1 5

5 removed
The list is: 1

1 removed
Empty list

 

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.