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.

Adding Items

The purpose of a linked list is to allow fast inserts and deletions. If you only initialised your lists from existing collections, you would end up with a less efficient collection that used additional memory for pointers unnecessarily. So let's look at how items can be inserted into a list.

There are four methods for inserting items. To add a value to the beginning of a linked list, use AddFirst, passing the new value. AddLast performs a similar action but places the new value at the very end of the list. You can also use AddBefore and AddAfter to insert items before or after an existing node. These methods require two arguments. The first specifies the node that you wish to insert next to. The second parameter receives the new value.

The following example shows all four methods in action.

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

LinkedListNode<int> originalFirst = list.First;
LinkedListNode<int> originalLast = list.Last;

list.AddFirst(1);
list.AddLast(6);
list.AddAfter(originalFirst, 3);
list.AddBefore(originalLast, 4);

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

1
2
3
4
5
6

*/

NB: As LinkedList<T> implements ICollection<T>, it also includes an Add method. This adds a new item at the end of the linked list.

Removing Items

You can remove single items from a linked list using the RemoveFirst, RemoveLast and Remove methods. RemoveFirst and RemoveLast are the simplest. As you might imagine, they delete the first or last item from the linked list. These two methods do not have any parameters.

Remove has two overloaded versions. If you pass a LinkedListNode<T> object, that specific node is removed from the list. If you provide a value of the type defined by the generic type parameter, the first node containing that value is removed from the list. If the value is duplicated, further occurrences of the value remain.

NB: Removing a node is an O(1) operation. Removing a value is O(n), as the value must be located before the appropriate pointers can be updated.

int[] items = new int[] { 1, 2, 3, 4, 5 };
LinkedList<int> list = new LinkedList<int>(items);

list.RemoveFirst();
list.RemoveLast();
list.Remove(3);

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

2
4

*/

Finally, you can empty a linked list completely using the Clear method. No arguments are required.

int[] items = new int[] { 1, 2, 3, 4, 5 };
LinkedList<int> list = new LinkedList<int>(items);

list.Clear();

Console.WriteLine(list.Count);
            
/* OUTPUT

0

*/

Searching

Linked lists are not ideal data structures to use when you need to search the sequence for specific values. However, the LinkedList<T> class does include a pair of methods that traverse the list until they find a node containing a specified value. These are Find and FindLast. Find looks for the first element with the provided value. FindLast starts the search from the final node and navigates backwards until the value is located. Both operations are O(n).

int[] items = new int[] { 1, 2, 3, 4, 5 };
LinkedList<int> list = new LinkedList<int>(items);

LinkedListNode<int> found = list.Find(3);

Console.WriteLine(found.Next.Value);

/* OUTPUT

4

*/

List<T> or LinkedList<T>?

Deciding whether to use a LinkedList<T> or a List<T> collection depends on several factors. Standard generic lists are backed by an internal array that is varied in size as the list grows. The elements of the list are contiguous, so no pointers are required and the list generally has lower memory requirements. However, inserting items anywhere but at the end of a list can be expensive.

A linked list usually requires more memory because of the additional pointers. However, these pointers make inserting and removing items very fast. There is a problem though. If you need to find a specific item in order to insert near it or to remove it, the find operation can slow the overall process. This can remove the advantage that the linked list has over its array-backed counterpart.

All of this means that the benefits of a linked list can be lost if you need to perform random insertions and deletions. You will obtain the greatest benefit from a LinkedList<T> when you perform lots of insertions and removals from the ends of the list, as these do not involve searching for nodes.

3 November 2013