List, Dictionary, HashSet

Arrays are of fixed size, but in real programs you will often need collections of varying size. C# has pre-created various data structures in the System.Collections.Generic namespace.

Learning Objectives

• Use the add, delete, search, and sort operations of List<T>
• Store and search key-value pairs with Dictionary<TKey, TValue>
• Perform duplicate removal and set operations (union/intersection) with HashSet<T>
• Know the difference between Queue<T> (FIFO) and Stack<T> (LIFO)

Key concepts

1) List<T> — variable-length lists

List<int> nums = [10, 20, 30];        //Collection type OK
nums.Add(40);
nums.Remove(20);     //remove first by value
nums.RemoveAt(0);    //remove by index
bool has = nums.Contains(30);
nums.Sort();

• Accessible like an array with indexer nums[i].
• Automatically expands the array internally.

2) Dictionary<TKey, TValue> — key-value mapping

Dictionary<string, int> ages = new()
{
    ["exponent"] = 20,
    ["minho"] = 25
};

ages["Seoyeon"] = 22;                 //Add or Renew
if (ages.TryGetValue("minho", out int age))
{
    Console.WriteLine(age);
}

• The key must be unique, and an exception will be thrown if Add is used twice with the same key.
• TryGetValue is a safe query pattern.

3) HashSet<T> — sets without duplicates

HashSet<string> a = ["apple", "ship", "persimmon"];
HashSet<string> b = ["ship", "persimmon", "grapes"];

a.UnionWith(b);      //union (a is changed)
a.IntersectWith(b);  //intersection

• Add/Search is very fast, with an average of O(1).
• Order is not guaranteed.

4) Queue<T> and Stack<T>

• Queue<T> (First-in-first-out, FIFO): Input with Enqueue and take out with Dequeue. Parable of people waiting in line.
• Stack<T> (last in, first out, LIFO): Input with Push and take out with Pop. Parable of a pile of books.
• In both cases, you can only preview the value to be pulled out next with Peek.

See as example

Example 1 — ListBasics : Basics of List<T>

List<int> nums = [10, 20, 30];

nums.Add(40);
nums.Remove(20);

Console.WriteLine($"Including 30? {nums.Contains(30)}");
Console.WriteLine($"Count: {nums.Count}");

nums.Sort();
Console.WriteLine($"Sort: [{string.Join(", ", nums)}]");

Execution result

Including 30? True
Count: 3
Sort: [10, 30, 40]

Memo: List<T>.Count has the same role as Length in the array. Remove is erased by value, and RemoveAt is erased by index.

Example 2 — DictBasics: word counter

string text = "apple banana apple cherry banana apple";
Dictionary<string, int> counts = new();

foreach (string word in text.Split(' '))
{
    counts[word] = counts.GetValueOrDefault(word, 0) + 1;
}

foreach (var (word, count) in counts)
{
    Console.WriteLine($"{word}: {count}");
}

Execution result

apple: 3
banana: 2
cherry: 1

Memo: GetValueOrDefault(key, default) is a convenient method that returns a default value if the key does not exist. The var (k, v) decomposition syntax of foreach works naturally in .NET 8.

Example 3 — HashSet: Deduplication and set operations

string[] input = ["apple", "ship", "apple", "persimmon", "ship"];
HashSet<string> unique = new(input);
Console.WriteLine($"Remove duplicates: [{string.Join(", ", unique)}]");

HashSet<string> a = ["apple", "ship", "persimmon"];
HashSet<string> b = ["ship", "persimmon", "grapes"];

HashSet<string> intersection = new(a);
intersection.IntersectWith(b);
Console.WriteLine($"Intersection: [{string.Join(", ", intersection)}]");

HashSet<string> union = new(a);
union.UnionWith(b);
Console.WriteLine($"Union: [{string.Join(", ", union)}]");

Execution result

Remove duplicates: [apple, pear, persimmon]
Intersection: [pear, persimmon]
Union: [apple, pear, persimmon, grape]

Memo: To preserve the original, copy it to new HashSet<T>(original) and then call the set operation. IntersectWith directly modifies the calling side.

Example 4 — QueueStack: FIFO and LIFO

Queue<string> queue = new();
queue.Enqueue("first");
queue.Enqueue("second");
queue.Enqueue("third");

Console.WriteLine("=== Queue (FIFO) ===");
while (queue.Count > 0)
{
    Console.WriteLine(queue.Dequeue());
}

Stack<string> stack = new();
stack.Push("first");
stack.Push("second");
stack.Push("third");

Console.WriteLine("=== Stack (LIFO) ===");
while (stack.Count > 0)
{
    Console.WriteLine(stack.Pop());
}

Execution result

=== Queue (FIFO) ===
first
second
third
=== Stack (LIFO) ===
third
second
first

Note: Queue appears in the order it came in, and Stack appears backwards. Back in web browser = Stack, printer job queue = Queue.

Common Mistakes

1. Call Add twice on the same key of Dictionary → ArgumentException. Update to dict[key] = value.
2. Call Dequeue/Pop from empty Queue/Stack → InvalidOperationException. Check Count > 0 in advance.
3. While traversing List<T> to foreach, Add/Remove → collection change exception. for Reverse traversal or use new list.
4. The illusion that HashSet<T> keeps order — order is not guaranteed. If you need sorting, use SortedSet<T>.
5. Remove(value) of List<T> removes only the first match. To clear them all, click RemoveAll(predicate).

Cleanup

• List<T> is a variable length array, the first choice in most "multiple" situations.
• Dictionary<K,V> is key-value mapping, lookup average O(1).
• HashSet<T> removes duplicates and sets operations.
• Queue<T>(FIFO), Stack<T>(LIFO) are used in situations where processing order is important.

Try it yourself

cd src/ListBasics
dotnet run

cd ../DictBasics
dotnet run

cd ../HashSet
dotnet run

cd ../QueueStack
dotnet run