Jump to: navigation, search

Time Complexity Overview of .NET Generic Collections


Operation               List<T>                HashSet<T>              LinkedList<T>
Add                     O(1) (count>cap: O(n)) O(1) (count>cap: O(n))  O(1)
Remove                  O(n)                   O(1)                    O(1) (by node)
Contains / Find         O(n)                   O(1)                    O(n)
Count                   O(1)                   O(1)                    O(1)
Clear                   O(n)                   O(n)                    O(n)


Operation               Dictionary<K,V>        SortedDictionary<K,V>   SortedList<K,V>
this[key]               O(1)                   O(log n)                O(log n) or O(n)
Add                     O(1) or O(n)           O(log n)                O(n)
Remove                  O(1)                   O(log n)                O(n)
ContainsKey             O(1)                   O(log n)                O(log n)
ContainsValue           O(n)                   O(n)                    O(n)
Count                   O(1)                   O(1)                    O(1)
Clear                   O(n)                   O(1)                    O(n)


List<Thing> list = new List<Thing>();
list.RemoveAll(delegate(Thing s) { return Thing.Coolness > 2f; });

Duplicate Array

originalArray.CopyTo(newArray, 0); // 0 = start index


Kurt Nørmark: Object-oriented Programming in C# for C and Java programmers