
add to end 
remove from end 
insert at middle 
remove from middle 
Random Access 
Inorder Access 
Search for specific element 
Notes 
Array 
O(n) 
O(n) 
O(n) 
O(n) 
O(1) 
O(1) 
O(n) 
Most efficient use of memory; use in cases where data size is fixed. 
List<T> 
best case O(1); worst case O(n) 
O(1) 
O(n) 
O(n) 
O(1) 
O(1) 
O(n) 
Implementation is optimized
for speed. In many cases, List
will be the best choice.

Collection<T> 
best case O(1); worst case O(n) 
O(1) 
O(n) 
O(n) 
O(1) 
O(1) 
O(n) 
List is a better choice, unless
publicly exposed as API.

LinkedList<T> 
O(1) 
O(1) 
O(1) 
O(1) 
O(n) 
O(1) 
O(n) 
Many operations are fast,
but watch out for cache
coherency.

Stack<T> 
best case O(1); worst case O(n) 
O(1) 
N/A 
N/A 
N/A 
N/A 
N/A 
Shouldn't be selected for
performance reasons, but
algorithmic ones.

Queue<T> 
best case O(1); worst case O(n) 
O(1) 
N/A 
N/A 
N/A 
N/A 
N/A 
Shouldn't be selected for
performance reasons, but
algorithmic ones.

Dictionary<K,T> 
best case O(1); worst case O(n) 
O(1) 
best case O(1); worst case O(n) 
O(1) 
O(1)* 
O(1)* 
O(1) 
Although inorder access time
is constant time, it is usually slower than other structures due to the overhead of looking up the key.
