从常见数据结构中索引,插入和删除的时间复杂度是多少？

对于最常见的数据结构(包括数组,链表,哈希表等)的操作,没有大O表示法的摘要.

1> Mobiletainme..：

---

有关此主题的信息现在可在维基百科上找到:搜索数据结构

+----------------------+----------+------------+----------+--------------+
|                      |  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.

---

请注意,您需要*区分**未排序的**和**排序的数组**.移位/填充数组的元素只是排序数组的一个问题,因此线性复杂度而不是未排序数组上的"O(1)".关于你想要找到要删除的元素的想法,你再次必须区分**找**元素和**删除它.删除的复杂性假定您已经知道要删除的元素,这就是为什么在排序数组上需要"O(n)"(需要移位)和未排序数组上的"O(1)".

2> Jose Vega..：

---

我想我会以链表的时间复杂度开始你:

索引----> O(n)
在末尾插入/删除----> O(1)或O(n)
在中间插入/删除---> O(1),迭代器O(n)没有

最后插入的时间复杂度取决于你是否拥有最后一个节点的位置,如果你有,那么它将是O(1),你将不得不搜索链表并且时间复杂度会跳到O. (N).

---

@Rob:这可能是一个愚蠢的怀疑,但我无法理解你如何插入O(1)中的双重链表？如果我有'1 < - > 2 < - > 3 < - > 4`并且如果我必须在3和4之间插入5,并且我拥有的是指向头节点的指针(即1)我必须在O中遍历(N).我错过了什么吗？