关于单链表插入O(1)时间复杂度的疑问：为何与删除逻辑矛盾？

与数组不同，我们无需移动插入位置后的所有元素，因此可以以O(1)的时间复杂度在链表中插入新节点，效率很高。

删除操作的时间复杂度为O(n)是合理的，因为需要遍历到目标节点的前一个节点并修改指针。但插入操作似乎也需要遍历到待插入位置的前一个节点，修改其.next指向新节点，为何时间复杂度不是O(n)？

参考来源 #

• LeetCode学习模块 - 单链表插入
• LeetCode学习模块 - 链表结论

关键在于插入操作的前提条件：这里提到的O(1)插入，指的是已经拿到待插入位置的前驱节点或目标插入位置节点引用的场景。

举两种情况说明：

• 如果已经持有某个节点p的引用，要在p后面插入新节点，只需要执行两步操作：new_node.next = p.next、p.next = new_node，这都是常数时间的操作，不需要遍历链表，时间复杂度自然是O(1)。
• 但如果只知道要插入的“位置序号”（比如要在第k个节点后插入），那确实需要从头遍历找到第k个节点，这时时间复杂度是O(n)——但这不属于LeetCode所描述的O(1)插入场景。

而删除操作通常是O(n)，核心原因是单链表中无法从目标节点直接获取它的前驱节点，即使拿到目标节点的引用，也必须从头遍历找到其前驱才能完成删除；而插入操作只要有前驱节点的引用，就能直接完成，这就是两者的本质区别。

内容的提问来源于stack exchange，提问作者wongx