Section 24.4. Linked Lists

24.4. Linked Lists

A linked list is a linear collection (i.e., a sequence) of self-referential class objects called nodes, connected by reference linksthus 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 Nothing to mark the end of the list. Data is stored in a linked list dynamicallythat is, each node is created as necessary. You can declare a node's class to store 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 Visual Basic 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 24.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 24.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). Existing list elements do not need to be moved.

Performance Tip 24.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.

Performance Tip 24.4

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

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

Figure 24.3. Linked list graphical representation.

Performance Tip 24.5

Using linked data structures and dynamic memory allocation (instead of arrays) for data structures that grow and shrink 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 in Fig. 24.4 and 24.5 uses an object of class List to manipulate a list of miscellaneous object types. The Main method of class ListTest (Fig. 24.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 is thrown. A detailed discussion of the program follows.

Figure 24.4. ListNode, List and EmptyListException classes.

  1  ' Fig. 24.4: LinkedListLibrary.vb  2  ' Class ListNode and class List declarations.  3  4  Public Class ListNode  5     Private dataValue As Object ' stores data for this node                6     Private nextNodeReference As ListNode ' stores reference to next node  7  8     ' constructor to create a ListNode that contains data  9     ' and is the last node in the List 10    Public Sub New(ByVal data As Object) 11       MyClass.New(data, Nothing) ' invokes the other constructor 12    End Sub ' New 13 14    ' constructor to create a ListNode that contains data 15    ' and refers to the next ListNode in the List 16    Public Sub New(ByVal data As Object, ByVal nextNode As ListNode) 17       dataValue = data 18       nextNodeReference = nextNode 19    End Sub ' New 20 21     ' property NextNode 22     Public Property NextNode() As ListNode 23        Get 24           Return nextNodeReference 25        End Get 26        Set(ByVal value As ListNode) 27           nextNodeReference = value 28        End Set 29     End Property ' NextNode 30   31     ' property Data 32     Public ReadOnly Property Data() As Object 33        Get 34           Return dataValue 35        End Get 36     End Property ' Data 37  End Class ' ListNode 38 39  ' class List declaration 40  Public Class List 41    Private firstNode As ListNode                          42    Private lastNode As ListNode                           43    Private name As String ' string like "list" to display 44 45    ' construct empty List with "list" as its name 46    Public Sub New() 47       MyClass.New("list") ' invokes the other constructor 48    End Sub ' New 49 50    ' construct empty List with specified name 51    Public Sub New(ByVal listName As String) 52$      name = listName 53       firstNode = Nothing 54       lastNode = Nothing 55    End Sub ' New 56 57    ' Insert object at front of List. If List is empty, firstNode and 58    ' lastNode will refer to same object. Otherwise, firstNode refers 59    ' to new node and the new node refers to the previous first node. 60    Public Sub InsertAtFront(ByVal  insertItem As Object$) 61       If IsEmpty() Then 62          lastNode = New ListNode(insertItem) 63          firstNode = lastNode                64       Else 65          firstNode = New ListNode(insertItem, firstNode) 66       End If 67    End Sub ' InsertAtFront 68 69    ' Insert object at end of List. If List is empty, 70    ' firstNode and lastNode will refer to same object. 71    ' Otherwise, lastNode's NextNode property refers to new node. 72    Public Sub InsertAtBack(ByVal insertItem As Object$) 73       If IsEmpty() Then 74          lastNode = New ListNode(insertItem) 75          firstNode = lastNode                76       Else 77          lastNode.NextNode = New ListNode(insertItem) 78          lastNode = lastNode.NextNode                 79       End If 80    End Sub ' InsertAtBack 81 82    ' remove  first node from List 83    Public Function RemoveFromFront() As Object 84       If IsEmpty() Then                     85          Throw New EmptyListException(name) 86       End If                                87 88       Dim removeItem As Object = firstNode.Data ' retrieve data 89 90       ' reset firstNode and lastNode references 91       If firstNode.Equals(lastNode) Then 92          firstNode = Nothing 93          lastNode = Nothing  94       Else 95          firstNode = firstNode.NextNode 96       End If 97 98       Return removeItem ' return removed data 99     End Function ' RemoveFromFront 100 101    ' remove last node from List 102    Public Function RemoveFromBack() As Object 103       If IsEmpty() Then                     104          Throw New EmptyListException(name) 105       End If                                106 107       Dim removeItem As Object = lastNode.Data ' retrieve data 108 109       ' reset firstNode and lastNode references 110       If firstNode.Equals(lastNode) Then 111          firstNode = Nothing 112          lastNode = Nothing  113       Else 114          Dim current As ListNode = firstNode 115 116          ' loop while current node is not lastNode 117          While Not current.NextNode.Equals(lastNode)       118             current = current.NextNode ' move to next node 119          End While                                         120 121          ' current is new lastNode 122          lastNode = current          123          current.NextNode =  Nothing 124        End If 125 126        Return removeItem ' return removed data 127     End Function ' RemoveFromBack 128 129     ' return True if List is empty 130     Public Function IsEmpty() As Boolean 131        Return firstNode Is Nothing 132     End Function ' IsEmpty 133 134     ' output List contents 135     Public Sub Print() 136        If IsEmpty() Then 137           Console.WriteLine("Empty " & name) 138           Return 139        End If 140 141        Console.Write("The " & name  & " is: " ) 142 143        Dim current As ListNode = firstNode 144 145        ' output current node  data while not at end of list 146        While Not (current Is Nothing) 147           Console.Write(current.Data & " ") 148           current = current.NextNode 149        End While 150 151        Console.WriteLine(vbCrLF) 152     End Sub ' Print 153  End Class ' List 154 155  ' class EmptyListException declaration 156  Public Class EmptyListException :  Inherits ApplicationException 157     Public Sub New(ByVal name As String) 158        MyBase.New("The " & name & " is empty") 159     End Sub ' New 160  End Class' EmptyListException 

Figure 24.5. Linked list demonstration.

  1  ' Fig. 24.5: ListTest.vb  2  ' Testing class List.  3  Imports LinkedListLibrary  4  5  ' class to test List class functionality  6  Module LinkTest  7     Sub Main()  8        Dim list As New List() ' create List container  9 10        ' create   data to store in List 11        Dim aBoolean As Boolean = True 12        Dim aCharacter As Char = "$"c 13        Dim anInteger As Integer = 34567 14        Dim aString As String = "hello" 15 16        ' use List insert methods      17        list.InsertAtFront(aBoolean)   18        list.Print()                   19        list.InsertAtFront(aCharacter) 20        list.Print()                   21        list.InsertAtBack(anInteger)   22        list.Print()                   23        list.InsertAtBack(aString)     24        list.Print()                   25 26        ' use List remove methods 27        Dim removedObject As Object 28 29        ' remove   data from list and print after each removal 30        Try 31           removedObject = list.RemoveFromFront() 32           Console.WriteLine(removedObject & " removed") 33           list.Print() 34 35           removedObject = list.RemoveFromFront() 36           Console.WriteLine(removedObject & " removed") 37           list.Print() 38 39           removedObject = list.RemoveFromBack() 40           Console.WriteLine(removedObject & " removed") 41           list.Print() 42 43           removedObject = list.RemoveFromBack() 44           Console.WriteLine(removedObject & " removed") 45           list.Print() 46        Catch exception As EmptyListException 47           Console.Error.WriteLine( _ 48              vbCrLf & exception.ToString()) 49        End Try 50     End Sub ' Main 51  End Module ' LinkTest 

 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 

The program consists of four classesListNode (Fig. 24.4, lines 4-37), List (lines 40-153), EmptyListException (lines 156-160) and ListTest (Fig. 24.5). The classes in Fig. 24.4 create a linked-list library that can be reused throughout this chapter. You should place the code from Fig. 24.4 in its own class library project as described in Section 9.13. Name the project LinkedListLibrary.

Encapsulated in each List object is a linked list of ListNode objects. Class ListNode (Fig. 24.4, lines 4-37) contains instance variables dataValue and nextNodeReference. Member dataValue 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 nextNodeReference stores a reference to the next ListNode object in the linked list. The ListNode constructors (lines 10-12 and 16-19) 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.

Class List (lines 40-153) 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 46-48 and 51-55) initialize both references to Nothing and enable us to specify the List's name for output purposes. InsertAtFront (lines 60-67), InsertAtBack (lines 72-80), RemoveFromFront (lines 83-99) and RemoveFromBack (lines 102-127) are the primary methods of class List. Method IsEmpty (lines 130-132) is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is Nothing). 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 135-153) displays the list's contents.

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

Class ListTest (Fig. 24.5) uses the linked-list library to create and manipulate a linked list. [Note: In the project containing Fig. 24.5, you must add a reference to the class library containing the classes in Fig. 24.4. If you use our existing example, you may need to update this reference.] Line 8 creates a new Listobject and assigns it to variable list.

Lines 11-14 create data of various types to add to the list. Lines 17-24 use the List insertion methods to insert these values and use List method Print to output the contents of the list object after each insertion. Note that the values of the primitive-type variables are implicitly boxed in lines 17, 19 and 21 where Object references are expected. The code inside the try block (lines 30-45) removes objects via List deletion methods, outputs each removed object and displays the list after every deletion. If there is an attempt to remove an object from an empty list, the Catch at lines 46-48 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. 24.4, lines 60-67) 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 61).
2.	If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (lines 62-63). The ListNode constructor in lines 10-12 of Fig. 24.4 calls the ListNode constructor in lines 16-19, which sets instance variable dataValue to refer to the Object passed as the first argument and sets nextNodeReference to Nothing.
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 65). The ListNode constructor (lines 16-19) sets instance variable dataValue to refer to the Object passed as the first argument, and performs the insertion by setting nextNodeReference to the ListNode passed as the second argument.

In Fig. 24.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 24.6. InsertAtFront operation.

(a)

(b)

Method InsertAtBack

Method InsertAtBack (Fig. 24.4, lines 72-80) 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 73).
2.	If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (lines 74-75). The ListNode constructor in lines 10-12 calls the ListNode constructor in lines 16-19, which sets instance variable dataValue to refer to the Object passed as the first argument and sets nextNodeReference to Nothing.
3.	If the list is not empty, link the new node into the list by setting lastNode and lastNode.NextNode to refer to a new ListNode object initialized with insertItem (line 77). The ListNode constructor (lines 10-12) calls the constructor in lines 16-19, which sets instance variable dataValue to refer to the Object passed as an argument and sets the nextNodeReference reference to Nothing.

In Fig. 24.7, part (a) shows a list and a new node during the InsertAtBack operation and 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 24.7. InsertAtBack operation.

(a)

(b)

Method RemoveFromFront

Method RemoveFromFront (Fig. 24.4, lines 83-99) removes the front node of the list and returns a reference to the removed data. The method throws an EmptyListException (line 85) if an attempt is made 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 88).
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 Nothing (lines 92-93) 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.NextNode to firstNode (line 95). Thus, firstNode references the node that was previously the second node in the List.
4.	Return the removeItem reference (line 98).

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

Figure 24.8. RemoveFromFront operation.

(b)

Method RemoveFromBack

Method RemoveFromBack (Fig. 24.4, lines 102-127) removes the last node of a list and returns a reference to the removed data. The method throws an EmptyListException (line 104) 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 107).
2.	If firstNode and lastNode refer to the same object (line 110), the list has only one element, so the method sets firstNode and lastNode to Nothing (lines 111-112) 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 114).
4.	Now "walk the list" with current until it references the node before the last node. The While loop (lines 117-119) assigns current.NextNode to current as long as current.NextNode is not equal to lastNode.
5.	After locating the second-to-last node, assign current to lastNode (line 122) to update which node is last in the list.
6.	Set current.NextNode to Nothing (line 123) to remove the last node from the list and terminate the list at the current node.
7.	Return the removeItem reference (line 126).

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

Figure 24.9. RemoveFromBack operation.

(a)

(b)

Method Print

Method Print (Fig. 24.4, lines 135-152) first determines whether the list is empty (line 136). If so, Print displays a String consisting of "Empty" and the list's name, then terminates. Otherwise, Print outputs the data in the list. The method prints a String consisting of "The", the list's name and "is:". Then line 143 creates ListNode variable current and initializes it with firstNode. While current is not Nothing, there are more items in the list. Therefore, the method displays current.Data (line 147), then assigns current.NextNode to current (line 148) 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 Nothing. A singly linked list may be traversed in only one direction.

A circular, singly linked list (Fig. 24.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 Nothing reference. Instead the reference in the last node points back to the first node, thus closing the "circle."

Figure 24.10. Circular, singly linked list.

A doubly linked list (Fig. 24.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 24.11. Doubly linked list.

In a circular, doubly linked list (Fig. 24.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 24.12. Circular, doubly linked list.