This page summarises some of the time comlplexities for various collection types with Java, though they should be exactly the same for .NET.
I've taken the tables from that page and altered/expanded them for the .NET framework.
See also the MSDN pages for SortedDictionary and SortedList, which detail the time complexities required for various operations.
Searching
Type of Search/Collection Types Complexity Comments
Linear search Array/ArrayList/LinkedList O(N) Unsorted data.
Binary search sorted Array/ArrayList/ O(log N) Requires sorted data.
Search Hashtable/Dictionary<T> O(1) Uses hash function.
Binary search SortedDictionary/SortedKey O(log N) Sorting is automated.
Retrieval and Insertion
Operation Array/ArrayList LinkedList SortedDictionary SortedList
Access back O(1) O(1) O(log N) O(log N)
Access front O(1) O(1) N.A. N.A.
Access middle O(1) O(N) N.A. N.A.
Insert at back O(1) O(1) O(log N) O(N)
Insert at front O(N) O(1) N.A. N.A.
Insert in middle O(N) O(1) N.A. N.A.
Deletion should have the same complexity as insertion for the associated collection.
SortedList has a few notable peculiarities for insertion and retrieval.
Insertion (Add method):
This method is an O(n) operation for
unsorted data, where n is Count. It is
an O(log n) operation if the new
element is added at the end of the
list. If insertion causes a resize,
the operation is O(n).
Retrieval (Item property):
Retrieving the value of this property
is an O(log n) operation, where n is
Count. Setting the property is an
O(log n) operation if the key is
already in the SortedList<(Of <(TKey,
TValue>)>). If the key is not in the
list, setting the property is an O(n)
operation for unsorted data, or O(log
n) if the new element is added at the
end of the list. If insertion causes a
resize, the operation is O(n).
Note that ArrayList
is equivalent to List<T>
in terms of the complexity of all operations.