21.5 Generic LinkedList Collection
Section 9.4 introduced the generic List<T> collection, which defines an array-based list implementation. Here, we discuss class LinkedList<T>, which defines a doubly linked list that an app can navigate both forwards and backwards. A LinkedList<T> contains nodes of generic class LinkedListNode<T>. Each node contains property Value and read-only properties Previous and Next. The Value property’s type matches LinkedList<T>’s single type parameter because it contains the data stored in the node. Previous gets a reference to the preceding node in the linked list (or null if the node is the first of the list). Similarly, Next gets a reference to the subsequent reference in the linked list (or null if the node is the last of the list). We demonstrate a few linked-list manipulations in Fig. 21.5.
Fig. 21.5 Using LinkedLists.
Alternate View
1 // Fig. 21.5: LinkedListTest.cs
2 // Using LinkedLists.
3 using System;
4 using System.Collections.Generic;
5
6 class LinkedListTest
7 {
8 private static readonly string[] colors =
9 {"black", "yellow", "green", "blue", "violet", "silver"};
10 private static readonly string[] colors2 =
11 {"gold", "white", "brown", "blue", "gray"};
12
13 // set up and manipulate LinkedList objects
14 static void Main()
15 {
16 var list1 = new LinkedList<string>();
17
18 // add elements to first linked list
19 foreach (var color in colors)
20 {
21 list1.AddLast(color);
22 }
23
24 // add elements to second linked list via constructor
25 var list2 = new LinkedList<string>(colors2);
26
27 Concatenate(list1, list2); // concatenate list2 onto list1
28 PrintList(list1); // display list1 elements
29
30 Console.WriteLine("
Converting strings in list1 to uppercase
");
31 ToUppercaseStrings(list1); // convert to uppercase string
32 PrintList(list1); // display list1 elements
33
34 Console.WriteLine("
Deleting strings between BLACK and BROWN
");
35 RemoveItemsBetween(list1, "BLACK", "BROWN");
36
37 PrintList(list1); // display list1 elements
38 PrintReversedList(list1); // display list in reverse order
39 }
40
41 // display list contents
42 private static void PrintList<T>(LinkedList<T> list)
43 {
44 Console.WriteLine("Linked list: ");
45
46 foreach (var value in list)
47 {
48 Console.Write($"{value} ");
49 }
50
51 Console.WriteLine();
52 }
53
54 // concatenate the second list on the end of the first list
55 private static void Concatenate<T>(
56 LinkedList<T> list1, LinkedList<T> list2)
57 {
58 // concatenate lists by copying element values
59 // in order from the second list to the first list
60 foreach (var value in list2)
61 {
62 list1.AddLast(value); // add new node
63 }
64 }
65
66 // locate string objects and convert to uppercase
67 private static void ToUppercaseStrings(LinkedList<string> list)
68 {
69 // iterate over the list by using the nodes
70 LinkedListNode<string> currentNode = list.First;
71
72 while (currentNode != null)
73 {
74 string color = currentNode.Value; // get value in node
75 currentNode.Value = color.ToUpper(); // convert to uppercase
76 currentNode = currentNode.Next; // get next node
77 }
78 }
79
80 // delete list items between two given items
81 private static void RemoveItemsBetween<T>(
82 LinkedList<T> list, T startItem, T endItem)
83 {
84 // get the nodes corresponding to the start and end item
85 LinkedListNode<T> currentNode = list.Find(startItem);
86 LinkedListNode<T> endNode = list.Find(endItem);
87
88 // remove items after the start item
89 // until we find the last item or the end of the linked list
90 while ((currentNode.Next != null) && (currentNode.Next != endNode))
91 {
92 list.Remove(currentNode.Next); // remove next node
93 }
94 }
95
96 // display reversed list
97 private static void PrintReversedList<T>(LinkedList<T> list)
98 {
99 Console.WriteLine("Reversed List:");
100
101 // iterate over the list by using the nodes
102 LinkedListNode<T> currentNode = list.Last;
103
104 while (currentNode != null)
105 {
106 Console.Write($"{currentNode.Value} ");
107 currentNode = currentNode.Previous; // get previous node
108 }
109
110 Console.WriteLine();
111 }
112 }
Linked list: black yellow green blue violet silver gold white brown blue gray Converting strings in list1 to uppercase Linked list: BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY Deleting strings between BLACK and BROWN Linked list: BLACK BROWN BLUE GRAY Reversed List: GRAY BLUE BROWN BLACK
Lines 16–25 create LinkedLists of strings named list1 and list2 and fill them with the contents of arrays colors and colors2, respectively. LinkedList is a generic class that has one type parameter for which we specify the type argument string in this example (lines 16 and 25).
LinkedList Methods AddLast and AddFirst
We demonstrate two ways to fill the lists. Lines 19–22 use the foreach statement and method AddLast to fill list1. The AddLast method creates a new LinkedListNode (with the node’s value available via the Value property) and appends this node to the end of the list. There’s also an AddFirst method that inserts a node at the beginning of the list.
Line 25 invokes the constructor that takes an IEnumerable<T> parameter. All arrays implement the generic interfaces IList<T> and IEnumerable<T> with the array’s element type as the type argument, so a string array implements IEnumerable<string>. Thus, colors2 is an IEnumerable<string> and can be passed to the List<string> constructor to initialize the List. This constructor copies array colors2’s contents into list2.
Methods That Test Class LinkedList
Line 27 calls generic method Concatenate (lines 55–64) to append all elements of list2 to the end of list1. Line 28 calls method PrintList (lines 42–52) to output list1’s contents. Line 31 calls method ToUppercaseStrings (lines 67–78) to convert each string element to uppercase, then line 32 calls PrintList again to display the modified strings. Line 35 calls method RemoveItemsBetween (lines 81–94) to remove the elements between "BLACK" and "BROWN"—not including either. Line 37 outputs the list again, then line 38 invokes method PrintReversedList (lines 97–111) to display the list in reverse order.
Generic Method Concatentate
Generic method Concatenate (lines 55–64) iterates over its second parameter (list2) with a foreach statement and calls method AddLast to append each value to the end of its first parameter (list1). The LinkedList class’s enumerator loops over the values of the nodes, not the nodes themselves, so the iteration variable is inferred to be of the LinkedList’s element type T. Notice that this creates a new node in list1 for each node in list2. One LinkedListNode cannot be a member of more than one LinkedList. If you want the same data to belong to more than one LinkedList, you must make a copy of the node for each list to avoid InvalidOperationExceptions.
Generic Method PrintList and Method ToUppercaseStrings
Generic method PrintList (lines 42–52) similarly uses a foreach statement to iterate over the values in a LinkedList, and outputs them. Method ToUppercaseStrings (lines 67–78) takes a linked list of strings and converts each string value to uppercase. This method replaces the strings stored in the list, so we cannot use a foreach statement as in the previous two methods. Instead, we obtain the first LinkedListNode via the First property (line 70) and use a sentinel-controlled while statement to loop through the list (lines 72–77). Each iteration of the while statement obtains and updates the contents of currentNode via property Value (line 74), using string method ToUpper to create an uppercase version of the string (line 75). Then line 76 moves to the next node in the list by assigning to currentNode the value of currentNode.Next, which refers to the LinkedList’s next node. The Next property of the LinkedList’s last node is null, so when the while statement iterates past the end of the list, the loop exits.
Method ToUppercaseStrings is not a Generic Method
It does not make sense to declare ToUppercaseStrings as a generic method, because it uses the string-specific methods of the values in the nodes.
Software Engineering Observation 21.1
For maximal code reuse, define methods with generic type parameters whenever possible.
Generic Method RemoveItemsBetween
Generic method RemoveItemsBetween (lines 81–94) removes a range of items between two nodes. Lines 85–86 obtain the two “boundary” nodes of the range by using method Find, which performs a linear search on the list and returns the first node that contains a value equal to Find’s argument, or null if the value is not found. We store the node preceding the range in local variable currentNode and the node following the range in endNode.
Lines 90–93 remove all the elements between currentNode and endNode. Each iteration of the loop removes the node following currentNode by invoking method Remove (line 92), which takes a LinkedListNode, splices it out of the LinkedList, and fixes the references of the surrounding nodes. After the Remove call, currentNode’s Next property now refers to the node following the node just removed, and that node’s Previous property refers to currentNode. The while statement continues to loop until there are no nodes left between currentNode and endNode, or until currentNode is the last node in the list. An overloaded version of method Remove performs a linear search for a specified value and removes the first node in the list that contains it.
Method PrintReversedList
Method PrintReversedList (lines 97–111) displays the list backwards by navigating the nodes manually. Line 102 obtains the last element of the list via the Last property and stores it in currentNode. The while statement in lines 104–108 iterates through the list backwards by assigning to currentNode the value of currentNode.Previous (the previous node in the list). The loop terminates when currentNode.Previous is null. Note how similar this code is to lines 70–77, which iterated through the list from the beginning to the end.