我对链表的时间复杂度感到有些困惑。在这篇文章(连接)中,它指出链表的插入和删除是O(1)。我想知道这是如何可能的?是否假设向前和向后的指针是已知的?那不是双向链表吗?如果有人能澄清一下这个问题,我将不胜感激。并且单向链表的插入/删除时间复杂度如何实现O(1)?
我对链表的时间复杂度感到有些困惑。在这篇文章(连接)中,它指出链表的插入和删除是O(1)。我想知道这是如何可能的?是否假设向前和向后的指针是已知的?那不是双向链表吗?如果有人能澄清一下这个问题,我将不胜感激。并且单向链表的插入/删除时间复杂度如何实现O(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
是的,它假设您已经知道要插入数据的位置。
假设您在列表中有一些项目 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;
}
也许这与数组的删除和插入操作有关。
而且,前提是您知道要插入或删除的位置。
在数组中,当您想要在位置pos
插入或删除元素时,应将该位置pos
后面的其他元素移动,因此复杂度为O(N)
。
但是,在列表中,当您执行相同的操作时,无需考虑其他元素,因此复杂度为O(1)
。