BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

.NET Framework
.NET 2.0+

Doubly-Linked Lists and LinkedList<T>

A linked list is a data structure that holds a sequence of values. In a doubly-linked list, each item in the collection includes a pointer to the previous and next elements. This allows insertions and deletions to be performed quickly and efficiently.

Removing a Node

Removing a node from a linked list is also a fast operation. Only the nodes that point to the item to be excluded need adjustment. Each has a pointer updated to link to the other. You can see this in the diagram below. When compared to the original linked list that contained the values 5, 10 and 15, this list has had the ten node removed. The five node's "next" pointer has been altered to point to the fifteen node. In turn, the fifteen node's "previous" pointer references the five node.

Linked List

LinkedList<T>

Luckily, if you are using the .NET 2.0 framework version 2.0 or later, there is no need to implement your own linked list. The System.Collections.Generic namespace includes a class, named LinkedList, that provides a doubly-linked list structure. As you might expect from the namespace, this is a generic class so can hold values of any type. In the remaining sections of this article we'll look at the main features of the LinkedList<T> type.

Creating a LinkedList<T>

As with many .NET collection types, LinkedList<T> includes a default constructor, which creates an empty list, and one that receives a sequence of values in its parameter. The second constructor allows you to initialise a linked list with a number of items that you have in an array, list or other collection.

The following code demonstrates the initialisation of a linked list from the items in an array. The order of items is preserved when the new collection is created. Note that you can enumerate the values in the list with a foreach loop without needing to understand or use the node pointers. The code also outputs the number of items in the linked list, using the Count property. Count is available because the class implements ICollection, as well as several other interfaces.

int[] items = new int[] { 5, 10, 15 };
LinkedList<int> list = new LinkedList<int>(items);

foreach (int i in list)
{
    Console.WriteLine(i);
}

Console.WriteLine("{0} items", list.Count);

/* OUTPUT

5
10
15
3 items

*/

Traversing the List

Sometimes you will want to traverse or navigate the items in a linked list using the system of "previous" and "next" pointers described earlier. To do so, it is important to understand that, despite the foreach loop suggesting otherwise, the linked list holds nodes, not values. In fact, every item in the list is of the type, LinkedListNode<T>. The generic type for the node always matches the type of the overall list.

You can obtain references to the first and last nodes using the First and Last properties of the linked list. Each returns a LinkedListNode<T> object. To determine the value that is stored in a node you can read its Value property.

This is demonstrated in the sample code below. Once the linked list is initialised, the code outputs the values from the first and last nodes.

int[] items = new int[] { 5, 10, 15 };
LinkedList<int> list = new LinkedList<int>(items);

Console.WriteLine("First: {0}", list.First.Value);
Console.WriteLine("Last: {0}", list.Last.Value);

/* OUTPUT

First: 5
Last: 15

*/

To follow the pointers between nodes you can use the LinkedListNode<T>'s Next and Previous properties. Each returns a LinkedListNode<T> object that represents an adjacent item from the list. If the next or previous node is a sentinel node, the result will be null.

The next example shows the value of the item immediately after the first node and the value from the node before the final element. These are both the same node, which has a value of ten.

int[] items = new int[] { 5, 10, 15 };
LinkedList<int> list = new LinkedList<int>(items);

Console.WriteLine("First.Next: {0}", list.First.Next.Value);
Console.WriteLine("Last.Previous: {0}", list.Last.Previous.Value);

/* OUTPUT

First.Next: 10
Last.Previous: 10

*/
3 November 2013