C# Collections: Choosing the Right Data Structure Every Time

Why Collections Matter in Interviews

The question "why did you use a List here?" is a junior trap. Seniors answer with tradeoffs: access patterns, allocation costs, thread safety, and growth characteristics. This guide gives you those answers.

The Collection Hierarchy

IEnumerable          — iterate only (foreach)
  └─ ICollection     — + Count, Add, Remove, Contains
       └─ IList      — + indexed access (this[i])
            ├─ List
            └─ T[]      (Array — implicitly implements IList)

IDictionary        — key/value pairs
  └─ Dictionary

ISet                 — unique elements
  └─ HashSet
  └─ SortedSet

Rule of thumb for method parameters: accept the narrowest interface that covers your needs.

// Too broad — allows any enumerable but forces multiple enumeration
void Process(IEnumerable<Order> orders) { }

// Better — signals you need count and indexed access
void Process(IList<Order> orders) { }

// Best — only iterating? say so
void Process(IReadOnlyList<Order> orders) { }

Array vs List<T>

| Feature | T[] (Array) | List<T> | |---|---|---| | Fixed size | Yes | No (grows) | | Memory | Contiguous, one allocation | Contiguous, may reallocate | | Access | O(1) | O(1) | | Insert/remove at middle | O(n) | O(n) | | Append | Not supported | O(1) amortized | | Boxing (value types) | None | None | | SIMD / Span support | Native | Via CollectionsMarshal |

Use Array when:

Size is known and fixed
You need maximum memory efficiency
Working with Span<T> / Memory<T> / interop

Use List<T> when:

Size varies at runtime
You need Add/Remove
Building collections incrementally

// Prefer array for fixed data
var primes = new int[] { 2, 3, 5, 7, 11 };

// Use List for dynamic data
var results = new List<string>();
foreach (var item in source)
    if (Matches(item)) results.Add(item.Name);

Pre-allocate List capacity

// BAD — List doubles its internal array multiple times as items are added
var list = new List<int>();
for (int i = 0; i < 10_000; i++) list.Add(i);

// GOOD — single allocation, no copying
var list = new List<int>(10_000);
for (int i = 0; i < 10_000; i++) list.Add(i);

Span<T> and Memory<T>

Span<T> is a stack-allocated view over any contiguous memory — arrays, stackalloc, or unmanaged memory. Zero allocation, zero copying.

// Slice without allocation
int[] array = { 1, 2, 3, 4, 5 };
Span<int> slice = array.AsSpan(1, 3);  // [2, 3, 4] — no copy
slice[0] = 99;                          // mutates original: array = [1, 99, 3, 4, 5]

// String slicing without allocation
ReadOnlySpan<char> name = "Alice Smith".AsSpan(0, 5); // "Alice"

// Stack allocation for small buffers
Span<byte> buffer = stackalloc byte[256]; // no heap allocation

Limitations of Span<T>:

Cannot be stored on the heap (can't be a field, not usable in async methods)
Use Memory<T> when you need heap storage or async

// Memory<T> — heap-based, usable in async
public async Task ProcessAsync(Memory<byte> buffer, CancellationToken ct)
{
    var written = await stream.ReadAsync(buffer, ct);
    var filled = buffer.Slice(0, written);
    // process filled
}

Dictionary<TKey, TValue>

Hash-based key/value store. O(1) average for get, set, contains.

var scores = new Dictionary<string, int>();
scores["Alice"] = 95;
scores["Bob"]   = 87;

// Safe access
if (scores.TryGetValue("Alice", out int score))
    Console.WriteLine(score);

// Default if missing (.NET 6+)
var val = scores.GetValueOrDefault("Charlie", 0);

// Populate from collection
var lookup = products.ToDictionary(p => p.Id, p => p);

Dictionary Internals

Dictionary uses an array of buckets. Each bucket points to a chain of entries with the same hash. When load factor exceeds threshold (~0.72), it rehashes — allocates a new array and recopies all entries.

// Pre-size to avoid rehashing
var map = new Dictionary<string, int>(capacity: 1000);

When Dictionary Gets Slow

If your TKey has a poor GetHashCode (many collisions), all lookups degrade to O(n).

// Custom key — always override both
public record ProductKey(int CategoryId, int ProductId)
{
    // record auto-generates correct GetHashCode and Equals
}

HashSet<T>

Unordered set of unique values. O(1) add, remove, contains.

var seen   = new HashSet<int>();
var unique = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

// Fast "already processed?" check
foreach (var id in ids)
{
    if (!seen.Add(id)) continue; // Add returns false if already present
    Process(id);
}

// Set operations
var a = new HashSet<int> { 1, 2, 3 };
var b = new HashSet<int> { 2, 3, 4 };

a.UnionWith(b);        // a = {1,2,3,4}
a.IntersectWith(b);    // a = {2,3}
a.ExceptWith(b);       // a = {1}
bool overlap = a.Overlaps(b);
bool subset  = a.IsSubsetOf(b);

Use HashSet when you need:

Fast duplicate detection
Set operations (union, intersect)
Membership tests without caring about order

SortedDictionary and SortedSet

Red-black tree based. O(log n) operations but maintains sorted order.

var sorted = new SortedDictionary<string, int>();
sorted["banana"] = 2;
sorted["apple"]  = 1;
sorted["cherry"] = 3;

// Keys always in alphabetical order
foreach (var kv in sorted) Console.WriteLine(kv.Key); // apple, banana, cherry

// Range queries — get all keys in [B, C)
var range = sorted.Keys.SkipWhile(k => k < "b").TakeWhile(k => k < "c");

Use SortedDictionary when:

You need key iteration in sorted order
You do range queries

Queue<T> and Stack<T>

// Queue — FIFO (first in, first out)
var queue = new Queue<string>();
queue.Enqueue("first");
queue.Enqueue("second");
var next = queue.Dequeue();   // "first"
var peek = queue.Peek();      // "second" — doesn't remove

// Stack — LIFO (last in, first out)
var stack = new Stack<string>();
stack.Push("a");
stack.Push("b");
var top  = stack.Pop();   // "b"
var peek = stack.Peek();  // "a"

Use Queue for: task queues, BFS, message buffering Use Stack for: undo history, DFS, expression evaluation, call simulation

LinkedList<T>

Doubly-linked. O(1) insert/remove anywhere given a node reference. O(n) indexed access.

var list = new LinkedList<int>();
var node = list.AddLast(1);
list.AddLast(2);
list.AddBefore(node, 0);   // O(1) insert before a known node

// Use case: LRU cache
// Move accessed node to head in O(1) — not possible with List

Use LinkedList when:

Frequent insertion/removal at arbitrary positions
You hold references to nodes (LRU cache, deque)

Concurrent Collections

Thread-safe collections from System.Collections.Concurrent.

// Thread-safe dictionary — lockless for reads
var cache = new ConcurrentDictionary<int, string>();
cache.TryAdd(1, "one");
cache.GetOrAdd(2, id => FetchFromDb(id));     // atomic get-or-create
cache.AddOrUpdate(1, "ONE", (k, v) => "ONE"); // atomic update

// Thread-safe queue — producer/consumer
var queue = new ConcurrentQueue<WorkItem>();
queue.Enqueue(item);
if (queue.TryDequeue(out var work)) Process(work);

// Blocking collection — producer blocks when full, consumer blocks when empty
var channel = new BlockingCollection<WorkItem>(boundedCapacity: 100);

// Producer
channel.Add(item); // blocks if at capacity

// Consumer (on another thread)
foreach (var item in channel.GetConsumingEnumerable(ct))
    Process(item);

For modern producer/consumer pipelines, prefer Channel<T> over BlockingCollection:

var channel = Channel.CreateBounded<WorkItem>(new BoundedChannelOptions(100)
{
    FullMode = BoundedChannelFullMode.Wait
});

// Producer
await channel.Writer.WriteAsync(item, ct);
channel.Writer.Complete(); // signal no more items

// Consumer
await foreach (var item in channel.Reader.ReadAllAsync(ct))
    await ProcessAsync(item);

ImmutableCollections

From System.Collections.Immutable. Every modification returns a new collection — thread-safe, shareable.

var original = ImmutableList.Create(1, 2, 3);
var modified = original.Add(4);    // returns new list, original unchanged

var map = ImmutableDictionary<string, int>.Empty
    .Add("a", 1)
    .Add("b", 2);

// Builder pattern for bulk construction (efficient)
var builder = ImmutableList.CreateBuilder<int>();
for (int i = 0; i < 1000; i++) builder.Add(i);
var immutable = builder.ToImmutable();

Choosing the Right Collection

| Scenario | Collection | |---|---| | Ordered list, dynamic size | List<T> | | Fixed-size, high performance | T[] | | Slice without copy | Span<T> / Memory<T> | | Key/value fast lookup | Dictionary<K,V> | | Unique values | HashSet<T> | | Sorted iteration | SortedDictionary<K,V> / SortedSet<T> | | FIFO task queue | Queue<T> | | LIFO undo/parse | Stack<T> | | Fast mid-list insert | LinkedList<T> | | Thread-safe key/value | ConcurrentDictionary<K,V> | | Producer/consumer | Channel<T> | | Share across threads (read) | ImmutableList<T> |

Interview Questions

Q: What is the difference between IEnumerable<T>, ICollection<T>, and IList<T>? IEnumerable<T> supports only forward iteration. ICollection<T> adds Count, Add, Remove, Contains. IList<T> adds indexed access (this[i]). Use the narrowest interface that satisfies your needs to keep APIs flexible.

Q: Why would you use HashSet<T> instead of List<T> for membership checks? List<T>.Contains is O(n) — it scans every element. HashSet<T>.Contains is O(1) average. For any "have I seen this?" check on large collections, HashSet<T> is significantly faster.

Q: What is Span<T> and why is it useful? A stack-allocated struct that provides a view over contiguous memory (array, stack-alloc, or native) without copying. Eliminates allocations for slicing and substring operations — important for high-throughput parsing and buffer processing.

Q: When would you use ConcurrentDictionary vs Dictionary with a lock? ConcurrentDictionary uses lock striping — only the affected bucket is locked, allowing high concurrency. A lock on a plain Dictionary serializes all operations. Use ConcurrentDictionary when multiple threads read/write frequently; use lock + Dictionary when you need atomic multi-step operations (read-modify-write as a unit).

Q: What is Channel<T> and how does it differ from BlockingCollection<T>? Both implement bounded producer/consumer queues. BlockingCollection uses blocking threads. Channel<T> is fully async — producers and consumers use await, freeing threads while waiting. In async code (ASP.NET Core, modern .NET), always prefer Channel<T>.