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

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)。这有点误导，但在维基百科上有一个图表更好地解释了它：

将此与动态数组进行对比，如果要在开头插入，则为：?(n)。

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