data-structures - 从通用数据结构中进行索引，插入和删除的时间复杂度是多少？

Question

没有大的O标记可用于对最常见的数据结构（包括数组，链表，哈希表等）进行操作的摘要。

Answer 1

现在可以在Wikipedia上找到有关此主题的信息：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.