Collections

Definition

Collections in C# are data structures for storing, organizing, and managing groups of related objects. The .NET Base Class Library provides collections in the System.Collections.Generic namespace, offering type-safe, generic versions of classic data structures.

using System.Collections.Generic;

List<int> numbers = [1, 2, 3, 4, 5]; // Collection expression (C# 12)
Dictionary<string, int> ages = new() { ["Alice"] = 30, ["Bob"] = 25 };
HashSet<int> unique = [1, 2, 3];

Core Concepts

Arrays

Arrays are fixed-size, zero-indexed, and stored in contiguous memory. They are the most fundamental collection type in C#.

// Declaration and initialization
int[] nums = new int[5];           // [0, 0, 0, 0, 0]
int[] primes = [2, 3, 5, 7, 11];  // Collection expression (C# 12)
string[] names = ["Alice", "Bob"];

// Multi-dimensional arrays
int[,] grid = new int[3, 4];           // 3 rows, 4 columns
int[,] matrix = { { 1, 2 }, { 3, 4 } };

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

mẹo

Use arrays when the size is known at creation and does not change. They offer the best performance due to contiguous memory layout.

List<T>

A dynamic array that automatically resizes. The most commonly used collection in C#.

List<int> list = [3, 1, 4, 1, 5];

list.Add(9);                    // Append to end
list.AddRange([2, 6, 5]);      // Add multiple
list.Insert(0, 99);             // Insert at index
list.Remove(1);                 // Remove first occurrence of 1
list.RemoveAt(0);               // Remove by index
list.Sort();                    // Sort in place

bool has = list.Contains(4);            // O(n) search
int? found = list.Find(x => x > 3);     // First match
List<int> all = list.FindAll(x => x > 2); // All matches

int count = list.Count;     // Actual number of elements
int cap = list.Capacity;    // Allocated internal array size

cảnh báo

Count returns the number of elements. Capacity returns the size of the internal array. Capacity >= Count always holds.

Dictionary<TKey, TValue>

Stores key-value pairs with O(1) average lookup by key. Keys must be unique.

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

// Add and retrieve
scores["Charlie"] = 72;
int aliceScore = scores["Alice"];        // 95 (throws if key missing)

// Safe retrieval
if (scores.TryGetValue("Bob", out int bobScore))
{
    Console.WriteLine(bobScore); // 87
}

// Check existence
bool hasKey = scores.ContainsKey("Alice");
bool hasVal = scores.ContainsValue(87); // O(n)

// Iteration
foreach (KeyValuePair<string, int> kvp in scores)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}

HashSet<T>

Stores unique elements with O(1) average lookup. Supports mathematical set operations.

HashSet<int> setA = [1, 2, 3, 4, 5];
HashSet<int> setB = [4, 5, 6, 7, 8];

setA.Add(6);                         // Add (ignored if exists)
setA.UnionWith(setB);                // A = A U B
setA.IntersectWith(setB);            // A = A ^ B
setA.ExceptWith(setB);               // A = A - B
bool subset = setA.IsSubsetOf(setB); // Is A a subset of B?
bool overlap = setA.Overlaps(setB);  // Any common elements?

Queue<T>

FIFO (First-In, First-Out) data structure.

var queue = new Queue<string>();

queue.Enqueue("first");   // Add to back
queue.Enqueue("second");

string front = queue.Peek();          // View front without removing: "first"
string dequeued = queue.Dequeue();    // Remove and return front: "first"

// Safe dequeue
if (queue.TryDequeue(out string? item))
{
    Console.WriteLine(item); // "second"
}

Stack<T>

LIFO (Last-In, First-Out) data structure.

var stack = new Stack<int>();

stack.Push(1);   // Add to top
stack.Push(2);
stack.Push(3);

int top = stack.Peek();       // View top without removing: 3
int popped = stack.Pop();     // Remove and return top: 3

// Safe pop
if (stack.TryPop(out int item))
{
    Console.WriteLine(item); // 2
}

Non-Generic Collections (Legacy)

The System.Collections namespace provides non-generic collections that store elements as object. Prefer the generic versions in System.Collections.Generic for type safety and to avoid boxing/unboxing overhead.

Queue and Stack (Non-Generic)

using System.Collections; // non-generic namespace

// Non-generic Queue — stores object, requires casting
Queue queue = new Queue();
queue.Enqueue(42);
int val = (int)queue.Dequeue(); // explicit cast needed

// Non-generic Stack — stores object, requires casting
Stack stack = new Stack();
stack.Push(99);
int top = (int)stack.Pop(); // explicit cast needed

cảnh báo

Always prefer Queue<T> and Stack<T> over their non-generic counterparts. The non-generic versions store object, causing boxing for value types and requiring runtime casts that can fail.

Hashtable

A non-generic key-value collection based on the hash code of keys. Has no generic equivalent in this namespace — use Dictionary<TKey, TValue> instead.

using System.Collections;

Hashtable hashTable = new Hashtable();
hashTable.Add("key1", 174);
hashTable.Remove("key1");
bool hasKey = hashTable.ContainsKey("key1");
bool hasVal = hashTable.ContainsValue(174);

ICollection keys = hashTable.Keys;
ICollection values = hashTable.Values;

Feature	Hashtable	Dictionary<TKey, TValue>
Namespace	System.Collections	System.Collections.Generic
Type safety	None (stores object)	Full compile-time checking
Boxing	Yes, for value types	No
Null key	Allows single null key	Throws ArgumentNullException
Modern alternative	Use Dictionary<TKey, TValue>	Recommended

LinkedList<T>

A doubly-linked list where each node holds a reference to the previous and next node. Efficient insertions and removals at known positions.

var linked = new LinkedList<string>();

LinkedListNode<string> node1 = linked.AddFirst("A");
LinkedListNode<string> node2 = linked.AddLast("B");
linked.AddBefore(node2, "AB");
linked.AddAfter(node1, "A2");

linked.Remove("AB");              // Remove by value
linked.Remove(linked.First);      // Remove node reference

LinkedListNode<string>? found = linked.Find("A2"); // Find first occurrence

ReadOnlyCollection<T> and ImmutableList<T>

using System.Collections.ObjectModel;
using System.Collections.Immutable;

// ReadOnlyCollection — wrapper, prevents modification via the wrapper
List<int> source = [1, 2, 3];
ReadOnlyCollection<int> readOnly = source.AsReadOnly();

// ImmutableList — truly immutable, creates new instances on "modification"
ImmutableList<int> imm = ImmutableList.Create(1, 2, 3);
ImmutableList<int> added = imm.Add(4); // new list, imm unchanged

Code Examples

Collection Expressions (C# 12)

// Inline initialization
int[] arr = [1, 2, 3];
List<string> names = ["Alice", "Bob"];
Span<int> span = [10, 20, 30];

// Spread operator
int[] a = [1, 2];
int[] b = [3, 4];
int[] combined = [..a, ..b]; // [1, 2, 3, 4]

Iterating and Modifying Safely

// WRONG: modifying during foreach throws InvalidOperationException
// foreach (var item in list) { list.Remove(item); } // EXCEPTION

// Option 1: iterate backward
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] < 0) list.RemoveAt(i);
}

// Option 2: use RemoveAll
list.RemoveAll(x => x < 0);

// Option 3: create a new filtered list
List<int> filtered = list.Where(x => x >= 0).ToList();

When to Use — Decision Matrix

Need	Use	Lookup	Insert/Delete
Fixed-size, indexed data	T[] (array)	O(1)	N/A
Dynamic list, frequent add/remove at end	List<T>	O(1) index / O(n) search	O(1) append / O(n) middle
Key-value lookup	Dictionary<TKey, TValue>	O(1) by key	O(1) amortized
Unique elements, set operations	HashSet<T>	O(1)	O(1) amortized
FIFO processing (task queues)	Queue<T>	O(1) front/back	O(1) enqueue/dequeue
LIFO processing (undo/redo, parsing)	Stack<T>	O(1) top	O(1) push/pop
Frequent insert/remove in middle	LinkedList<T>	O(n)	O(1) at known node
Read-only public API	ReadOnlyCollection<T>	O(1) index	N/A
True immutability, thread-safe sharing	ImmutableList<T>	O(1) index	O(n) returns new

Common Pitfalls

1. Modifying a collection during foreach — Throws InvalidOperationException. Use a for loop (backward), RemoveAll, or LINQ to create a new collection.

2. Using Count vs Any() — list.Count > 0 accesses the Count property (fast for List<T> but not for IEnumerable<T> which triggers full enumeration). Prefer list.Any() from LINQ for general IEnumerable<T>.

3. Dictionary key collisions — Add throws ArgumentException if the key already exists. Use the indexer dict[key] = value to overwrite, or TryAdd to safely attempt insertion.

4. Removing from List<T> in a forward loop — Removing shifts remaining elements left, causing the next element to be skipped. Iterate backward or use RemoveAll.

5. Using List<T> for frequent middle insertions — List<T> is backed by an array, so inserting in the middle is O(n). Use LinkedList<T> for this pattern.

Key Takeaways

• Arrays are fixed-size and fastest for indexed access
• List<T> is the default choice for dynamic collections
• Dictionary<TKey, TValue> provides O(1) key-based lookup
• HashSet<T> ensures uniqueness and supports set operations
• Always iterate backward or use RemoveAll when removing elements during iteration
• Use Count for collections that implement ICollection<T>, Any() for IEnumerable<T>
• Collection expressions ([...]) provide clean initialization syntax in C# 12+

Interview Questions

Q: What is the difference between an array and List<T>? A: Arrays have a fixed size defined at creation and cannot grow or shrink. List<T> is a dynamic array that automatically resizes its internal array when capacity is exceeded. Arrays offer slightly better performance for fixed-size scenarios; List<T> offers flexibility with Add, Remove, Insert, and other methods.

Q: What is the difference between Dictionary<TKey, TValue> and HashSet<T>? A: Dictionary stores key-value pairs and retrieves values by key. HashSet stores unique keys only (no values). Both use hash-based lookup (O(1) average). Use Dictionary when you need to associate data with a key; use HashSet when you only need to test membership.

Q: What is the time complexity of Dictionary lookup? A: Average O(1) for TryGetValue, ContainsKey, and indexer access. Worst case O(n) if there are many hash collisions, but .NET uses a good hash algorithm and resizing strategy to keep collisions minimal.

Q: How do you safely iterate and modify a collection at the same time? A: Iterate backward with a for loop (so index shifts do not cause skips), use RemoveAll for conditional removal, or build a new filtered collection with LINQ. Never modify a collection inside a foreach loop.

References

• Tour of C# — Collections
• C# Programming Guide — Collections
• W3Schools C# Collections
• Programiz C# Collections