All 16 Collections questions
More in Collections
When would you reach for a ConcurrentDictionary or an immutable collection? How do you avoid multiple enumeration of an IEnumerable? How does Dictionary<TKey,TValue> handle hash collisions internally, and why does a poor GetHashCode() implementation degrade its performance? What is the performance and thread-safety difference between ConcurrentDictionary<TKey,TValue> and a regular Dictionary<TKey,TValue> guarded by a manual lock? How does the 'yield return'-based lazy evaluation of collections (like LINQ or a custom iterator) differ from eagerly materializing a full collection, in terms of memory usage? How would you implement a custom, strongly-typed, read-only wrapper around a mutable collection to safely expose it from a class's public API?
Advertisement
C# › Collections

How would you choose between List<T>, LinkedList<T>, and ImmutableList<T> based on their different Big-O characteristics for common operations?

Advanced

Answer

List<T> offers O(1) index access and O(1) amortized append, but O(n) insertion/removal in the middle (due to shifting elements); LinkedList<T> offers O(1) insertion/removal ANYWHERE (given a node reference), but O(n) index access (no random access at all); ImmutableList<T> uses a persistent tree structure giving O(log n) for most operations while preserving full immutability (every 'mutation' returns a new list sharing most of the old structure).
List<int> list = new(); list.Insert(0, 1); // O(n): shifts every existing element

LinkedList<int> linked = new(); linked.AddFirst(1); // O(1): no shifting needed

ImmutableList<int> immutable = ImmutableList<int>.Empty.Add(1); // O(log n), returns a NEW list
Real-world example Choosing LinkedList<T> specifically for a scenario with frequent insertions/removals at arbitrary positions and no need for index access, like an LRU cache's internal ordering.

Common follow-ups: In practice, why does List<T> often outperform LinkedList<T> even for insertion-heavy workloads, despite the Big-O theory favoring LinkedList<T>?

Generics
All 16 Collections questions