C# Built-In Data Structures for Coding Interviews

You picked C# for your coding interview. Solid choice. C# has a genuinely good collection library, decent generics, and it won't make you implement a heap from scratch like JavaScript will. The trap is that it has just enough subtle differences from Java to send you somewhere embarrassing at exactly the wrong moment. The Dictionary indexer throws. The PriorityQueue is a min-heap named like a max-heap. List.Sort() is not stable. SortedSet has no floor or ceiling.

None of these are deal-breakers. All of them will cost you if you don't know about them beforehand.

Here's every structure you'll reach for, what it costs, and what bites.

C# Data Structures: Quick Reference

Collection	Lookup	Insert	Delete	Ordered	Notes
`List<T>`	O(1) index, O(n) search	O(1) amortized end, O(n) middle	O(n)	No	Use everywhere
`Dictionary<K,V>`	O(1) avg	O(1) avg	O(1) avg	No	Indexer throws on missing key
`HashSet<T>`	O(1) avg	O(1) avg	O(1) avg	No	Set ops built in
`SortedDictionary<K,V>`	O(log n)	O(log n)	O(log n)	Yes	Red-black tree
`SortedSet<T>`	O(log n)	O(log n)	O(log n)	Yes	No floor/ceiling API
`SortedList<K,V>`	O(log n)	O(n)	O(n)	Yes	Index access, memory efficient
`Stack<T>`	O(1) Peek	O(1) Push	O(1) Pop	No
`Queue<T>`	O(1) Peek	O(1) Enqueue	O(1) Dequeue	No
`LinkedList<T>`	O(n)	O(1) with node	O(1) with node	No	Poor cache locality
`PriorityQueue<E,P>`	O(1) Peek	O(log n)	O(log n)	By priority	.NET 6+, min-heap

`List<T>`: The Default Choice

List<T> is a dynamic array. It doubles capacity when full, so appending is O(1) amortized. Random access by index is O(1). Everything else is O(n).

var nums = new List<int> { 3, 1, 4, 1, 5 };
nums.Add(9);               // O(1) amortized
nums.Insert(2, 99);        // O(n), shifts elements right
nums.RemoveAt(0);          // O(n), shifts elements left
nums.Contains(4);          // O(n) linear scan
int x = nums[3];           // O(1)
nums.Sort();               // O(n log n), introsort, NOT stable
nums.Sort((a, b) => b - a); // descending

List.Sort() is not stable. If you need to preserve the relative order of equal elements, use LINQ's OrderBy. It uses a stable merge sort. The interviewer will not care which one you use until they suddenly care very much.

// Stable sort by first element of pair, preserve order of ties
var pairs = new List<(int, int)> { (2, 1), (1, 3), (2, 0) };
var sorted = pairs.OrderBy(p => p.Item1).ToList();

`Dictionary<K,V>` and `HashSet<T>`: The O(1) Workhorses

Both use a hash table internally. Average O(1) for insert, lookup, and delete. Worst case O(n) on adversarial collisions, which won't happen in an interview unless you have truly terrible luck.

The one trap that burns everyone

The indexer throws a KeyNotFoundException if the key is absent. Not null. Not zero. An exception. Right in the middle of a frequency-counting problem while your interviewer watches in silence.

var freq = new Dictionary<string, int>();

// WRONG: throws if "hello" isn't present
int count = freq["hello"];

// RIGHT: safe options
freq.TryGetValue("hello", out int val);        // val = 0 if missing
int val2 = freq.GetValueOrDefault("hello", 0); // cleaner
bool exists = freq.ContainsKey("hello");       // check first

// Idiomatic frequency counting
freq["hello"] = freq.GetValueOrDefault("hello", 0) + 1;

This is the single most common C# interview bug. Burn GetValueOrDefault into your fingers.

HashSet<T> gives you set operations that come up more often than you'd expect:

var a = new HashSet<int> { 1, 2, 3, 4 };
var b = new HashSet<int> { 3, 4, 5, 6 };

a.UnionWith(b);        // a = {1,2,3,4,5,6}
a.IntersectWith(b);    // a = {3,4}
a.ExceptWith(b);       // a = {1,2}
a.IsSubsetOf(b);       // false

Sorted Collections: The Java Gap

This is where C# genuinely hurts compared to Java. Java's TreeMap and TreeSet have floorKey, ceilingKey, higherKey, lowerKey. You call the method, you get the answer. C# has none of these directly. You get GetViewBetween, which is functional but looks like you lost a bet.

`SortedDictionary<K,V>`

Red-black tree. O(log n) for everything. Iterates in key order. Use it when you need a sorted key-value map with frequent inserts and deletes.

var sd = new SortedDictionary<int, string>();
sd[3] = "three";
sd[1] = "one";
sd[2] = "two";
foreach (var kv in sd) Console.WriteLine(kv.Key); // 1, 2, 3

// Keys property gives sorted sequence
int first = sd.Keys.First();  // 1
int last  = sd.Keys.Last();   // 3

`SortedSet<T>`

Red-black tree of unique values. O(log n) for add, remove, contains. No floor or ceiling method. The workaround uses GetViewBetween, which returns a live view of the set between two bounds. Calling .Min or .Max on it walks the tree, so it's still O(log n), just more typing.

var ss = new SortedSet<int> { 1, 3, 5, 7, 9 };

// Floor: largest element <= x
int FloorVal(SortedSet<int> set, int x) =>
    set.GetViewBetween(int.MinValue, x).Max;

// Ceiling: smallest element >= x
int CeilVal(SortedSet<int> set, int x) =>
    set.GetViewBetween(x, int.MaxValue).Min;

// Direct range queries work cleanly:
var between = ss.GetViewBetween(3, 7); // {3, 5, 7}

A proposal to add GetLowerThan and GetHigherThan in .NET 10 is open but not shipped. GetViewBetween is what you have.

`SortedList<K,V>` vs `SortedDictionary<K,V>`

	`SortedList`	`SortedDictionary`
Internal structure	Two parallel arrays	Red-black tree
Insert/delete	O(n)	O(log n)
Lookup	O(log n)	O(log n)
Memory	Lower	Higher
Index access	Yes (`Keys[i]`, `Values[i]`)	No
Pre-sorted bulk load	Faster	Slower

Use SortedDictionary when you insert and delete frequently. Use SortedList when you load data once and mostly read. For most interview problems, SortedDictionary is the default.

`Stack<T>` and `Queue<T>`: Simple, One Caveat

Both are O(1) at their operating end. Queue<T>.Dequeue() throws InvalidOperationException on an empty collection. Same for Stack<T>.Pop(). Use TryDequeue / TryPop if there is any doubt.

var stack = new Stack<int>();
stack.Push(1); stack.Push(2);
int top = stack.Peek();   // 2, does not remove
int val = stack.Pop();    // 2

var queue = new Queue<int>();
queue.Enqueue(1); queue.Enqueue(2);
int front = queue.Peek();    // 1
int head  = queue.Dequeue(); // 1

When you need a double-ended queue for sliding window or monotonic deque patterns, use LinkedList<T> directly. C# has no built-in Deque<T>. This is fine. It is also mildly annoying.

var deque = new LinkedList<int>();
deque.AddFirst(1);    // push front
deque.AddLast(2);     // push back
deque.RemoveFirst();  // pop front
deque.RemoveLast();   // pop back

`LinkedList<T>`: When to Actually Use It

LinkedList<T> is a doubly linked list. Each node is a LinkedListNode<T> with Previous and Next pointers.

The only time this beats List<T> is when you already hold a direct node reference. With the node, insertion and deletion are O(1). Without it, finding the node first costs O(n), and pointer chasing makes sequential traversal 5 to 10x slower than an array due to cache misses.

The canonical interview use case: an LRU cache needs O(1) removal from the middle of a list given a direct pointer. That's the whole reason this structure exists in interview prep.

var list = new LinkedList<int>();
var node = list.AddLast(42);  // keep the node reference
list.AddBefore(node, 10);
list.Remove(node);            // O(1) because we have the node

`PriorityQueue<TElement, TPriority>`: The Heap

Added in .NET 6. It is a min-heap: Dequeue() returns the element with the smallest priority. The name suggests priority means importance. The behavior means smallest number leaves first. So priority 1 beats priority 10. If your mental model is "higher number = more important," you will build an inverted heap and not notice until you wonder why the smallest element keeps coming out.

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low",  10);
pq.Enqueue("high",  1);
pq.Enqueue("mid",   5);

Console.WriteLine(pq.Dequeue()); // "high" (priority 1, smallest)

For a max-heap, pass a reversed comparer:

var maxPq = new PriorityQueue<int, int>(
    Comparer<int>.Create((a, b) => b.CompareTo(a))
);
maxPq.Enqueue(10, 10);
maxPq.Enqueue(30, 30);
maxPq.Enqueue(20, 20);
Console.WriteLine(maxPq.Dequeue()); // 30

PriorityQueue has no DecreaseKey and no way to update an existing entry's priority. For Dijkstra, push duplicate entries and skip stale ones at pop time.

// Lazy deletion pattern for Dijkstra
var dist = new int[n];
// push (distance, node) pairs
pq.Enqueue(node, newDist);
while (pq.Count > 0) {
    pq.Dequeue(out int node, out int d);
    if (d > dist[node]) continue; // stale entry, skip
    // process node
}

The Five Traps

1. Dictionary indexer throws, it does not return null. Use TryGetValue or GetValueOrDefault. This one gets everyone eventually.

2. PriorityQueue is a min-heap. Smallest priority number dequeues first. Negate priorities for max behavior, or pass a custom comparer.

3. List.Sort() is not stable. Use OrderBy when tie-breaking order matters.

4. SortedSet has no floor/ceiling. Unlike Java's TreeSet, you need the GetViewBetween workaround. It works, but explaining it during an interview costs time.

5. LinkedList is slower than List for most operations. Pointer chasing makes sequential traversal 5 to 10x slower due to cache misses. Use it only when you hold a node reference and need O(1) mid-list removal.

The One Comparator Pattern Worth Knowing Cold

For interviews, the lambda form is fastest to write:

// Sort by second element descending, break ties by first ascending
var data = new List<(int a, int b)> { (1,3), (2,3), (1,1) };
data.Sort((x, y) => {
    if (x.b != y.b) return y.b - x.b; // descending by b
    return x.a - y.a;                  // ascending by a
});

Two cautions. Subtraction comparers (a - b) overflow when values span the full int range. Use a.CompareTo(b) instead. Multi-key sorts that need stability belong to OrderBy(...).ThenBy(...), not Sort.

Build the Muscle for Interview Day

Knowing which collection to reach for is half the work. The other half is narrating the trade-off under pressure while someone watches. That combination is what gets documented in a write-up.

SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly these decisions: did you choose the right data structure, and did you explain it out loud?

Key Takeaways

List<T> is your default. It beats LinkedList in almost every scenario.
Dictionary indexer throws. Always use TryGetValue or GetValueOrDefault.
PriorityQueue is a min-heap. Negate or use a custom comparer for max behavior.
SortedDictionary and SortedSet are O(log n) red-black trees. SortedSet has no floor/ceiling; use GetViewBetween().Min/.Max.
List.Sort() is unstable. LINQ OrderBy is stable.
LinkedList wins only when you hold a direct node reference and need O(1) mid-list removal.

C# Data Structures: Quick Reference

List<T>: The Default Choice

Dictionary<K,V> and HashSet<T>: The O(1) Workhorses

The one trap that burns everyone

Sorted Collections: The Java Gap

SortedDictionary<K,V>

SortedSet<T>

SortedList<K,V> vs SortedDictionary<K,V>

Stack<T> and Queue<T>: Simple, One Caveat

LinkedList<T>: When to Actually Use It

PriorityQueue<TElement, TPriority>: The Heap