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();
}
}
Collection
When to use it
Important methods
List<T>
an array of variable length
Add, Insert, Remove, Sort, Contains, Count
Dictionary<K,V>
fast search by key, counting
[key], ContainsKey, TryGetValue, Remove
HashSet<T>
unique elements, membership
Add, Contains, UnionWith, IntersectWith
Queue<T>
processing in order of arrival
Enqueue, Dequeue, Peek
Stack<T>
last in – first out
Push, 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
Hint
Count the words in a Dictionary<string, int>, then in one pass through the dictionary remember the best one: a larger count, or the same count and a smaller word (string.CompareOrdinal).
Solution (C#)
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
var count = new Dictionary<string, int>();
foreach (string w in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries))
count[w] = count.TryGetValue(w, out int k) ? k + 1 : 1;
string bestWord = "";
int bestCount = 0;
foreach (var p in count)
if (p.Value > bestCount || (p.Value == bestCount && string.CompareOrdinal(p.Key, bestWord) < 0))
{
bestWord = p.Key;
bestCount = p.Value;
}
Console.WriteLine($"{bestWord} {bestCount}");
}
}
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
Hint
Put an opening bracket on the stack. For a closing one: the stack must not be empty, and the bracket on top must be the matching opening bracket. At the end the stack must be empty.
Solution (C#)
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string s = Console.ReadLine();
var stack = new Stack<char>();
bool ok = true;
foreach (char c in s)
{
if (c == '(' || c == '[' || c == '{')
stack.Push(c);
else if (c == ')' || c == ']' || c == '}')
{
char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
if (stack.Count == 0 || stack.Pop() != expected)
{
ok = false;
break;
}
}
}
Console.WriteLine(ok && stack.Count == 0 ? "YES" : "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"?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.