单向链表和双向链表的插入时间如何？

Question

想了想，我觉得插入和查找任何数据结构的时间复杂度应该是一样的，因为要插入，首先要查找要插入的位置，然后再插入.

根据这里：http://bigocheatsheet.com/，对于链表来说，查找是线性时间，而插入是常数时间。我明白搜索是线性的（从最前面开始，然后一直遍历链表上的节点，直到找到要搜索的内容），但是插入常数时间如何？

假设我有这个链表：

1 -> 5 -> 8 -> 10 -> 8

而我想在数字8之后插入数字2，那么我是否必须先搜索数字8（搜索是线性时间），然后再进行额外的2步插入它（所以，插入还是线性时间？)?

#insert y after x in python 
def insert_after(x, y):
    search_for(y)
    y.next = x.next
    x.next = y

编辑：即使是双向链表，不应该还是先搜索节点（线性时间），然后再插入吗？

Answer 1

因此，如果您已经有对要插入的节点的引用，那么它是 O(1)。否则就是search_time + O(1)。这有点误导，但 on wikipedia 有一张图表更好地解释了它：

将此与动态数组进行对比，如果您想在开头插入，则为：Θ(n).

强调一下：您引用的网站指的是实际插入行为，因为我们已经知道要插入的位置。

Answer 2

插入时间 = 设置三个指针的时间 = O(3) = 常数时间。

插入数据的时间与在特定位置插入数据的时间不同。询问的时间只是插入数据的时间。

How is insertion for a Singly Linked List and Doubly Linked List constant time?