19.4 Linked Lists

A linked list is a linear collection (i.e., a sequence) of self-referential class objects, called nodes, connected by reference links—hence, 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 dynamically—that 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 structures—in fact, they may 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 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 19.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.

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 19.2

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

Normally linked-list nodes are not stored contiguously in memory. Rather, the nodes are logically contiguous. Figure 19.3 illustrates a linked list with several nodes. Note that the reference lastNode is not required to implement a linked list—it’s an optimization that enables fast access to a linked list’s last element.

Performance Tip 19.3

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.

Fig. 19.3 Linked list graphical representation.

Linked-List Implementation

Figures 19.4–19.5 use an object of our List class to manipulate a list of miscellaneous object types. Class ListTest’s Main method (Fig. 19.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 insert and delete operation, the program invokes List method Display to output 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.

Performance Tip 19.4

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

The program consists of four classes—ListNode (Fig. 19.4, lines 8–27), List (lines 30–161), EmptyListException (lines 164–176) and ListTest (Fig. 19.5). The classes in Fig. 19.4 create a linked-list library (defined in namespace LinkedListLibrary) that can be reused throughout this chapter. You should place the code of Fig. 19.4 in its own class library project, as we described in Section 15.13.

Fig. 19.4 ListNode, List and EmptyListException class declarations.

Alternate View 

 1   // Fig. 19.4: LinkedListLibrary.cs
 2   // ListNode, List and EmptyListException class declarations.
 3   using System;
 4
 5   namespace LinkedListLibrary
 6   {
 7      // class to represent one node in a list
 8      class ListNode
 9   {
10      // automatic read-only property Data
11      public object Data { get; private set; }
12
13      // automatic property Next
14      public ListNode Next { get; set; }
15
16      // constructor to create ListNode that refers to dataValue
17      // and is last node in list
18      public ListNode(object dataValue) : this(dataValue, null) { }
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      }
27   }
28
29   // class List declaration
30   public class List
31   {
32      private ListNode firstNode;                          
33      private ListNode lastNode;                           
34      private string name; // string like "list" to display
35
36      // construct empty List with specified name
37      public List(string listName)
38     {
39        name = listName;
40        firstNode = lastNode = null;
41     }
42
43     // construct empty List with "list" as its name
44     public List() : this("list") { }
45
46     // Insert object at front of List. If List is empty,
47     // firstNode and lastNode will refer to same object.
48     // Otherwise, firstNode refers to new node.
49     public void InsertAtFront(object insertItem)
50     {
51       if (IsEmpty())
52       {
53          firstNode = lastNode = new ListNode(insertItem);
54       }
55       else
56       {
57          firstNode = new ListNode(insertItem, firstNode);
58       }
59     }
60
61     // Insert object at end of List. If List is empty,
62     // firstNode and lastNode will refer to same object.
63     // Otherwise, lastNode's Next property refers to new node.
64     public void InsertAtBack(object insertItem)
65     {
66        if (IsEmpty())
67       {
68          firstNode = lastNode = new ListNode(insertItem);
69       }
70       else
71       {
72          lastNode = lastNode.Next = new ListNode(insertItem);
73       }
74    }
75
76    // remove first node from List
77    public object RemoveFromFront()
78     {
79       if (IsEmpty())
80       {
81          throw new EmptyListException(name);
82       }
83
84       object removeItem = firstNode.Data; // retrieve data
85
86       // reset firstNode and lastNode references
87       if (firstNode == lastNode)
88       {
89          firstNode = lastNode = null;
90       }
91       else
92       {
93         firstNode = firstNode.Next;
94       }
95
96         return removeItem; // return removed data
97       }
98
99       // remove last node from List
100      public object RemoveFromBack()
101      {
102         if (IsEmpty()) 
103         {
104            throw new EmptyListException(name);
105         }
106
107         object removeItem = lastNode.Data; // retrieve data
108
109         // reset firstNode and lastNode references
110         if (firstNode == lastNode)
111         {
112            firstNode = lastNode = null;
113         }
114         else
115         {
116            ListNode current = firstNode;
117
118            // loop while current.Next is not lastNode
119            while (current.Next != lastNode)               
120            {                                              
121               current = current.Next; // move to next node
122            }                                              
123
124            // current is new lastNode
125            lastNode = current;
126            current.Next = null;
127         }
128
129         return removeItem; // return removed data
130      }
131
132      // return true if List is empty
133      public bool IsEmpty()
134      {
135         return firstNode == null;
136      }
137
138      // output List contents
139      public void Display()
140      {
141         if (IsEmpty())
142         {
143            Console.WriteLine($"Empty {name}");
144         }
145         else
146         {
147            Console.Write($"The {name} is: ");
148
149            ListNode current = firstNode;
150
151            // output current node data while not at end of list
152            while (current != null)              
153            {                                    
154               Console.Write($"{current.Data} ");
155               current = current.Next;           
156            }                                    
157
158            Console.WriteLine("
");
159         }
160      }
161   }
162
163   // class EmptyListException declaration
164   public class EmptyListException : Exception
165   {
166      // parameterless constructor
167      public EmptyListException() : base("The list is empty") { }
168
169      // one-parameter constructor
170      public EmptyListException(string name)
171         : base($"The {name} is empty") { }
172
173      // two-parameter constructor
174      public EmptyListException(string exception, Exception inner)
175         : base(exception, inner) { }
176     }
177   }

Class ListNode

Encapsulated in each List is a linked list of ListNode objects. Class ListNode (Fig. 19.4, lines 8–27) contains two properties—Data and Next. 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—normally a data structure’s elements are all of the same type. Next stores a reference to the next ListNode object in the linked list. The ListNode constructors (lines 18 and 22–26) 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. ListNode is not a public class, because only class List needs to manipulate ListNodes.

Class List

Class List (lines 30–161) contains private instance variables firstNode and lastNode—references to the first and last ListNodes in a List, respectively. The constructors (lines 37– 41 and 44) initialize both references to null and enable us to specify the List’s name for output purposes. InsertAtFront (lines 49–59), InsertAtBack (lines 64–74), RemoveFrom-Front (lines 77–97) and RemoveFromBack (lines 100–130) are the primary methods of class List. Method IsEmpty (lines 133–136) is a predicate method—such a method checks a condition and returns a bool value without modifying the object on which it’s called. In this case, the method determines whether the list is empty (i.e., firstNode is null). (IsEmpty also could have been implemented as a getter-only property.) If the list is empty, method IsEmpty returns true; otherwise, it returns false. Method Display (lines 139–160) displays the list’s contents. A detailed discussion of class List’s methods follows Fig. 19.5.

Class EmptyListException

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

Class ListTest

Class ListTest (Fig. 19.5) uses the linked-list library to create and manipulate a linked list. [Note: In the project containing Fig. 19.5, you must add a reference to the class library containing the classes in Fig. 19.4.] Line 11 creates a new List object and assigns it to variable list. Lines 14–17 create data to add to the list. Lines 20–27 use List insertion methods to insert these values and use List method Display to output the contents of list after each insertion. 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 32–46) removes objects via List deletion methods, outputs each removed object and outputs list after every deletion. If there’s an attempt to remove an object from an empty list, the catch at lines 48–51 catches the EmptyListException and displays an error message.

Fig. 19.5 Testing class List.

Alternate View 

  1   // Fig. 19.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()
 10      {
 11        var 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.Display();
 22        list.InsertAtFront(aCharacter);
 23        list.Display();
 24        list.InsertAtBack(anInteger);
 25        list.Display();
 26        list.InsertAtBack(aString);
 27        list.Display();
 28
 29        // remove data from list and display after each removal
 30        try
 31        {
 32         object removedObject = list.RemoveFromFront();
 33         Console.WriteLine($"{removedObject} removed");
 34         list.Display();
 35
 36          removedObject = list.RemoveFromFront();
 37          Console.WriteLine($"{removedObject} removed");
 38          list.Display();
 39
 40          removedObject = list.RemoveFromBack();
 41          Console.WriteLine($"{removedObject} removed");
 42          list.Display();
 43
 44           removedObject = list.RemoveFromBack();
 45           Console.WriteLine($"{removedObject} removed");
 46           list.Display();
 47        }
 48        catch (EmptyListException emptyListException)
 49        {
 50            Console.Error.WriteLine($"
{emptyListException}");
 51         }
 52      }
 53   }


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

Method InsertAtFront

Over the next several pages, we discuss each of the methods of class List in detail. Method InsertAtFront (Fig. 19.4, lines 49–59) 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 51).

  2. If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (line 53). The ListNode constructor at line 18 calls the ListNode constructor at lines 22–26, which sets property Data to refer to the object passed as the first argument and sets the Next property’s 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 57). When the ListNode constructor (lines 22–26) executes, it sets property 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. 19.6, part (a) shows a list and a new node during the InsertAtFront operation 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.

Fig. 19.6 InsertAtFront operation.

Performance Tip 19.5

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

Method InsertAtBack

Method InsertAtBack (Fig. 19.4, lines 64–74) 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 66).

  2. If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (line 68). The ListNode constructor at line 18 calls the ListNode constructor at lines 22–26, which sets property 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 72)—setting lastNode.Next that the previous last node links to the new last node. When the ListNode constructor (line 18) executes, it calls the constructor at lines 22–26, which sets property Data to refer to the object passed as an argument and sets the Next reference to null.

In Fig. 19.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.

Fig. 19.7 InsertAtBack operation.

Method RemoveFromFront

Method RemoveFromFront (Fig. 19.4, lines 77–97) removes the front node of the list and returns a reference to the removed data. The method throws an EmptyListException (line 81) 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 84).

  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 89) 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 93). Thus, firstNode references the node that was previously the second node in the List.

  4. Return the removeItem reference (line 96).

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

Fig. 19.8 RemoveFromFront operation.

Method RemoveFromBack

Method RemoveFromBack (Fig. 19.4, lines 100–130) 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 null (line 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 116).

  4. Now “walk the list” with current until it references the node before the last node. The while loop (lines 119–122) 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 125) to update which node is last in the list.

  6. Set current.Next to null (line 126) to remove the last node from the list and terminate the list at the current node.

  7. Return the removeItem reference (line 129).

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

Fig. 19.9 RemoveFromBack operation.

Method Display

Method Display (Fig. 19.4, lines 139–161) first determines whether the list is empty (line 141). If so, Display displays a string consisting of the string "Empty " and the list’s name, then returns control to the calling method. Otherwise, Display outputs the data in the list. The method writes a string consisting of the string "The ", the list’s name and the string "is: ". Then line 149 creates ListNode variable current and initializes it with firstNode. While current is not null, there are more items in the list. Therefore, the method repeatedly displays current.Data (line 154), then assigns current.Next to current (line 155) 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 list—it 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. 19.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.”

Fig. 19.10 Circular, singly linked list.

A doubly linked list (Fig. 19.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. 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.

Fig. 19.11 Doubly linked list.

In a circular, doubly linked list (Fig. 19.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.”

Fig. 19.12 Circular, doubly linked list.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset