C Sharp Collections

Time Complexity Overview of .NET Generic Collections

Unkeyed:

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)

Keyed:

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)

Filtering

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

Duplicate Array

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

References

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