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. A program accesses a linked list via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node. By convention, the link reference in the last node of a list is set to null to mark the end of the list. Data is stored in a linked list dynamicallythat is, each node is created as necessary. A node can contain data of any type, including references to objects of other classes. Stacks and queues are also linear data structuresin fact, they 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. Unlike a linked list, the size of a conventional C# array cannot be altered, because the array size is fixed at creation time. Conventional arrays can become full, but linked lists become full only when the system has insufficient memory to satisfy dynamic memory allocation requests.

Performance Tip 25 1

An array can be declared to contain more elements than the number of items expected, possibly wasting memory. Linked lists provide better memory utilization in these situations, because they can grow and shrink at execution time.

Performance Tip 25 2

After locating the insertion point for a new item in a sorted linked list, inserting an element in the list is fastonly two references have to be modified. All existing nodes remain at their current locations in memory.

Programmers can maintain linked lists in sorted order simply by inserting each new element at the proper point in the list (locating the proper insertion point does take time). They do not need to move existing list elements.

Performance Tip 25 3

The elements of an array are stored contiguously in memory to allow immediate access to any array elementthe address of any element can be calculated directly from its index. Linked lists do not afford such immediate access to their elementsan element can be accessed only by traversing the list from the front.

Normally linked-list nodes are not stored contiguously in memory. Rather, the nodes are logically contiguous. Figure 25.3 illustrates a linked list with several nodes.

Figure 25.3. Linked list graphical representation.

Performance Tip 25 4

Using linked data structures and dynamic memory allocation (instead of arrays) for data structures that grow and shrink at execution time can save memory. Keep in mind, however, that reference links occupy space, and dynamic memory allocation incurs the overhead of method calls.

 

Linked List Implementation

The program of Figs. 25.4 and 25.5 uses an object of class List to manipulate a list of miscellaneous object types. The Main method of class ListTest (Fig. 25.5) creates a list of objects, inserts objects at the beginning of the list using List method InsertAtFront, inserts objects at the end of the list using List method InsertAtBack, deletes objects from the front of the list using List method RemoveFromFront and deletes objects from the end of the list using List method RemoveFromBack. After each insertion and deletion operation, the program invokes List method Print to display the current list contents. If an attempt is made to remove an item from an empty list, an EmptyListException occurs. A detailed discussion of the program follows.

Figure 25.4. ListNode, List and EmptyListException classes.

(This item is displayed on pages 1327 - 1330 in the print version)

 1 // Fig. 25.4: LinkedListLibrary.cs
 2 // Class ListNode and class List declarations.
 3 using System;
 4
 5 namespace LinkedListLibrary
 6 {
 7 // class to represent one node in a list
 8 class ListNode
 9 {
10 private object data; // stores data for this node 
11 private ListNode next; // stores a reference to the next node
12
13 // constructor to create ListNode that refers to dataValue
14 // and is last node in list
15 public ListNode( object dataValue )
16 : this( dataValue, null )
17 {
18 } // end default constructor
19
20 // constructor to create ListNode that refers to dataValue
21 // and refers to next ListNode in List
22 public ListNode( object dataValue, ListNode nextNode )
23 {
24 data = dataValue;
25 next = nextNode;
26 } // end constructor
27
28 // property Next
29 public ListNode Next
30 {
31 get
32 {
33 return next;
34 } // end get
35 set
36 {
37 next = value;
38 } // end set
39 } // end property Next

40 41 // property Data 42 public object Data 43 { 44 get 45 { 46 return data; 47 } // end get 48 } // end property Data 49 } // end class ListNode 50 51 // class List declaration 52 public class List 53 { 54 private ListNode firstNode; 55 private ListNode lastNode; 56 private string name; // string like "list" to display 57 58 // construct empty List with specified name 59 public List( string listName ) 60 { 61 name = listName; 62 firstNode = lastNode = null; 63 } // end constructor 64 65 // construct empty List with "list" as its name 66 public List() 67 : this( "list" ) 68 { 69 } // end constructor default 70 71 // Insert object at front of List. If List is empty, 72 // firstNode and lastNode will refer to same object. 73 // Otherwise, firstNode refers to new node. 74 public void InsertAtFront( object insertItem ) 75 { 76 if ( IsEmpty() ) 77 firstNode = lastNode = new ListNode( insertItem ); 78 else 79 firstNode = new ListNode( insertItem, firstNode ); 80 } // end method InsertAtFront 81 82 // Insert object at end of List. If List is empty, 83 // firstNode and lastNode will refer to same object. 84 // Otherwise, lastNode's Next property refers to new node. 85 public void InsertAtBack( object insertItem ) 86 { 87 if ( IsEmpty() ) 88 firstNode = lastNode = new ListNode( insertItem ); 89 else 90 lastNode = lastNode.Next = new ListNode( insertItem ); 91 } // end method InsertAtBack 92 93 // remove first node from List 94 public object RemoveFromFront() 95 { 96 if ( IsEmpty() ) 97 throw new EmptyListException( name ); 98 99 object removeItem = firstNode.Data; // retrieve data 100 101 // reset firstNode and lastNode references 102 if ( firstNode == lastNode ) 103 firstNode = lastNode = null; 104 else 105 firstNode = firstNode.Next; 106 107 return removeItem; // return removed data 108 } // end method RemoveFromFront 109 110 // remove last node from List 111 public object RemoveFromBack() 112 { 113 if ( IsEmpty() ) 114 throw new EmptyListException( name ); 115 116 object removeItem = lastNode.Data; // retrieve data 117 118 // reset firstNode and lastNode references 119 if ( firstNode == lastNode ) 120 firstNode = lastNode = null; 121 else 122 { 123 ListNode current = firstNode; 124 125 // loop while current node is not lastNode 126 while ( current.Next != lastNode ) 127 current = current.Next; // move to next node 128 129 // current is new lastNode 130 lastNode = current; 131 current.Next = null; 132 } // end else 133 134 return removeItem; // return removed data 135 } // end method RemoveFromBack 136 137 // return true if List is empty 138 public bool IsEmpty() 139 { 140 return firstNode == null; 141 } // end method IsEmpty 142 143 // output List contents 144 public void Print() 145 { 146 if ( IsEmpty() ) 147 { 148 Console.WriteLine( "Empty " + name ); 149 return; 150 } // end if 151 152 Console.Write( "The " + name + " is: " ); 153 154 ListNode current = firstNode; 155 156 // output current node data while not at end of list 157 while ( current != null ) 158 { 159 Console.Write( current.Data + " " ); 160 current = current.Next; 161 } // end while 162 163 Console.WriteLine( " " ); 164 } // end method Print 165 } // end class List 166 167 // class EmptyListException declaration 168 public class EmptyListException : ApplicationException 169 { 170 public EmptyListException( string name ) 171 : base( "The " + name + " is empty" ) 172 { 173 } // end constructor 174 } // end class EmptyListException 175 } // end namespace LinkedListLibrary

Figure 25.5. Linked list demonstration.

(This item is displayed on pages 1331 - 1332 in the print version)

 1 // Fig. 25.5: ListTest.cs
 2 // Testing class List.
 3 using System;
 4 using LinkedListLibrary;
 5
 6 // class to test List class functionality
 7 class ListTest
 8 {
 9 static void Main( string[] args )
10 {
11 List list = new List(); // create List container
12
13 // create data to store in List
14 bool aBoolean = true;
15 char aCharacter = '$';
16 int anInteger = 34567;
17 string aString = "hello";
18
19 // use List insert methods 
20 list.InsertAtFront( aBoolean ); 
21 list.Print(); 
22 list.InsertAtFront( aCharacter );
23 list.Print(); 
24 list.InsertAtBack( anInteger ); 
25 list.Print(); 
26 list.InsertAtBack( aString ); 
27 list.Print(); 
28
29 // use List remove methods
30 object removedObject;
31
32 // remove data from list and print after each removal
33 try
34 {
35 removedObject = list.RemoveFromFront();
36 Console.WriteLine( removedObject + " removed" );
37 list.Print();
38
39 removedObject = list.RemoveFromFront();
40 Console.WriteLine( removedObject + " removed" );
41 list.Print();
42

43 removedObject = list.RemoveFromBack(); 44 Console.WriteLine( removedObject + " removed" ); 45 list.Print(); 46 47 removedObject = list.RemoveFromBack(); 48 Console.WriteLine( removedObject + " removed" ); 49 list.Print(); 50 } // end try 51 catch ( EmptyListException emptyListException ) 52 { 53 Console.Error.WriteLine( " " + emptyListException ); 54 } // end catch 55 } // end method Main 56 } // end class ListTest

The list is: True

The list is: $ True

The list is: $ True 34567

The list is: $ True 34567 hello

$ removed
The list is: True 34567 hello

True removed
The list is: 34567 hello

hello removed
The list is: 34567

34567 removed
Empty list

Performance Tip 25 5

Insertion and deletion in a sorted array can be time consumingall the elements following the inserted or deleted element must be shifted appropriately.

The program consists of four classesListNode (Fig. 25.4, lines 849), List (lines 52165), EmptyListException (lines 168174) and ListTest (Fig. 25.5). The classes in Fig. 25.4 create a linked-list library (defined in namespace LinkedListLibrary) that can be reused throughout this chapter. You should place the code of Fig. 25.4 in its own class library project as we described in Section 9.14.

Encapsulated in each List object is a linked list of ListNode objects. Class ListNode (Fig. 25.4, lines 849) contains two instance variablesdata and next. Member data can refer to any object. [Note: Typically, a data structure will contain data of only one type, or data of any type derived from one base type.] In this example, we use data of various types derived from object to demonstrate that our List class can store data of any type. Member next stores a reference to the next ListNode object in the linked list. The ListNode constructors (lines 1518 and 2226) enable us to initialize a ListNode that will be placed at the end of a List or before a specific ListNode in a List, respectively. A List accesses the ListNode member variables via properties Next (lines 2939) and Data (lines 4248), respectively.

Class List (lines 52165) contains private instance variables firstNode (a reference to the first ListNode in a List) and lastNode (a reference to the last ListNode in a List). The constructors (lines 5963 and 6669) initialize both references to null and enable us to specify the List's name for output purposes. InsertAtFront (lines 7480), InsertAtBack (lines 8591), RemoveFromFront (lines 94108) and RemoveFromBack (lines 111135) are the primary methods of class List. Method IsEmpty (lines 138141) 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 144164) displays the list's contents. A detailed discussion of class List's methods follows Fig. 25.5.

Class EmptyListException (lines 168174) defines an exception class that we use to indicate illegal operations on an empty List.

Class ListTest (Fig. 25.5) uses the linked-list library to create and manipulate a linked list. [Note: In the project containing Fig. 25.5, you must add a reference to the class library containing the classes in Fig. 25.4. If you use our existing example, you may need to update this reference.] Line 11 creates a new List object and assigns it to variable list. Lines 1417 create data to add to the list. Lines 2027 use List insertion methods to insert these values and use List method Print to output the contents of list after each insertion. Note that the values of the simple-type variables are implicitly boxed in lines 20, 22 and 24 where object references are expected. The code inside the TRy block (lines 3350) removes objects via List deletion methods, outputs each removed object and outputs list after every deletion. If there is an attempt to remove an object from an empty list, the catch at lines 5154 catches the EmptyListException and displays an error message.

Method InsertAtFront

Over the next several pages, we discuss each of the methods of class List in detail. Method InsertAtFront (Fig. 25.4, lines 7480) places a new node at the front of the list. The method consists of three steps:

1.	Call IsEmpty to determine whether the list is empty (line 76).
2.	If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (line 77). The ListNode constructor at lines 1518 of Fig. 25.4 calls the ListNode constructor at lines 2226, which sets instance variable data to refer to the object passed as the first argument and sets the next reference to null.
3.	If the list is not empty, the new node is "linked" into the list by setting firstNode to refer to a new ListNode object initialized with insertItem and firstNode (line 79). When the ListNode constructor (lines 2226) executes, it sets instance variable data to refer to the object passed as the first argument and performs the insertion by setting the next reference to the ListNode passed as the second argument.

In Fig. 25.6, part (a) shows a list and a new node during the InsertAtFront operation and before the new node is linked into the list. The dashed lines and arrows in part (b) illustrate Step 3 of the InsertAtFront operation, which enables the node containing 12 to become the new list front.

Figure 25.6. InsertAtFront operation.

(a)

(b)

 

Method InsertAtBack

Method InsertAtBack (Fig. 25.4, lines 8591) places a new node at the back of the list. The method consists of three steps:

1.	Call IsEmpty to determine whether the list is empty (line 87).
2.	If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (line 88). The ListNode constructor at lines 1518 calls the ListNode constructor at lines 2226, which sets instance variable data to refer to the object passed as the first argument and sets the next reference to null.
3.	If the list is not empty, link the new node into the list by setting lastNode and lastNode.next to refer to a new ListNode object initialized with insertItem (line 90). When the ListNode constructor (lines 1518) executes, it calls the constructor at lines 2226, which sets instance variable data to refer to the object passed as an argument and sets the next reference to null.

In Fig. 25.7, part (a) shows a list and a new node during the InsertAtBack operation; before the new node has been linked into the list. The dashed lines and arrows in part (b) illustrate Step 3 of method InsertAtBack, which enables a new node to be added to the end of a list that is not empty.

Figure 25.7. InsertAtBack operation.

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

(a)

(b)

 

Method RemoveFromFront

Method RemoveFromFront (Fig. 25.4, lines 94108) removes the front node of the list and returns a reference to the removed data. The method throws an EmptyListException (line 97) if the programmer tries to remove a node from an empty list. Otherwise, the method returns a reference to the removed data. After determining that a List is not empty, the method consists of four steps to remove the first node:

1.	Assign firstNode.Data (the data being removed from the list) to variable removeItem (line 99).
2.	If the objects to which firstNode and lastNode refer are the same object, the list has only one element, so the method sets firstNode and lastNode to null (line 103) to remove the node from the list (leaving the list empty).
3.	If the list has more than one node, the method leaves reference lastNode as is and assigns firstNode.Next to firstNode (line 105). Thus, firstNode references the node that was previously the second node in the List.
4.	Return the removeItem reference (line 107).

In Fig. 25.8, part (a) illustrates a list before a removal operation. The dashed lines and arrows in part (b) show the reference manipulations.

Figure 25.8. RemoveFromFront operation.

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

(a)

(b)

 

Method RemoveFromBack

Method RemoveFromBack (Fig. 25.4, lines 111135) removes the last node of a list and returns a reference to the removed data. The method throws an EmptyListException (line 114) if the program attempts to remove a node from an empty list. The method consists of several steps:

1.	Assign lastNode.Data (the data being removed from the list) to variable removeItem (line 116).
2.	If firstNode and lastNode refer to the same object (line 119), the list has only one element, so the method sets firstNode and lastNode to null (line 120) to remove that node from the list (leaving the list empty).
3.	If the list has more than one node, create ListNode variable current and assign it firstNode (line 123).
4.	Now "walk the list" with current until it references the node before the last node. The while loop (lines 126127) assigns current.Next to current as long as current.Next is not equal to lastNode.
5.	After locating the second-to-last node, assign current to lastNode (line 130) to update which node is last in the list.
6.	Set current.Next to null (line 131) to remove the last node from the list and terminate the list at the current node.
7.	Return the removeItem reference (line 134).

In Fig. 25.9, part (a) illustrates a list before a removal operation. The dashed lines and arrows in part (b) show the reference manipulations.

Figure 25.9. RemoveFromBack operation.

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

(a)

(b)

 

Method Print

Method Print (Fig. 25.4, lines 144164) first determines whether the list is empty (line 146). If so, Print displays a string consisting of the string "Empty " and the list's name, then returns control to the calling method. Otherwise, Print outputs the data in the list. The method prints a string consisting of the string "The ", the list's name and the string " is: ". Then line 154 creates ListNode variable current and initializes it with firstNode. While current is not null, there are more items in the list. Therefore, the method displays current.Data (line 159), then assigns current.Next to current (line 160) to move to the next node in the list.

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 reference to the first node, and each node contains a reference to the next node "in sequence." This list terminates with a node whose reference member has the value null. A singly linked list may be traversed in only one direction.

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

Figure 25.10. Circular, singly linked list.

A doubly linked list (Fig. 25.11) allows traversals both forward and backward. Such a list is often implemented with two "start references"one that refers to the first element of the list to allow front-to-back traversal of the list and one that refers to the last element to allow back-to-front traversal. Each node has both a forward reference to the next node in the list and a backward reference to the previous node in the list. 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. A search for someone whose name begins with a letter near the end of the alphabet might begin from the back of the list.

Figure 25.11. Doubly linked list.

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

Figure 25.12. Circular, doubly linked list.