在双向链表最后一个元素的复杂性缺失

Question

如果你想删除一个节点，那么你必须遍历只有一个和复杂性在O（1）

如果你想删除节点C，那么你必须遍历两次和复杂性会为O（n）

如果你想删除节点d，那么你必须遍历三次和复杂性可能是为O（n）。然而，在双链表的最后一个节点删除复杂度为O（1）

我不明白这一点它是如何工作的？

我检查这个链接，但我没有/不明白我的答案Link

Answer 1

复杂性是不是在去除项目，但它的定位。

在双向链表，你通常有一个指向最后一个元素的列表，这样可以追加。所以，如果有人问你要删除的最后一个元素，你可以将其删除。

如果有人问你要删除列表中的第k个元素，你必须从头开始并遍历ķ链接查找元素，然后才能删除它。这将是O（k）时，这在最坏的情况下将是O（N-1）。

Answer 2

只有当从双向链表最后一个节点的缺失将为O情况（1）复杂性是当你有直接访问这个节点上，像尾指针。否则，你将不得不遍历整个列表这需要为O（n）。