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

Question

我对链表的时间复杂度有点困惑。在本文中，它指出在链表中插入和删除是O(1)。我想知道这怎么可能?是否假设前进指针和下一步指针是已知的?这不是双链表吗?如果有人能澄清一下，我会很感激的。单链表的插入/删除的时间复杂度如何为O(1) ?

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)中通常不可能。EDIT:如codebeard所示，我们可以通过知道插入/删除点的指针来插入和删除。它涉及到从后继程序复制数据，从而避免修复前一个程序的next指针。

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)!

删除除最后一个元素以外的任何元素都是0(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;
}

Answer 3

这可能与数组的删除和插入操作有关。

有一个先决条件是你知道在哪里插入或删除。

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

但是在List中，当你做同样的操作时，你不需要考虑其他元素，所以复杂度是O(1)