What is the time complexity of indexing, inserting and removing from common data structures?

Question

There is no summary available of the big O notation for operations on the most common data structures including arrays, linked lists, hash tables etc.

Answer 1

Information on this topic is now available on Wikipedia at: Search data structure

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list 
   (i.e. if you have an iterator to the location) is O(1). If you don't 
   know the location, then you need to traverse the list to the location
   of deletion/insertion, which takes O(n) time. 

** The deletion cost is O(log n) for the minimum or maximum, O(n) for an
   arbitrary element.