Intro

LinkedList<T> is a doubly linked list where each node points to previous and next nodes. It is useful when you already keep node references and need frequent O(1) inserts/removes around those nodes.

Unlike array-backed collections, linked lists do not store elements contiguously:

• Random index access is O(n) because traversal is required.
• Inserting/removing at a known node is O(1).
• Each element carries node-pointer overhead, so memory locality is worse than List<T>.

Structure

graph LR
    H[head] --> N1[node a]
    N1 <--> N2[node b]
    N2 <--> N3[node c]
    N3 --> T[tail]

Example

var list = new LinkedList<string>();
var a = list.AddLast("A");
list.AddLast("C");

list.AddAfter(a, "B");
list.Remove("C");

Pitfalls

• Using LinkedList<T> for index-based access causes O(n) scans and can underperform List<T> significantly. Prefer List<T>/arrays for index-heavy workloads, or store node handles when linked-list locality edits are truly required.
• Using detached or foreign LinkedListNode<T> instances as anchors (AddBefore, AddAfter, Remove) throws because a node must belong to the target list context. Check node.List before using node handles and re-find/re-add nodes when needed.
• Pointer-rich node allocation hurts cache locality, so iteration can be slower even when complexity looks similar on paper. Prefer List<T> for traversal-heavy workloads unless node-local O(1) edits are the dominant operation.

Tradeoffs

• LinkedList<T> vs List<T>: linked list wins for O(1) local edits around known nodes; list usually wins for traversal and random access.
• LinkedList<T> vs Queue<T>/Stack<T>: queue/stack APIs are simpler and often faster when you only need FIFO/LIFO behavior.

Questions

Links