Arrays and Collections in C#

Arrays: Copy vs Share

Arrays are covered in depth in Arrays in C#; the one collection-level fact to carry forward is that assigning an array shares it, while Clone or Array.Copy duplicates it.

int[] data = { 5, 3, 8, 1 };
int[] alias = data;
int[] clone = (int[])data.Clone();

Array.Sort(data);

Console.WriteLine(string.Join(", ", alias));
Console.WriteLine(string.Join(", ", clone));
Console.WriteLine(ReferenceEquals(data, alias));

$ dotnet run
1, 3, 5, 8
5, 3, 8, 1
True

alias is just another name for the same array, so it shows the sorted order too. clone was copied before the sort and keeps the original order. Every collection below is a reference type with the same behaviour.

List<T>

List<T> is a growable array: Add appends, and removal methods shift the remaining elements left.

var names = new List<string> { "Alice", "Bob" };
names.AddRange(new[] { "Carol", "Dave", "Anna" });
names.Insert(1, "Ana");
Console.WriteLine($"{names.Count}: {string.Join(", ", names)}");

names.Remove("Bob");
names.RemoveAt(0);
int removed = names.RemoveAll(n => n.StartsWith("A"));
Console.WriteLine($"removed {removed}: {string.Join(", ", names)}");

Console.WriteLine(names.IndexOf("Dave"));
Console.WriteLine(names.Find(n => n.Length > 4));
Console.WriteLine(names.Find(n => n.Length > 10) ?? "(null)");

names.AddRange(new[] { "Bo", "Eve" });
names.Sort();
Console.WriteLine(string.Join(", ", names));
names.Sort((a, b) => a.Length.CompareTo(b.Length));
Console.WriteLine(string.Join(", ", names));

var big = new List<int>(capacity: 1000);
Console.WriteLine($"Count={big.Count} Capacity={big.Capacity}");

$ dotnet run
6: Alice, Ana, Bob, Carol, Dave, Anna
removed 2: Carol, Dave
1
Carol
(null)
Bo, Carol, Dave, Eve
Bo, Eve, Dave, Carol
Count=0 Capacity=1000

RemoveAll returns how many it removed — two here, Ana and Anna, since Alice was already gone via RemoveAt(0). Find returns null (the default for string) when nothing matches instead of throwing. The comparison lambda re-sorts by length. List.Sort is not stable, so if two names had the same length their relative order would not be guaranteed. capacity reserves space without adding items — Count is still 0.

Dictionary<TKey, TValue>

A hash map with O(1) average lookup; the indexer throws on a missing key, while TryGetValue and GetValueOrDefault do not.

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

scores["Carol"] = 91;
scores["Alice"] = 97;
Console.WriteLine(scores.TryAdd("Alice", 0));
Console.WriteLine(scores.TryAdd("Eve", 79));

if (scores.TryGetValue("Alice", out int alice))
    Console.WriteLine($"Alice: {alice}");
Console.WriteLine(scores.GetValueOrDefault("Faye", -1));

try { Console.WriteLine(scores["Faye"]); }
catch (KeyNotFoundException ex) { Console.WriteLine(ex.Message); }

scores.Remove("Bob");
foreach (var (name, score) in scores)
    Console.WriteLine($"{name}: {score}");

var grid = new Dictionary<(int, int), string> { [(0, 0)] = "Origin" };
Console.WriteLine(grid[(0, 0)]);

$ dotnet run
False
True
Alice: 97
-1
The given key 'Faye' was not present in the dictionary.
Alice: 97
Carol: 91
Eve: 79
Origin

Assigning through the indexer adds or overwrites (Alice became 97), while TryAdd refuses to overwrite and returns false. The exception message names the missing key, which is useful when it shows up in a log. Tuples make good composite keys because they compare by value.

HashSet<T>

A HashSet<T> keeps each value once. The ...With methods change the set in place; the LINQ operators return new sequences.

var set = new HashSet<string> { "apple", "banana" };
Console.WriteLine(set.Add("apple"));
Console.WriteLine(set.Add("cherry"));
Console.WriteLine(set.Count);

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

Console.WriteLine(string.Join(",", a.Intersect(b)));
Console.WriteLine(string.Join(",", a.Except(b)));
Console.WriteLine(string.Join(",", a));

a.UnionWith(b);
Console.WriteLine(string.Join(",", a));
Console.WriteLine(b.IsSubsetOf(a));

$ dotnet run
False
True
3
3,4
1,2
1,2,3,4
1,2,3,4,5,6
True

Add returns false for a duplicate instead of throwing, which makes it a one-line “have I seen this?” check. Intersect and Except left a untouched; UnionWith rewrote it, after which b is a subset of a.

Queue<T>, Stack<T> and PriorityQueue

A queue is first-in-first-out, a stack is last-in-first-out, and a priority queue dequeues the smallest priority first.

var queue = new Queue<string>(new[] { "A", "B", "C" });
Console.WriteLine($"{queue.Peek()} {queue.Dequeue()} {queue.Count}");

var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine($"{stack.Pop()} then [{string.Join(", ", stack)}]");

var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 3);
pq.Enqueue("high", 1);
pq.Enqueue("mid", 2);
while (pq.TryDequeue(out string? item, out int priority))
    Console.WriteLine($"{priority}: {item}");

$ dotnet run
A A 2
3 then [2, 1]
1: high
2: mid
3: low

Peek looks without removing, so both it and Dequeue return A. Enumerating a stack goes top-down, so after popping 3 it prints 2, 1. The priority queue came out in priority order, not insertion order — and lowest number first, because PriorityQueue is a min-heap.

IEnumerable<T> and Lazy Sequences

A method using yield return produces values one at a time, only as the caller asks for them.

IEnumerable<int> GetEvens(int max)
{
    for (int i = 0; i <= max; i += 2)
    {
        Console.Write($"[gen {i}] ");
        yield return i;
    }
}

var query = GetEvens(100).Where(n => n % 6 == 0).Take(2);
Console.WriteLine("query built");

foreach (int n in query)
    Console.Write($"<{n}> ");
Console.WriteLine();

$ dotnet run
query built
[gen 0] <0> [gen 2] [gen 4] [gen 6] <6> 

Nothing is generated when the query is built — “query built” prints first. Then the output interleaves: [gen 0] is immediately followed by <0>, because each value flows through Where and Take into the loop before the next one is produced. And the generator runs only until Take(2) has two matches: it stops at 6, never producing the other 47 even numbers up to 100. Enumerate query a second time and the generator runs again from scratch.

Sorted and Linked Collections

SortedDictionary keeps keys ordered; LinkedList inserts next to a node in O(1).

var sorted = new SortedDictionary<string, int>
{
    ["Zebra"] = 1,
    ["Apple"] = 2,
    ["Mango"] = 3,
};
Console.WriteLine(string.Join(", ", sorted.Keys));

var linked = new LinkedList<int>();
linked.AddLast(1);
linked.AddLast(2);
var node = linked.AddLast(3);
linked.AddBefore(node, 99);
linked.AddFirst(0);
Console.WriteLine(string.Join(" -> ", linked));

$ dotnet run
Apple, Mango, Zebra
0 -> 1 -> 2 -> 99 -> 3

The keys came out alphabetically regardless of insertion order. AddBefore needed the node handle returned by AddLast; that handle is what makes the insert O(1).

Collection Expressions and Read-Only Views

C# 12 collection expressions use [...] for any collection type, and .. spreads another collection in.

int[] arr = [1, 2, 3];
List<int> list = [.. arr, 4, 5];
Console.WriteLine(string.Join(", ", list));

IReadOnlyList<int> view = list.AsReadOnly();
list.Add(6);
Console.WriteLine(view.Count);

try { ((IList<int>)view).Add(7); }
catch (NotSupportedException ex) { Console.WriteLine(ex.Message); }

$ dotnet run
1, 2, 3, 4, 5
6
Collection is read-only.

AsReadOnly is a view, not a copy: after list.Add(6) the view reports six items. It stops callers from mutating through it — even a cast back to IList<int> fails at run time — but it does not freeze the underlying list.

Performance: List vs HashSet Lookups

The table below summarises the cost of common operations; the program after it measures the one that matters most in practice.

using System.Diagnostics;

var list = Enumerable.Range(0, 100_000).ToList();
var set = list.ToHashSet();
int hits = 0;

var sw = Stopwatch.StartNew();
for (int i = 0; i < 10_000; i++)
    if (list.Contains(99_999 - i)) hits++;
Console.WriteLine($"List.Contains:    {sw.ElapsedMilliseconds,5} ms ({hits} hits)");

hits = 0;
sw.Restart();
for (int i = 0; i < 10_000; i++)
    if (set.Contains(99_999 - i)) hits++;
Console.WriteLine($"HashSet.Contains: {sw.ElapsedMilliseconds,5} ms ({hits} hits)");

$ dotnet run
List.Contains:      240 ms (10000 hits)
HashSet.Contains:     1 ms (10000 hits)

Your millisecond numbers will differ, but the gap will not: each List.Contains scans up to 100,000 elements, while each HashSet.Contains hashes the value and checks one bucket. When a loop calls Contains on a list, converting it to a HashSet first is usually the cheapest speed-up available.

Practice

1. Word counts. Count how often each word appears in "the cat and the hat and the bat" using a Dictionary<string, int>, then print the words sorted by count descending.

var counts = new Dictionary<string, int>();
foreach (var word in "the cat and the hat and the bat".Split(' '))
    counts[word] = counts.GetValueOrDefault(word) + 1;

foreach (var (word, n) in counts.OrderByDescending(kv => kv.Value))
    Console.WriteLine($"{word}: {n}");

$ dotnet run
the: 3
and: 2
cat: 1
hat: 1
bat: 1

2. First duplicate. Using a HashSet<int>, print the first number that repeats in { 4, 7, 1, 7, 4, 9 }.

int[] nums = { 4, 7, 1, 7, 4, 9 };
var seen = new HashSet<int>();
foreach (int n in nums)
{
    if (!seen.Add(n))
    {
        Console.WriteLine($"first duplicate: {n}");
        break;
    }
}

$ dotnet run
first duplicate: 7

3. Max-first priority queue. Change the PriorityQueue example so the highest number comes out first.

var pq = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
pq.Enqueue("low", 3);
pq.Enqueue("high", 1);
pq.Enqueue("mid", 2);
while (pq.TryDequeue(out string? item, out int priority))
    Console.WriteLine($"{priority}: {item}");

$ dotnet run
3: low
2: mid
1: high

4. Balanced brackets. Use a Stack<char> to check whether "{[()]}" and "{[(])}" are balanced.

foreach (var s in new[] { "{[()]}", "{[(])}" })
    Console.WriteLine($"{s}: {Balanced(s)}");

static bool Balanced(string s)
{
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (pairs.ContainsValue(c)) stack.Push(c);
        else if (pairs.TryGetValue(c, out char open))
            if (stack.Count == 0 || stack.Pop() != open) return false;
    }
    return stack.Count == 0;
}

$ dotnet run
{[()]}: True
{[(])}: False