LinkedList
CollectionSection 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.
Lines 16–25 create LinkedList
s of string
s 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
.
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 string
s. 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.
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 InvalidOperationException
s.
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 string
s and converts each string
value to uppercase. This method replaces the string
s 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.
ToUppercaseStrings
is not a Generic MethodIt does not make sense to declare ToUppercaseStrings
as a generic method, because it uses the string
-specific methods of the values in the nodes.
For maximal code reuse, define methods with generic type parameters whenever possible.
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.
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.