C# – How to use LinkedList

by

LinkedList<T> is a doubly linked list. It consists of nodes with values (i.e. integers, strings, etc…) and links to the next and previous node. LinkedList<T> has a reference to the head and tail nodes, which enables efficient insertion (and removal) from the start and end of the list. The main reason to use LinkedList<T> is when you’re doing lots of insertions/removals from the start (or end) of the list need it to be faster than List<T>.

Here’s an example of using LinkedList<T> as a stack (last-in, first-out ordering) by inserting and removing integers from the start of the list.

var linkedList = new LinkedList<int>();
// head -> null <- tail

linkedList.AddFirst(1);
// head -> 1 <- tail

linkedList.AddFirst(2);
// head -> 2 <-> 1 <- tail

Console.WriteLine($"Value={linkedList.First}"); //Outputs: Value=2
linkedList.RemoveFirst();
// head->1 <- last 

Console.WriteLine($"Value={linkedList.First}"); //Outputs: Value=1
linkedList.RemoveFirst();
// head -> null <- tail
Code language: C# (cs)

Technical note: For simplicity, this shows ‘head’ and ‘tail’ separately, but ‘tail’ is actually just ‘head.previous’. That’s an implementation detail that isn’t important for understanding the concept.

LinkedList’s primary methods and properties

LinkedList<T> is useful in scenarios where you need to do lots of head/tail insertions (and removals). Here are the primary methods/properties you need to know about:

  • AddFirst(): Inserts a node at the start of the linked list.
  • AddLast(): Inserts a node at the end of the linked list.
  • First: The node at the start of the list (aka the head).
  • Last: The node at the end of the list (aka the tail).
  • RemoveFirst(): Removes the node at the start of the linked list.
  • RemoveLast(): Removes the node at the end of the linked list.

It should be noted that the removal methods are void. They remove the node but don’t return a value. To get the value before removing, use the First/Last properties.

Iterating through the LinkedList<T>

You can iterate through the LinkedList’s values with a regular foreach loop:

var linkedList = new LinkedList<int>();
linkedList.AddFirst(1);
linkedList.AddFirst(2);
linkedList.AddFirst(3);

foreach(var val in linkedList)
{
    Console.WriteLine(val);
}
Code language: C# (cs)

This outputs the following:

3
2
1Code language: plaintext (plaintext)

LinkedList<T> vs List<T>

LinkedList<T> is a doubly linked list and it provides efficient O(1) insertion and removal operations from the start and end of the list.

List<T> manages a dynamically-sized array internally. Appending to the end of the list (or removing from it) is an efficient O(1) operation. On the other hand, inserting (or removing from) anywhere else is an O(n) operation that requires shifting multiple elements (with Array.Copy()). Inserting/removing at the start of the list requires shifting ALL elements.

Therefore, if you’re doing lots of head insertions/removals, use LinkedList<T>. This is up to 30x faster than List<T> (based on my testing).

Note: List<T> sometimes has to resize the internal array, but the cost is amortized across all operations. That won’t have a significant impact on performance compared to the much greater cost of shifting ALL elements repeatedly.