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.
var list = new LinkedList<int>(); LinkedListNode<int> n = list.AddLast(10); list.AddFirst(5); list.AddAfter(n, 15); // 5, 10, 15
Try it
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.
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
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,ContainsandRemove(T)scan the list, so they are O(n).Countis O(1). - No indexer. There is no
list[i];ElementAtfrom 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 aList<int>and is less cache-friendly. For most workloadsList<T>orQueue<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
foreachis running invalidates the enumerator; savenode.Nextbefore removing the current node when you walk manually. - Circular behaviour is not built in.
Nextof the last node isnull. - Not thread-safe for concurrent writes.