Page 29 : 36
Object-oriented Programming in C#
Collection Classes
* Collections - History and Overview
A historic View on Collection Programming
* Generic Collections in C#
Overview of Generic Collections in C#
The Interface
IEnumerable<T>
The Interface
ICollection<T>
The Interface
IList<T>
Overview of the class
Collection<T>
Sample use of class
Collection<T>
Specialization of Collections
Specialization of Collections - a realistic example
Overview of the class
List<T>
Sample use of class
List<T>
Sample use of the Find operations in
List<T>
Sample use of Sort in
List<T>
Sample use of BinarySearch in
List<T>
Overview of the class
LinkedList<T>
The class
LinkedListNode<T>
Sample use of class
LinkedList<T>
Time complexity overview: Collection classes
Using Collections through Interfaces
* Generic Dictionaries in C#
Dictionaries
Overview of Generic Dictionaries in C#
The interface
IDictionary<K,V>
Overview of the class
Dictionary<K,V>
Sample use of class
Dictionary<K,V>
Notes about Dictionary Classes
Time complexity overview: Dictionary classes
* Non-generic Collections in C#
The non-generic collection library in C#
Notes about non-generic Collections
* Patterns and Techniques
The Iterator Design Pattern
Making iterators with yield return
Iterator blocks and yield return
Time complexity overview: Dictionary classes
Assume that we work on a dictionary with
n
elements
Operation
Dictionary<K,V>
SortedDictionary<K,V>
SortedList
<K,V>
this[key]
O(1)
O(log n)
O(log n) or O(n)
Add(key,value)
O(1) or O(n)
O(log n)
O(n)
Remove(key)
O(1)
O(log n)
O(n)
ContainsKey(key)
O(1)
O(log n)
O(log n)
ContainsValue(value)
O(n)
O(n)
O(n)
Time complexities of important operations in the classes
Dictionary<K,V>
,
SortedDictionary<K,V>
, and
SortedList<K,V>
.
Notes
Add(key,value)
in
Dictionary<K,V>
:
Worst case if the hashtable must be enlarged
Constant times indicate
amortized complexity