ntechdevelopers.

com

.NET Collections - Part 1

Nam Vu Thanh
20/10/2023
1
In this workshop, we will...

§ Understand how collections work under the hood

§ Discover C# compiler's secrets

§ Explore code written by Microsoft

§ Know how to avoid traps when using collections

2
Table of Contents

§ Overview § Dictionary
‒ Sorted List
§ Array
‒ Sorted Dictionary
§ Collection Interfaces
§ Hash Set
§ List ‒ Sorted Set
‒ Linked-List
‒ Stack
‒ Queue

3
 Overview

* 4
.NET collection history

2002 2005 2007 2010 2012

.NET 1.0 .NET 2.0 .NET 3.0 .NET 4.0 .NET 4.5

Generics LINQ Concurrent Read-only

Collections Interfaces

5
Basic collection operations

Collection
Read Write

Look up an item Add items

Enumerate items Remove items

Insert items

Replace items

6
 Arrays

* 7
Introducing arrays

§ Index-based (start from 0)

§ Many built-in functionalities (copy, reverse, binary search, ...)
§ Lightweight (less overhead than other collections)
§ Special syntax in C# (other collections don't have this)
§ Fixed length (cannot add or remove elements)

§ Many other collections use arrays under the hood

‒ List<T>, Stack<T>, Queue<T>

8
How to create a new array

§ Array numbers = Array.CreateInstance(typeof(int), 5);

§ int[] numbers = new int[5]; // 0, 0, 0, 0, 0
§ int[] numbers = new int[5] { 1, 2, 3, 4, 5 };
§ int[] numbers = new int[] { 1, 2, 3, 4, 5 };
§ int[] numbers = new[] { 1, 2, 3, 4, 5 };
§ int[] numbers = { 1, 2, 3, 4, 5 };
§ var numbers = { 1, 2, 3, 4, 5 };

Fails to compile

9
How is array of integers created?

var numbers = new int[5];

numbers

Reference 0 i=0
0 i=1
0 i=2
0 i=3
0 i=4

10
How is array of strings created?

var names = new string[5] { “A”, “B”, “C”, “D”, “E” };

names
“A”
Reference i=0
“B”
i=1
i=2 “C”
i=3
“D”
i=4
“E”
11
How do arrays work?

X
Address of Remember C++ ?
the 1st item

i=0 S bytes

i=1 S bytes Address of item [i]

i=2 S bytes X + i * S
i=3 S bytes Note
• - Items must be sequential in
i=4 S bytes memory.
• - Size of each item must be the
same.
12
Why do arrays have fixed length?

i=0
I want to add
i=1 more items
i=2 to the array.

i=3
i=4

Add a new item here?

13
Why do arrays have fixed length?

i=0
i=1
i=2
Not guaranteed to be free memory
i=3
i=4
X Add a new item here?

14
How to create a multi-dimensional array

§ int[,] numbers = new int[3,3];

‒ 2D array of integers (multiple dimensions but only one array)
‒ This is called rectangular array

§ int[][] numbers = new int[3][];

‒ Array of arrays of integers
‒ This is called jagged array

15
How are rectangular arrays stored in memory?

var names = new string[2,2]

{
{ “A”, “D” },
{ “B”, “E” }
};
“A”

i = [0,0] “D”
names
Reference i = [0,1]
i = [1,0] “B”
i = [1,1]
“E”
16
How are jagged arrays stored in memory?

var names = new string[3][]

{
new string[] { “A”, “D”, “Q” },
new string[] { “B”, “E” },
new string[] { “C” }
};

“A” “D” “Q”

names
Reference i=0
“B” “E”
i=1
i=2 “C”
17
Enumerating arrays

var names = new string[] { “A”, “B”, “C” };

for (var i = 0; i < names.Length; i++)

{
Console.WriteLine(names[i]);
}

foreach (var item in names)

{
Console.WriteLine(item);
}

18
Foreach iteration variable is read-only

var names = new string[] { “A”, “B”, “C” };

foreach (var item in names)

{
item = “D”;
}
Fails to compile

Note
• Foreach interation variable (variable “item”) is read-only.

19
Foreach with array behind the scene

var names = new string[] { “A”, “B”, “C” };

foreach (var item in names)

{
Console.WriteLine(item);
}

var names = new string[] { “A”, “B”, “C” };

string[] array = names; Compiler converts

for (int i = 0; i < array.Length; i++) “foreach” loop to “for” loop
{ behind the scene.
string item = array[i]; This is only true for array.
Console.WriteLine(item);
}

20
Why is foreach iteration variable read-only?

var names = new string[] { “A”, “B”, “C” }; Note

Changing this variable is useless
string[] array = names;
for (int i = 0; i < array.Length; i++) because it is a local variable. Any
{ change will be discarded when it
string item = array[i]; goes out of scope. As a result, all
Console.WriteLine(item); values in the array remains intact.
}
That's why Microsoft makes this
Foreach interation variable variable read-only to prevent
confusion.

21
Array inheritance hierarchy

Object

Abstract class
Array

String[] Object[]

22
Array covariance

var names = new string[] { “A”, “B”, “C” };

object[] objects = names;

var numbers = new int[] { 1, 2, 3, 4, 5 };

objects = numbers;
Fails to compile
(only work with array
of reference types)

Note
• - Other collections don't have this feature.
• - However, IEnumerator<T> and IEnumerable<T> interfaces do have it.

23
Should you use array covariance?

var names = new string[] { “A”, “B”, “C” };

object[] objects = names;

objects[0] = 1;

Compiles successfully
but fails at run-time

Note
• - Array covariance is bad (damages type-safety of arrays).
• - Don't use it.

24
Copying arrays

var source = new int[] { 1, 2, 3, 4, 5 };

var target = new int[10];

Make sure the array is long enough

source.CopyTo(target, 2);
Start index of target array

Array.Copy(source, 0, target, 2, source.Length);

Note
• Array.Copy() will throw exception if “source” or “target” is null.

25
Reversing arrays

var source = new int[] { 1, 2, 3, 4, 5 };

Array.Reverse(source);

var target = source.Reverse().ToArray();

LINQ extension method

Note
• - Array methods work in-place (modify the source array).
• - LINQ methods return a new object (source array remains intact).

26
Sorting arrays

var source = new int[] { 5, 4, 3, 2, 1 };

Array.Sort(source);

var target = source.OrderBy(n => n).ToArray();

LINQ

Note
• String and number types (int, long, float, double, ...) have natural ordering.
• To compare other types, you must provide a comparer (IComparer<T>).

27
Finding elements using values

var source = new int[] { 1, 2, 3, 4, 5 };

var index = Array.IndexOf(numbers, 3); // 2

Search from the Value we need to

start of array find the index

var lastIndex = Array.LastIndexOf(numbers, 3);

Search from the

end of array

28
Finding elements using conditions

var source = new int[] { 1, 2, 3, 4, 5 };

var index = Array.FindIndex(numbers, n => n == 3);

Search condition
var lastIndex = Array.FindLastIndex(numbers, n => n == 3);

var items = Array.FindAll(numbers, n => n < 4); // 1, 2, 3

items = numbers.Where(n => n < 4).ToArray(); // 1, 2, 3
LINQ
Note
• - Search condition is a predicate (an expression that returns a boolean).
• - FindAll() and Where() returns all items that satisfy the search condition.

29
Binary search

var source = new int[] { 1, 2, 3, 4, 5 };

var index = Array.BinarySearch(source, 3);

Prerequisite for binary search

• - Array must be already sorted.
• - Items must be comparable.

Note
• Should use BinarySearch() if array is large.
• Otherwise, use IndexOf().

30
 Collection Interfaces

* 31
Non-generic collection interface hierarchy

IEnumerable Note
• These collections are obsolete.
• Should use generic versions instead.
ICollection

IList IDictionary

32
Generic collection interface hierarchy

IEnumerable

IEnumerable<T>
IList<T>

ICollection<T> IDictionary<TKey, TValue>

ISet<T>

33
Read-only collection interface hierarchy

IEnumerable

IEnumerable<T>
IReadOnlyList<T>

IReadOnlyCollection<T>
IReadOnlyDictionary<TKey, TValue>

34
IEnumerable<T>

You can enumerate me.

IEnumerable<T>

GetEnumerator()

35
ICollection<T>

IEnumerable<T> ICollection<T> I have basic

operations
Count
of a collection.
IsReadOnly

Add()
Remove()
Clear()
Contains()
CopyTo()

36
IList<T>

IEnumerable<T> ICollection<T>

I have basic
IList<T>
operations
of a list.
this[int]

IndexOf()
Insert()
RemoveAt()

37
IDictionary<TKey, TValue>

ICollection<T> IEnumerable<T>

IDictionary<TKey, TValue>
I have basic
this[TKey] operations
Keys of a dictionary.
Values

Add()
Remove()
ContainsKey()
TryGetValue()
38
ISet<T>

IEnumerable<T> ICollection<T>

ISet<T> I have basic

operations
Add() of a set.
SetEquals()
IsSubsetOf()
IntersectWith()
...

39
Read-only collection interfaces

You can't change IEnumerable<T>

me. But you can
count on me.
IReadOnlyCollection<T>

Count

IReadOnlyDictionary<TKey, TValue>

IReadOnlyList<T> this[TKey]
ContainsKey()
Keys
TryGetValue()
this[int] Values
40
 Lists

* 41
Introducing List<T>

§ Just a wrapper of array

§ Provide additional features which array doesn't have
‒ Add items
‒ Remove items
‒ Insert items

42
Create and use List<T>

var list = new List<int> { 1, 2, 3 };

list.Add(4);

list.AddRange(new[] { 6, 7, 8 });

list.Remove(2); Use linear search to find

the item to be removed
list.RemoveAt(1);

Index of item to be removed

43
How does List<T> work?

var names = new List<string> { “A”, “B” };

“A”
Count = 2
“B”
Capacity = 4
null
null
Note
• - Capacity is the length of the underlying array.
• - Count is the number of values stored in array.
44
How does List<T> add new items?

names.Add(“C”);

“A”
“B” “C”
null
null

45
How does List<T> add new items?

O(1)
Big O notation
“A”
“B”
“C”
null

46
How does List<T> remove items?

names.Remove(“B”);

“A”
“B”
Copy
“C”
Copy
null
Note
• Shift all elements after “B” up one slot.

47
How does List<T> remove items?

“A”
“C”
“C”
Copy
null

48
How does List<T> remove items?

O(n)
“A”
“C”
null
null

49
How does List<T> insert items?

names.Insert(1, “B”);

“A” “B”
“C”
null
null

50
How does List<T> insert items?

names.Insert(1, “B”);

“A” “B”
“C”
Copy
null
null
Note
• Shift all elements from index 1 down one slot.

51
How does List<T> insert items?

“A” Replace
“B”
“C”
“C”
null

52
How does List<T> insert items?

O(n)
“A”
“B”
“C”
null

53
How does List<T> reallocate its array?

names.Add(“E”);

“A”
There's no more room
“B” to store a new element.
“C”
“D” ?
“E”

54
How does List<T> reallocate its array?

names.Add(“E”);
“A”

Double “B”
capacity “C”
“A” “E”
“D”
“B” Capacity = 8
Capacity = 4 null
“C” null
“D” null
null
55
Create a List<T> with capacity

var list = new List<int>(10) { 1, 2, 3 };

Specify the capacity

Note
• - Use this when you know beforehand the capacity you'll need.
• - This will help List avoid reallocate its array continuously (better performance).

56
Introducing ReadOnlyCollection<T>

var list = new List<int> { 1, 2, 3 };

ReadOnlyCollection<int> readOnlyList1 = list.AsReadOnly();

var readOnlyList2 = new ReadOnlyCollection<int>(list);

Pass the IList<T> to constructor

Note
• As its name suggests, ReadOnlyCollection<T> doesn't allow you to add or remove items.

57
Introducing Collection<T>

§ Implements IList<T>

§ Used for creating custom collections

§ Demo: Create a list that prevent empty strings to be added

58
Using Collection<T>

class NotEmptyStringCollection : Collection<string>

{
protected override void InsertItem(int index, string item)
{
if (string.IsNullOrEmpty(item))
{
throw new InvalidOperationException();
}
Don't allow null
base.InsertItem(index, item); or empty string
}
} Reuse functionality
of the base class
59
Introducing ObservableCollection<T>

§ A derived class of Collection<T>

§ A list that notifies changes

§ Not only for WPF but also for other type of projects

§ CollectionChanged event is raised when the collection changes

§ NotifyCollectionChangedEventArgs contains useful information

about the changes

§ Demo: Create a collection that notifies changes

60
Using ObservableCollection<T>

var observables = new ObservableCollection<int> { 1, 2, 3 };

observables.CollectionChanged += OnCollectionChanged;
observables.Add(4);
observables.Remove(3); This event will be raised when
the collection changes
private void OnCollectionChanged(object sender,
NotifyCollectionChangedEventArgs e)
{
// Do something here. Many useful information
} about the change

61
 Linked-Lists, Stacks, and Queues

* 62
Introducing Linked-List, Stack, and Queue

§ They are lists but without the ability to look up items using index
§ LinkedList<T>
‒ Doubly-linked list (has references to previous and next nodes)
‒ Very quick at adding or removing items
‒ But uses a lot of memory

§ Stack<T> (LIFO)
‒ Uses array under the hood
‒ Therefore, more efficient than LinkedList<T>

§ Queue<T> (FIFO)
‒ Also uses array under the hood

63
How does LinkedList<T> work?

First Last
Next

“A” “B” “C” “D”

Previous LinkedListNode<T>

Note
• Each item in linked-list is a LinkedListNode<T>.

64
How to create a new LinkedList<T>

var linkedList = new LinkedList<string>();

var node = linkedList.AddFirst(“A”);

node = linkedList.AddLast(“B”);

Return newly added node

Note
• - LinkedList<T> has no initializer, you must add items manually.
• - Every item is a LinkedListNode<T>.

65
Basic LinkedList<T> operations

var node = linkedList.Find(“A”);

var success = linkedList.Remove(“B”);

linkedList.RemoveFirst();

Remove the first node

Note
• Find()
- Find()isisnot
notefficient
efficientbecause
becauseit ithas
hastotosearch
searchthe
thewhole
wholelist.
list.
• Remove()
- Remove()also
alsohas
hastotosearch
searchthe
thewhole
wholelist.
list.
66
How does Stack<T> work?

“C”

stack.Push(“C”)
“B”
“A”

67
How does Stack<T> work?

“C”
“B”
“A”

68
How does Stack<T> work?

“C”

stack.Pop()
“B”
“A”
Note
• Stack<T> is LIFO (Last In First Out)

69
How to create and use Stack<T>

var stack = new Stack<string>();

stack.Push(“A”); Add new item to the stack

var item = stack.Peek(); Get the top item

without removing it
item = stack.Pop(); Get the top item
and remove it

Note
• - Stack<T> uses array under the hood.
• - Like LinkedList<T>, Stack<T> has no initializer.

70
How does Queue<T> work?

“A” stack.Enqueue(“C”)
“B”

“C”

71
How does Queue<T> work?

“A”
“B”
“C”

72
How does Queue<T> work?

“A”

stack.Dequeue()
“B”
“C”

Note
• Queue<T> is FIFO (First In First Out)

73
How to create and use Queue<T>

var queue = new Queue<string>();

stack.Enqueue(“A”); Add new item to the queue

var item = stack.Peek(); Get the next item

without removing it
item = stack.Dequeue(); Get the next item
and remove it

Note
• - Queue<T> uses array under the hood.
• - It has no initializer.

74
 Dictionaries

* 75
Introducing Dictionary<TKey, TValue>

§ Implements IDictionary<TKey, TValue>

§ Key-based (accessing elements using keys instead of index)

§ Keys can be any type

‒ Uses GetHashCode() of the key object

§ Uses hash table under the hood

‒ Very fast lookup
‒ But a bit slower than index-based lookup

76
Creating Dictionary<TKey, TValue>

var employees = new Dictionary<string, string>();

employees.Add(“GCS1000”, “John Smith”);

Throws if key already exists

employees[“GCS1000”] = “John Doe”;

Update the value of existing key

Note
• - Dictionary has good performance.
• - Adding and removing items is fast.
77
Accessing values in Dictionary<TKey, TValue>

var employeeOfMonth = employees[“GCS1000”];

Throws if key doesn't exist

string employeeOfYear;
if (employees.TryGetValue(“GCS1000”, out employeeOfYear))
{
// Do something
}

Note
• Always use TryGetValue() to avoid exception if key doesn't exist.
78
How does Dictionary work?

Key: “GCS1000” Hash algorithm Bucket 2

GetHashCode()
Value: “John Smith”

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Note
• This is a high-level overview of how hash table works.

79
How does Dictionary work?

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Key: “GCS1000”
Value: “John Smith”

Note
• Buckets are implemented using array.
80
How does Dictionary work?

Key: “GCS1001” Hash algorithm Bucket 4

GetHashCode()
Value: “Jane Doe”

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Key: “GCS1000” Note

Value: “John Smith”
• The purpose of GetHashCode()
• is to allow all objects to be
• used as Dictionary keys.

81
How does Dictionary work?

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Key: “GCS1000” Key: “GCS1001”

Value: “John Smith” Value: “Jane Doe”

82
How does Dictionary work?

Key: “GCS1002” Hash algorithm Bucket 2

GetHashCode()
Value: “James Doe”

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Key: “GCS1000” Key: “GCS1001”

Value: “John Smith” Value: “Jane Doe”

83
How does Dictionary work?

Bucket 1 Bucket 2 Bucket 3 Bucket 4

Key: “GCS1000” Key: “GCS1001”

Value: “John Smith” Value: “Jane Doe”

Key: “GCS1002”
Value: “James Doe”

84
Using StringComparer with Dictionary

var dict = new Dictionary<string, string>(

StringComparer.InvariantCultureIgnoreCase);

Provide a string comparer

for Dictionary constructor

Note
• - By default, strings are case-sensitive.
• - You can use a different comparer to ignore the casing.
• - In this case, we use StringComparer provided by .NET.

85
Implementing IEqualityComparer<T>

§ Create a new class that implements IEqualityComparer<T> interface

§ There are 2 rules to remember:

‒ If 2 objects are equal, they must return the same hash code
‒ Use what Microsoft has already written such as GetHashCode()

§ Demo: Create a custom equality comparer

86
Implementing IEqualityComparer<T>

class CaseInsensitiveComparer : IEqualityComparer<string>

{
public bool Equals(string x, string y)
{
return string.Equals(x, y,
StringComparison.InvariantCultureIgnoreCase);
}
Reuse Microsoft's
public int GetHashCode(string obj) implementation of
{ GetHashCode()
return obj.ToUpper().GetHashCode();
}
}
87
Introducing ReadOnlyDictionary

var dict = new Dictionary<string, string>

{
[“GCS1000”] = “A”,
[“GCS1001”] = “B”
};

var readOnlyDict = new ReadOnlyDictionary<string, string>(dict);

Note
• ReadOnlyDictionary doesn't have methods that modify the collection.

88
Introducing SortedList<TKey, TValue>

§ A dictionary which always sorts its values by keys

§ Implements IDictionary<TKey, TValue>
§ Uses binary search to find the item (since it's already sorted)
§ Adding or removing items is slow (must sort items after modification)
§ Worth using only if the keys can be sorted

Note
• - Don't let its name fool you, SortedList is a dictionary.
• - It implements IDictionary<TKey, TValue> interface.

89
How does SortedList work?

SortedList<TKey, TValue>

TKey[] TValue[]
-------------- --------------
-------------- Sync --------------
-------------- --------------

This list is sorted

(binary search is used for
looking up keys)

90
Introducing SortedDictionary<TKey, TValue>

§ Uses balanced tree for sorting elements

§ Adding or removing items is fast
§ Can pass an IComparer<T> to the constructor
‒ Change the way its values are sorted

§ Demo: Implement a custom comparer for SortedDictionary

91
How does SortedDictionary work?

SortedDictionary<TKey, TValue>

Balanced tree
from SortedSet

92
Implementing IComparer<T>

class StringLengthComparer : IComparer<string>

{
public int Compare(string x, string y)
{
return x.Length.CompareTo(y.Length);
}
}

var dict = new SortedDictionary<string, string>(

new StringLengthComparer());
Pass the comparer
to the constructor
93
Introducing KeyedCollection<TKey, TItem>

§ Inherits from Collection<T>

§ Used to create Dictionary that can extract keys from its values

§ Must override GetKeyForItem(TItem item);

§ Elements can be accessed by Indexes or Keys

§ Demo: Create a dictionary that can extract keys from its values

94
Using KeyedCollection<TKey, TItem>

class AutoExtractKeyDictionary : KeyedCollection<string, Employee>

{
protected override string GetKeyForItem(Employee item)
{
return item.Id;
}
}

class Employee
{
public string Id { get; set; }
public string Name { get; set; }
}
95
How does KeyedCollection work?

KeyedCollection<TKey, TItem>

List<TItem> Hash table

--------------
-------------- Sync
--------------

Access elements Access elements

using indexes using keys
(inherited from Collection<T>)

96
 Sets

* 97
Introducing HashSet<T>

§ Implements ISet<T>

§ Contains elements that have no order

§ Uses hash table under the hood

§ Every element is guaranteed to be unique

§ Can only access elements by enumerating

98
Set operations

§ Intersection
‒ Find values that are in both sets

§ Union
‒ Find values that are in either set

§ Difference
‒ Find values that are in the first set

§ Symmetric difference
‒ Find values that are in only one set

99
Using set operations with HashSet<T>

var set1 = new HashSet<int>() { 1, 2, 3, 4 };

var set2 = new HashSet<int>() { 1, 3, 5, 7 };

set1.IntersectWith(set2); // 1, 3
set1.UnionWith(set2); // 1, 2, 3, 4, 5, 7
set1.ExceptWith(set2); // 2, 4
set1.SymmetricExceptWith(set2); // 2, 4, 5, 7

Note
• - These methods work in-place (modify the source set).
• - Can also use LINQ methods for similar functionalities.

100
Set comparisons

§ SetEquals() : Determines if the two sets have the same items

§ IsSubsetOf() : Determines if a set is a subset of another

§ IsSupersetOf(): Determines if a set is a superset of another

§ Overlaps() : Determines if the two sets have items overlapsed

§ IsProperSubsetOf()

§ IsProperSupersetOf() 2 4 2
1 3 1 3

101
Introducing SortedSet<T>

§ Has all functionalities of HashSet<T> but its values are sorted

§ Its constructor can receive an IComparer<T>

var set = new SortedSet<string>();

set.Add(“A”);
set.Remove(“A”);

102
How does SortedSet<T> work?

SortedSet<T>

Balanced tree

103
Dictionary vs HashSet

Dictionary HashSet

§ Use hash table § Use hash table

§ Store keys and values § Store only values, no keys

§ Get hash code of keys § Get hash code of values

§ Can access items by keys § Cannot access items

§ Can enumerate items § Can enumerate items

104
 Summary

* 105
Summary

Modification
Collection Under the hood Access Lookup efficiency
efficiency
Index: O(1) - Contains():
List Array Index O(n)
O(n)
LinkedList Circular doubly linked list Contains(): O(n) O(1)
Stack Array Peek(): O(1) O(1)
Queue Array Peek(): O(1) O(1)
Dictionary Hash table Key Key: O(1) O(1)
SortedList Array Key Key: O(log n) O(n)
SortedDictionary Binary search tree Key Key: O(log n) O(log n)
HashSet Hash table Contains(): O(1) O(1)
SortedSet Binary search tree Contains(): O(log n) O(log n)
Faster Slower
O(1) O(log n) O(n)
106