Skip to content
Tutorials Center
My learning

Topics

C# Reference ยท Collections

The LinkedList<T> class

Reference for C# LinkedList<T>: AddFirst, AddLast, AddBefore, AddAfter, Remove, Find, LinkedListNode<T>, complexity and when to prefer List<T>.

LinkedList<T> (namespace System.Collections.Generic) is a doubly linked list. Every element lives in its own LinkedListNode<T> object that knows its Previous and Next neighbours. Because you can hold on to a node, you can insert before it, insert after it or remove it in O(1), without shifting other elements.

That strength is rare in practice. There is no indexer, so reaching the middle takes O(n), and each node costs an extra object on the heap, which makes iteration slower than a List<T>. Choose LinkedList<T> only when you keep node references and splice often, for example in an LRU cache.

C#
var list = new LinkedList<int>();
LinkedListNode<int> n = list.AddLast(10);
list.AddFirst(5);
list.AddAfter(n, 15);   // 5, 10, 15

Try it

C# Adding, finding and removing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# A tiny LRU order list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Syntax

C#
public class LinkedList<T> : ICollection<T>, IReadOnlyCollection<T>, ICollection
{
    public LinkedList();
    public LinkedList(IEnumerable<T> collection);

    public int Count { get; }
    public LinkedListNode<T>? First { get; }
    public LinkedListNode<T>? Last { get; }

    public LinkedListNode<T> AddFirst(T value);
    public LinkedListNode<T> AddLast(T value);
    public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value);
    public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value);
    public bool Remove(T value);
    public void Remove(LinkedListNode<T> node);
    public void RemoveFirst();
    public void RemoveLast();
    public LinkedListNode<T>? Find(T value);
    public LinkedListNode<T>? FindLast(T value);
    public bool Contains(T value);
    public void Clear();
}
Name Description
value The item to store. A new node is created for it.
node An existing node of this list, used as the anchor for AddBefore, AddAfter or Remove.
First, Last The end nodes, or null when the list is empty.
LinkedListNode<T>.Value The stored item (settable).
LinkedListNode<T>.Next, Previous Neighbour nodes, or null at the ends.

Returns: the Add... methods return the new LinkedListNode<T>. Find returns the first node whose value equals the argument (using the default equality comparer), or null. Remove(T) returns bool.

Errors: ArgumentNullException if a node is null. InvalidOperationException if a node does not belong to the list (or already belongs to another list when you add an existing node), and for RemoveFirst and RemoveLast on an empty list.

Usage notes

  • Complexity: adding or removing at either end, or next to a node you already hold, is O(1). Find, Contains and Remove(T) scan the list, so they are O(n). Count is O(1).
  • No indexer. There is no list[i]; ElementAt from LINQ walks the nodes and is O(n).
  • Memory and speed. Each node is a separate heap object with two references plus the header, so a LinkedList<int> uses several times the memory of a List<int> and is less cache-friendly. For most workloads List<T> or Queue<T> is faster even for insert-heavy code.
  • Nodes belong to one list. To move a node, call Remove(node) first and then add that same node object again, which avoids allocating a new one.
  • Enumeration: modifying the list while a foreach is running invalidates the enumerator; save node.Next before removing the current node when you walk manually.
  • Circular behaviour is not built in. Next of the last node is null.
  • Not thread-safe for concurrent writes.