Collections in C#: List, Dictionary, HashSet, Queue and Stack

Lesson 9 of 15 · C#

An array has a fixed length. Collections from the namespace System.Collections.Generic grow and shrink as needed and have ready-made methods for adding, deleting and searching. The element type is written in angle brackets: List<int> is a list of integers, Dictionary<string, int> a dictionary that maps text to a number.

Before you start: required prior knowledge – classes and objects, arrays.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are C# console applications (.NET 8 or later, without "top-level statements"); every one has been tested and gives the output shown.

List<T>: an array of variable length

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> friends = new List<string> { "Anna", "Mark" };
        friends.Add("Ivy");                    // adding at the end
        friends.Insert(1, "Luke");             // inserting at position 1
        Console.WriteLine(string.Join(", ", friends));
        Console.WriteLine($"Count: {friends.Count}");

        friends.Remove("Mark");                // deleting by value
        friends.Sort();
        Console.WriteLine(string.Join(", ", friends));
        Console.WriteLine(friends.Contains("Ivy"));
        Console.WriteLine(friends.IndexOf("Luke"));

        for (int i = 0; i < friends.Count; i++)  // access by index, as with an array
            Console.WriteLine($"{i + 1}. {friends[i]}");
    }
}

The number of elements of a list is given by the Count property (for an array it is Length). When the amount of data is not known in advance, a list is a better choice than an array:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var numbers = new List<int>();
        while (true)                               // reading until zero
        {
            int x = int.Parse(Console.ReadLine());
            if (x == 0) break;
            numbers.Add(x);
        }
        numbers.RemoveAll(n => n < 0);             // remove all negative numbers
        numbers.Sort((a, b) => b.CompareTo(a));    // sort in descending order
        Console.WriteLine(string.Join(" ", numbers));
    }
}

The expressions n => n < 0 and (a, b) => b.CompareTo(a) are lambda expressions – short functions written where they are used. They are explained in detail in the lesson about LINQ.

Dictionary<K, V>: a dictionary (key → value)

A dictionary stores key – value pairs and quickly finds a value by its key. The keys are unique.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var count = new Dictionary<string, int>();
        foreach (string word in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries))
        {
            if (count.ContainsKey(word))
                count[word]++;                     // the word already exists – increase the counter
            else
                count[word] = 1;                   // a new word
        }
        foreach (var pair in count)                // pair is a KeyValuePair<string, int>
            Console.WriteLine($"{pair.Key}: {pair.Value}");

        if (count.TryGetValue("mouse", out int m))
            Console.WriteLine($"mouse: {m}");
        else
            Console.WriteLine("mouse does not appear");
    }
}

Reading a key that does not exist (count["mouse"]) stops the program with an error, so ContainsKey or TryGetValue is used. The order in which a dictionary is traversed is not guaranteed; when sorted keys are needed, SortedDictionary is used.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var phoneBook = new Dictionary<string, string>
        {
            ["Anna"] = "064 111 222",
            ["Mark"] = "063 333 444"
        };
        phoneBook["Ivy"] = "065 555 666";      // adding
        phoneBook["Anna"] = "064 999 888";     // changing an existing key
        phoneBook.Remove("Mark");              // deleting

        foreach (string name in phoneBook.Keys)
            Console.WriteLine($"{name}: {phoneBook[name]}");
        Console.WriteLine($"Total contacts: {phoneBook.Count}");
    }
}

HashSet<T>: a set without repetition

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var a = new HashSet<int> { 1, 2, 3, 4, 5 };
        var b = new HashSet<int> { 4, 5, 6, 7 };
        Console.WriteLine(a.Add(3));               // False – 3 already exists
        Console.WriteLine(a.Contains(4));          // a fast membership check

        var intersection = new HashSet<int>(a);
        intersection.IntersectWith(b);
        var union = new HashSet<int>(a);
        union.UnionWith(b);
        Console.WriteLine("Intersection: " + string.Join(" ", intersection));
        Console.WriteLine("Union: " + string.Join(" ", union));
    }
}

A set is best when you need to check "has this appeared already" or to remove duplicates: new HashSet<int>(array).

Queue<T> and Stack<T>

A queue works by the rule "first come, first served" (FIFO), and a stack by the rule "last in, first out" (LIFO).

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var queue = new Queue<string>();
        queue.Enqueue("Anna");                 // join the queue
        queue.Enqueue("Bob");
        queue.Enqueue("Cindy");
        Console.WriteLine($"Next in line: {queue.Peek()}");
        while (queue.Count > 0)
            Console.Write(queue.Dequeue() + " ");  // leave the queue
        Console.WriteLine();

        var stack = new Stack<int>();
        for (int i = 1; i <= 4; i++)
            stack.Push(i * 10);                // put on top
        Console.WriteLine($"Top of the stack: {stack.Peek()}");
        while (stack.Count > 0)
            Console.Write(stack.Pop() + " ");    // take off the top
        Console.WriteLine();
    }
}
CollectionWhen to use itImportant methods
List<T>an array of variable lengthAdd, Insert, Remove, Sort, Contains, Count
Dictionary<K,V>fast search by key, counting[key], ContainsKey, TryGetValue, Remove
HashSet<T>unique elements, membershipAdd, Contains, UnionWith, IntersectWith
Queue<T>processing in order of arrivalEnqueue, Dequeue, Peek
Stack<T>last in – first outPush, Pop, Peek

Practice tasks

Each task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: easy

The most frequent word

Read a line of words separated by spaces and print the word that appears most often and how many times. If there are several such words, print the one that comes first alphabetically.

Example 1

Input

yes no yes maybe no yes

Output

yes 3

Example 2

Input

b a b a

Output

a 2
TASK 02Difficulty: medium

Brackets

Read a line that contains the brackets ( ) [ ] { } (and possibly other characters) and print YES if the brackets are correctly paired and nested, and NO otherwise.

Example 1

Input

{[()()]}

Output

YES

Example 2

Input

([)]

Output

NO

Example 3

Input

((

Output

NO
Common mistakes and tips
  • Add using System.Collections.Generic; at the top of the file.
  • A list has Count, and an array Length.
  • Before reading from a dictionary, check the key (ContainsKey or TryGetValue).
  • A collection must not be changed (elements added or deleted) while you go through it with a foreach loop.

Check your knowledge

Open the quiz

Collections in C#

1. Which property gives the number of elements of a list?




2. Which collection is best for counting how many times each word appeared?




3. What does Add on a HashSet return if the element already exists?




4. Which collection works by the rule "last in, first out"?