document updated 15 years ago, on May 14, 2009

generic	non-generic	internally implemented as	IList	IEnumerable	IDictionary
Array	(none)	linear array	Y	Y	N
List<T>	ArrayList	linear array	Y	Y	N
Dictionary<TKey, TValue>	Hashtable	hash table	N	Y	Y
SortedList<TKey, TValue>	SortedList	binary search tree	N	Y	Y
SortedDictionary<TKey, TValue>	-	binary search tree	N	Y	Y
Stack<T>	Stack	linear array	N	Y	N
Queue<T>	Queue	linear array	N	Y	N
LinkedList<T>	-	linked list	N	Y	N
HashSet<T>	-	hash table	N	Y	N
SortedSet<T>	?	?	?	?	?

GetValue()	O(1)
SetValue()	O(1)
BinarySearch()	O(n log(n))	behavior is undefined if not presorted
Reverse()	O(n)
Resize()	O(n)	use ArrayList instead
Sort()	O(n log(n))	quick sort

An array that grows as needed. When it expands, it allocates a new array, double in size, leaving room for further expansion.

GetValue()	O(1)
SetValue()	O(1)
Add()	O(1)	appends one to the end
RemoveAt()	O(n)	removing things from the middle requires an array copy
Insert()	O(n)	adding things from the middle requires an array copy
Sort()	O(n log(n))	quick sort