单链表插入和删除的时间复杂度

Question

我对链表的时间复杂度感到有些困惑。在这篇文章（连接）中，它指出链表的插入和删除是O(1)。我想知道这是如何可能的？是否假设向前和向后的指针是已知的？那不是双向链表吗？如果有人能澄清一下这个问题，我将不胜感激。并且单向链表的插入/删除时间复杂度如何实现O(1)？

- Rajeshwar

---

将单词“sorted”添加到列表中，复杂度将迅速升高。如果不关心插入发生的位置，只是在列表的一端塞入一些东西，那显然是O(1)。如果您可以直接访问必须直接重连到新节点（即插入点）的指针，则将某些内容放入列表的特定位置为O(1)。 - WhozCraig

Answer 1

假设前置和后置指针已知吗？

在单向链表中，无论是插入还是删除，都需要一个指向插入/删除点之前元素的指针。然后一切都能正常运行。

例如：

# insert y after x in O(1)
def insert_after(x, y): 
    y.next = x.next
    x.next = y

# delete the element after x in O(1)
def delete_after(x):
    x.next = x.next.next

许多应用程序都可以通过算法轻松地携带当前查看项的前任，以允许动态插入和删除，时间复杂度为常数。当然，您始终可以在列表的前面插入和删除，时间复杂度为O(1)，这允许使用堆栈（LIFO）模式。

仅知道该项指针时通常不可能在O(1)内删除该项。编辑：正如codebeard所示，我们可以通过仅知道插入/删除点的指针来插入和删除。它涉及从后继节点复制数据，从而避免了修复前任的next指针的过程。

- Niklas B.

---

+1 ... 最后一条评论，除非你有指针按地址（或引用），这很少见，但有时确实很方便。写得不错。 - WhozCraig

@Rajeshwar 注意二叉搜索树（可以退化为节点的单链表）和平衡二叉搜索树（具有对数边界高度）之间的区别。当涉及到算法时，维基百科实际上非常有用。 - Niklas B.

@codebeard 现在我明白你的意思了，说得好。不过这需要复制数据。 - Niklas B.

@codebeard 当然可以，但是如果您可以接受间接性和额外指针，那么最好使用双向链表。单向链表通常用于节省空间和/或具有持久性数据结构，如果您这样做，则两者都不可能实现。我想这就是为什么它不太常用的原因，但我不确定。 - Niklas B.

@codebeard 当然，当然，你是完全正确的，我只是想知道为什么这不常用，因为它似乎很有用。我编辑了我的答案以反映这个事实（希望你不介意）。 - Niklas B.

Answer 2

是的，它假设您已经知道要插入数据的位置。

假设您在列表中有一些项目 p，并且您想在列表中的 p 之后插入一个新元素 new：

new->next = p->next;
p->next = new;

或者，假设您想在p之前插入new 。这仍然可以在O(1)时间内完成：

if (p == head) {
    new->next = head;
    head = new;
} else {
    tmp = p->data;
    p->data = new->data;
    new->data = tmp;
    new->next = p->next;
    p->next = new;
}

对于在传统的单向链表中删除元素，它并不严格是O（1）！

删除除最后一个元素以外的任何元素都是O（1）。如果您要删除单链表中的最后一个元素，则需要知道它之前的元素（假设您之前不知道它），这需要O（N）时间。

要删除项p：

free_if_necessary(p->data);
if (p->next) {
    /* O(1) */
    nextnext = p->next->next;
    nextdata = p->next->data;
    destroy_if_necessary(p->next);
    p->data = nextdata;
    p->next = nextnext;
} else if (p == head) {
    destroy_if_necessary(p);
    head = NULL;
} else {
    /* O(n) */
    prev = find_prev(head, p);
    destroy_if_necessary(p);
    prev->next = NULL;
}

- codebeard

---

@NiklasB。它运行良好，因为p所指向的数据已被更正。 - codebeard

Answer 3

也许这与数组的删除和插入操作有关。

而且，前提是您知道要插入或删除的位置。

在数组中，当您想要在位置pos插入或删除元素时，应将该位置pos后面的其他元素移动，因此复杂度为O(N)。

但是，在列表中，当您执行相同的操作时，无需考虑其他元素，因此复杂度为O(1)。

- BlackMamba