C# List vs LinkedList: Performance Differences

In C#, both List<T> and LinkedList<T> store sequential collections of elements, but their underlying data structures lead to vastly different performance characteristics. This article breaks down how memory layout, index access, element insertion, deletion, and CPU cache locality influence runtime efficiency, providing a clear guide on when to use each collection.

Underlying Data Structures

  • List<T> is backed by a dynamically resized, contiguous array. When its internal array reaches capacity, it allocates a larger array (usually double the size) and copies the elements over.
  • LinkedList<T> is a doubly linked list. Each element is wrapped inside a LinkedListNode<T> heap object containing the element's value, a pointer to the next node, and a pointer to the previous node.

Random Access and Indexing

  • List<T> (\(O(1)\)): Accessing an item by index (e.g., list[i]) occurs in constant time. Because the array elements are stored contiguously in memory, the runtime calculates the exact memory address with simple pointer arithmetic.
  • LinkedList<T> (\(O(n)\)): Linked lists do not support direct indexing. To reach a specific index, the runtime must traverse nodes one by one starting from either the head or the tail.

Insertion and Deletion

The performance of adding and removing elements depends heavily on where the operation takes place.

At the End

  • List<T>: Adding an item to the end (Add()) is an amortized \(O(1)\) operation. It is near-instantaneous until the internal array runs out of capacity, at which point an \(O(n)\) resize and copy occurs.
  • LinkedList<T>: Adding an item to the end (AddLast()) is always \(O(1)\) because it only requires updating the tail pointers.

At the Beginning or Middle

  • List<T>: Inserting or removing items at the beginning (Insert(0, ...) / RemoveAt(0)) or middle takes \(O(n)\) time. All subsequent elements must be shifted in memory to accommodate or close the gap.
  • LinkedList<T>: Adding or removing a node takes \(O(1)\) time, provided you already hold a direct reference to that LinkedListNode<T>. However, if you must first search for the node by value or index, the search step takes \(O(n)\) time, often negating the insertion speed advantage.

Memory Consumption and Cache Locality

Hardware architecture plays a massive role in real-world performance, giving List<T> a significant edge in most scenarios.

  • Cache Locality: Modern CPUs load data into cache lines in chunks. Because List<T> stores data in contiguous memory blocks, sequential operations yield high CPU cache hits. In contrast, LinkedList<T> nodes are scattered across the managed heap, frequently triggering CPU cache misses and slowing down traversal.
  • Memory Overhead:
    • List<T> has minimal memory overhead—only the unused capacity in its buffer array.
    • LinkedList<T> has substantial overhead. Every element requires a separate LinkedListNode<T> object on the heap, which adds 24 to 32 bytes of overhead per item on 64-bit systems (object headers plus forward and backward pointers), not counting the actual payload.
  • Garbage Collection (GC) Pressure: LinkedList<T> allocates a new object for every single added item and deallocates it upon removal, increasing GC pressure. List<T> reuses its underlying array and only allocates during resizes.

Performance Summary

Operation / Metric List<T> LinkedList<T>
Index Access (list[i]) \(O(1)\) \(O(n)\)
Append to End Amortized \(O(1)\) Pure \(O(1)\)
Prepend to Start \(O(n)\) Pure \(O(1)\)
Insert / Remove (known position) \(O(n)\) (element shifting) Pure \(O(1)\) (pointer update)
Sequential Traversal Extremely Fast (contiguous) Slower (cache misses)
Memory Overhead Low (only unused capacity) High (node object per item)
GC Pressure Low High

When to Choose Which

Use List<T> as your default collection. It is faster for general iteration, random access, and appending items, while consuming less memory and being friendly to modern CPU caches.

Use LinkedList<T> only when your application requires frequent insertions or deletions at both ends (like a queue or deque), or constant-time splicing/insertions in the middle of a collection where you already maintain direct node references.