大O符号数组与链接列表插入:
根据学术文献，数组是常数O(1)，链表是线性O(n)。
一个数组只需要一个乘法和加法。
未在连续内存中布置的链表需要遍历。
这个问题是，O(1)和O(n)是否分别准确地描述了数组和链表的索引/搜索成本？
最佳答案
O(1)准确地描述了在数组末尾的插入。但是，如果要插入到数组的中间，则必须将所有元素移到该元素之后，因此在这种情况下，插入的复杂度是数组的O(n)。如果数组已满，则必须附加结尾，这也可以打折。
对于链表，您必须遍历该列表以进行中间插入，因此即为O(n)。不过，您不必向下移动元素。
维基百科上有一个很好的图表:http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays
Linked list Array Dynamic array Balanced tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n)
Insert/delete at beginning Θ(1) N/A Θ(n) Θ(log n)
Insert/delete at end Θ(1) N/A Θ(1) amortized Θ(log n)
Insert/delete in middle search time
+ Θ(1) N/A Θ(n) Θ(log n)
Wasted space (average) Θ(n) 0 Θ(n)[2] Θ(n)
关于data-structures - 大O符号数组与链接列表插入，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7770569/