C# Collections Guide

Introduction

Collections are fundamental to .NET programming, providing efficient ways to store, organize, and manipulate groups of objects. Understanding which collection to use and their performance characteristics is essential for writing efficient code.

Table of Contents

• Collection Hierarchy
• Arrays
• List<T>
• Dictionary<TKey, TValue>
• HashSet<T>
• Queue<T> and Stack<T>
• LinkedList<T>
• SortedSet<T> and SortedDictionary
• Concurrent Collections
• Immutable Collections
• Collection Selection Guide
• Performance Comparison
• Interview Questions

Collection Hierarchy

                          IEnumerable<T>
                               │
                      ICollection<T>
                      /              \
              IList<T>            IDictionary<TKey,TValue>
                 │                        │
    ┌────────────┼────────────┐          │
    │            │            │          │
 List<T>    Array<T>    LinkedList<T>   Dictionary<TKey,TValue>
                                        SortedDictionary<TKey,TValue>

ISet<T>
    │
    ├── HashSet<T>
    └── SortedSet<T>

Key Interfaces

Arrays

Fixed-size, strongly-typed collections with the best performance for indexed access.

Declaration and Initialization

// Declaration styles
int[] numbers1 = new int[5];                    // Default values (0)
int[] numbers2 = new int[] { 1, 2, 3, 4, 5 };   // Explicit initialization
int[] numbers3 = { 1, 2, 3, 4, 5 };             // Implicit array creation
var numbers4 = new[] { 1, 2, 3, 4, 5 };         // Type inference

// Multi-dimensional arrays
int[,] matrix = new int[3, 3];                   // 2D array (rectangular)
int[,] grid = { { 1, 2 }, { 3, 4 }, { 5, 6 } };

// Jagged arrays (arrays of arrays)
int[][] jagged = new int[3][];
jagged[0] = new int[] { 1, 2 };
jagged[1] = new int[] { 3, 4, 5 };
jagged[2] = new int[] { 6 };

Array Operations

int[] arr = { 5, 2, 8, 1, 9 };

// Sorting
Array.Sort(arr);                    // In-place: [1, 2, 5, 8, 9]
Array.Reverse(arr);                 // In-place: [9, 8, 5, 2, 1]

// Searching
int index = Array.IndexOf(arr, 5);  // Returns index or -1
int binaryIndex = Array.BinarySearch(arr, 5);  // Requires sorted array

// Copying
int[] copy = new int[arr.Length];
Array.Copy(arr, copy, arr.Length);
int[] clone = (int[])arr.Clone();

// Resizing (creates new array)
Array.Resize(ref arr, 10);

// Fill with value
Array.Fill(arr, 0);                 // All elements = 0
Array.Fill(arr, 99, 2, 3);          // Elements 2-4 = 99

// Check existence
bool exists = Array.Exists(arr, x => x > 5);
int found = Array.Find(arr, x => x > 5);
int[] allFound = Array.FindAll(arr, x => x > 5);

Array Performance

List<T>

Dynamic array that automatically resizes. The most commonly used collection.

Basic Operations

// Creation
var list = new List<int>();                      // Empty
var list2 = new List<int> { 1, 2, 3 };           // With items
var list3 = new List<int>(100);                  // Pre-allocated capacity

// Adding elements
list.Add(1);                                     // Add at end
list.AddRange(new[] { 2, 3, 4 });               // Add multiple
list.Insert(0, 0);                              // Insert at index

// Removing elements
list.Remove(3);                                  // Remove first occurrence
list.RemoveAt(0);                               // Remove at index
list.RemoveAll(x => x > 5);                     // Remove matching
list.RemoveRange(0, 2);                         // Remove range
list.Clear();                                   // Remove all

// Accessing
int first = list[0];                            // Index access
int last = list[^1];                            // C# 8+: Last element
var slice = list[1..4];                         // C# 8+: Range (returns List<T>)

// Searching
bool contains = list.Contains(5);
int index = list.IndexOf(5);
int lastIndex = list.LastIndexOf(5);
int foundIndex = list.FindIndex(x => x > 5);
int found = list.Find(x => x > 5);              // First match
List<int> allFound = list.FindAll(x => x > 5);  // All matches
bool exists = list.Exists(x => x > 5);

// Sorting
list.Sort();                                    // In-place sort
list.Sort((a, b) => b.CompareTo(a));           // Descending
list.Reverse();

Capacity Management

var list = new List<int>();
Console.WriteLine(list.Capacity);  // 0

list.Add(1);
Console.WriteLine(list.Capacity);  // 4 (initial allocation)

// When Count exceeds Capacity, it doubles
// [0, 4, 8, 16, 32, 64, 128, ...]

// Pre-allocate to avoid resizing
var optimized = new List<int>(1000);  // Start with capacity 1000

// Trim excess
list.TrimExcess();  // Reduce capacity to match count

List Performance

Dictionary<TKey, TValue>

Hash table implementation for fast key-value lookups.

Basic Operations

// Creation
var dict = new Dictionary<string, int>();
var dict2 = new Dictionary<string, int>
{
    ["one"] = 1,
    ["two"] = 2,
    ["three"] = 3
};

// Adding/Updating
dict["key"] = 1;                              // Add or update
dict.Add("key2", 2);                          // Add only (throws if exists)
dict.TryAdd("key", 3);                        // Add if not exists (C# 7+)

// Retrieving
int value = dict["key"];                      // Throws if not found
bool found = dict.TryGetValue("key", out int val);  // Safe retrieval

// C# 8+: GetValueOrDefault
int valOrDefault = dict.GetValueOrDefault("missing", 0);

// Removing
dict.Remove("key");
dict.Remove("key", out int removed);          // C# 7+: Get removed value
dict.Clear();

// Checking
bool hasKey = dict.ContainsKey("key");
bool hasValue = dict.ContainsValue(1);        // O(n)!

// Iteration
foreach (var kvp in dict)
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");

foreach (var key in dict.Keys)
    Console.WriteLine(key);

foreach (var value in dict.Values)
    Console.WriteLine(value);

Custom Key Types

// When using custom types as keys, override GetHashCode and Equals
public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public override int GetHashCode()
    {
        return HashCode.Combine(Name, Age);  // C# 7+
    }

    public override bool Equals(object obj)
    {
        return obj is Person p &&
               Name == p.Name &&
               Age == p.Age;
    }
}

// Or use custom IEqualityComparer<T>
var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
dict["Key"] = 1;
Console.WriteLine(dict["KEY"]);  // Works! Returns 1

Dictionary Performance

HashSet<T>

Unordered collection of unique elements with fast lookup.

Basic Operations

// Creation
var set = new HashSet<int>();
var set2 = new HashSet<int> { 1, 2, 3, 3, 3 };  // Only stores 1, 2, 3

// Adding
set.Add(1);                 // Returns true if added
bool added = set.Add(1);    // Returns false (already exists)

// Removing
set.Remove(1);
set.RemoveWhere(x => x > 5);
set.Clear();

// Checking
bool contains = set.Contains(1);  // O(1)

Set Operations

var set1 = new HashSet<int> { 1, 2, 3, 4, 5 };
var set2 = new HashSet<int> { 4, 5, 6, 7, 8 };

// Union: All unique elements from both
set1.UnionWith(set2);           // set1 = {1, 2, 3, 4, 5, 6, 7, 8}

// Intersection: Common elements
set1.IntersectWith(set2);       // set1 = {4, 5}

// Except: In set1 but not in set2
set1.ExceptWith(set2);          // set1 = {1, 2, 3}

// Symmetric difference: In either but not both
set1.SymmetricExceptWith(set2); // set1 = {1, 2, 3, 6, 7, 8}

// Comparisons (non-modifying)
bool isSubset = set1.IsSubsetOf(set2);
bool isSuperset = set1.IsSupersetOf(set2);
bool overlaps = set1.Overlaps(set2);
bool setEquals = set1.SetEquals(set2);

HashSet Performance

Queue<T> and Stack<T>

Queue<T> (FIFO)

var queue = new Queue<string>();

// Enqueue (add to end)
queue.Enqueue("First");
queue.Enqueue("Second");
queue.Enqueue("Third");

// Dequeue (remove from front)
string first = queue.Dequeue();    // "First"

// Peek (view without removing)
string next = queue.Peek();        // "Second"

// Check before dequeue
if (queue.TryDequeue(out string item))
{
    Console.WriteLine(item);
}

// Iteration (doesn't remove)
foreach (var item in queue)
    Console.WriteLine(item);

Stack<T> (LIFO)

var stack = new Stack<string>();

// Push (add to top)
stack.Push("First");
stack.Push("Second");
stack.Push("Third");

// Pop (remove from top)
string top = stack.Pop();          // "Third"

// Peek (view without removing)
string next = stack.Peek();        // "Second"

// Safe operations
if (stack.TryPop(out string item))
{
    Console.WriteLine(item);
}

if (stack.TryPeek(out string peeked))
{
    Console.WriteLine(peeked);
}

Queue/Stack Performance

LinkedList<T>

Doubly-linked list for efficient insertion/removal at any position.

Basic Operations

var list = new LinkedList<string>();

// Adding
list.AddFirst("First");
list.AddLast("Last");

LinkedListNode<string> middle = list.AddAfter(list.First, "Middle");
list.AddBefore(middle, "Before Middle");

// Removing
list.RemoveFirst();
list.RemoveLast();
list.Remove("Middle");
list.Remove(middle);

// Navigation
LinkedListNode<string> node = list.First;
while (node != null)
{
    Console.WriteLine(node.Value);
    node = node.Next;
}

// Reverse navigation
node = list.Last;
while (node != null)
{
    Console.WriteLine(node.Value);
    node = node.Previous;
}

// Find nodes
LinkedListNode<string> found = list.Find("value");
LinkedListNode<string> lastFound = list.FindLast("value");

LinkedList Performance

When to Use LinkedList

// ✅ Good use case: Frequent insertions/removals in middle
var playlist = new LinkedList<Song>();
var currentSong = playlist.First;
// Insert new song after current - O(1)
playlist.AddAfter(currentSong, new Song("New Song"));

// ❌ Bad use case: Random access
// LinkedList has no indexer - must traverse

SortedSet and SortedDictionary

SortedSet<T>

Maintains elements in sorted order using a red-black tree.

var sortedSet = new SortedSet<int> { 5, 2, 8, 1, 9 };
// Automatically sorted: [1, 2, 5, 8, 9]

// Range operations
var subset = sortedSet.GetViewBetween(2, 8);  // [2, 5, 8]

// Min/Max - O(log n)
int min = sortedSet.Min;
int max = sortedSet.Max;

// Custom comparer
var descending = new SortedSet<int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));

SortedDictionary<TKey, TValue>

Maintains key-value pairs sorted by key.

var sortedDict = new SortedDictionary<string, int>
{
    ["Charlie"] = 3,
    ["Alice"] = 1,
    ["Bob"] = 2
};
// Keys sorted: Alice, Bob, Charlie

foreach (var kvp in sortedDict)
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
// Alice: 1, Bob: 2, Charlie: 3

Sorted Collections Performance

Concurrent Collections

Thread-safe collections for multi-threaded scenarios.

ConcurrentDictionary<TKey, TValue>

var dict = new ConcurrentDictionary<string, int>();

// Thread-safe operations
dict.TryAdd("key", 1);
dict.TryRemove("key", out int removed);
dict.TryUpdate("key", newValue: 2, comparisonValue: 1);

// Atomic get-or-add
int value = dict.GetOrAdd("key", 1);
int computed = dict.GetOrAdd("key", key => ComputeValue(key));

// Atomic add-or-update
int result = dict.AddOrUpdate(
    "key",
    addValue: 1,
    updateValueFactory: (key, oldValue) => oldValue + 1
);

ConcurrentQueue<T> / ConcurrentStack<T>

var queue = new ConcurrentQueue<int>();
queue.Enqueue(1);
if (queue.TryDequeue(out int item)) { }
if (queue.TryPeek(out int next)) { }

var stack = new ConcurrentStack<int>();
stack.Push(1);
stack.PushRange(new[] { 2, 3, 4 });
if (stack.TryPop(out int top)) { }
if (stack.TryPeek(out int peek)) { }

ConcurrentBag<T>

Unordered collection optimized for producer-consumer scenarios.

var bag = new ConcurrentBag<int>();
bag.Add(1);
if (bag.TryTake(out int item)) { }
if (bag.TryPeek(out int peek)) { }

BlockingCollection<T>

Bounded collection with blocking add/take.

// Producer-consumer pattern
var collection = new BlockingCollection<int>(boundedCapacity: 100);

// Producer thread
Task.Run(() =>
{
    for (int i = 0; i < 1000; i++)
    {
        collection.Add(i);  // Blocks if full
    }
    collection.CompleteAdding();
});

// Consumer thread
Task.Run(() =>
{
    foreach (var item in collection.GetConsumingEnumerable())
    {
        Process(item);  // Blocks until item available
    }
});

Immutable Collections

Collections that cannot be modified after creation (from System.Collections.Immutable).

using System.Collections.Immutable;

// ImmutableList<T>
var list = ImmutableList<int>.Empty;
var list2 = list.Add(1);        // Returns new list
var list3 = list2.AddRange(new[] { 2, 3 });

// ImmutableDictionary<TKey, TValue>
var dict = ImmutableDictionary<string, int>.Empty;
var dict2 = dict.Add("key", 1);
var dict3 = dict2.SetItem("key", 2);  // Update returns new dict

// ImmutableHashSet<T>
var set = ImmutableHashSet<int>.Empty;
var set2 = set.Add(1).Add(2).Add(3);

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

When to Use Immutable Collections

// ✅ Thread safety without locks
public class Cache
{
    private ImmutableDictionary<string, Data> _cache =
        ImmutableDictionary<string, Data>.Empty;

    public void Add(string key, Data data)
    {
        // Atomic replace, thread-safe
        _cache = _cache.Add(key, data);
    }
}

// ✅ Snapshots and versioning
public ImmutableList<Change> History { get; private set; } =
    ImmutableList<Change>.Empty;

public void RecordChange(Change change)
{
    History = History.Add(change);  // Previous versions preserved
}

Collection Selection Guide

Decision Tree

Need key-value pairs?
├── Yes: Need sorted keys?
│   ├── Yes: SortedDictionary<K,V>
│   └── No: Thread-safe?
│       ├── Yes: ConcurrentDictionary<K,V>
│       └── No: Dictionary<K,V>
└── No: Need unique elements?
    ├── Yes: Need sorted?
    │   ├── Yes: SortedSet<T>
    │   └── No: HashSet<T>
    └── No: Need specific order?
        ├── FIFO: Queue<T> or ConcurrentQueue<T>
        ├── LIFO: Stack<T> or ConcurrentStack<T>
        ├── Insertion order with fast insert/remove: LinkedList<T>
        └── Index access: List<T> or Array

Quick Reference Table

Performance Comparison

Time Complexity Summary

* Amortized (O(n) on resize) ** O(1) if you have the node reference

Memory Overhead

Interview Questions

1. What’s the difference between List<T> and LinkedList<T>?

Answer:

• List<T>: Uses dynamic array internally. O(1) index access, O(n) insert/remove in middle.
• LinkedList<T>: Doubly-linked nodes. O(n) index access, O(1) insert/remove at known node.

Use List<T> for most cases. Use LinkedList<T> when you frequently insert/remove from middle and have node references.

2. How does Dictionary<K,V> achieve O(1) lookup?

Answer: Uses hash table. When adding:

1. Computes hash code of key using GetHashCode()
2. Maps hash to bucket index: index = hash % bucketCount
3. Stores entry in bucket (handles collisions with linked list or linear probing)

Retrieval reverses this: hash key → find bucket → compare keys.

Performance degrades to O(n) with poor hash function causing many collisions.

3. When should you use HashSet<T> instead of List<T>?

Answer: Use HashSet<T> when:

• You need unique elements only
• You frequently check Contains() (O(1) vs O(n))
• You need set operations (Union, Intersect, Except)

Use List<T> when:

• Order matters
• Duplicates are allowed
• You need index access

4. What is the capacity vs count of a List<T>?

Answer:

• Count: Number of elements actually in the list
• Capacity: Size of internal array (how many elements can fit before resize)

When Count exceeds Capacity, the list allocates a new array double the size and copies elements. Pre-allocating capacity with new List<T>(expectedSize) avoids this overhead.

5. Which collection would you use for a producer-consumer scenario?

Answer:

• Single-threaded: Queue<T>
• Multi-threaded: ConcurrentQueue<T> or BlockingCollection<T>

BlockingCollection<T> is preferred when you need blocking semantics (consumer waits for items) or bounded capacity (producer blocks when full).

6. What’s the difference between SortedDictionary and SortedList?

Answer:

• SortedDictionary<K,V>: Red-black tree. O(log n) operations. Better for frequent insertions/deletions.
• SortedList<K,V>: Sorted array. O(n) insert/delete, O(log n) lookup. Better memory usage, faster iteration.

Use SortedDictionary for dynamic data, SortedList for mostly static data with frequent lookups.

Sources

• Microsoft Docs: Collections
• Microsoft Docs: Generic Collections
• Microsoft Docs: Thread-Safe Collections
• Microsoft Docs: Immutable Collections