双链表最后一个元素的删除复杂度
Deletion complexity of last element in double linked list
如果你想删除节点A那么你只需要遍历一个，复杂度会O(1)
如果要删除节点C那么就得遍历两次，复杂度会O(n)
如果你想删除节点D那么你必须遍历三次并且复杂度可能是O(n)
但是，double linked 列表中最后一个节点的删除复杂度是 O(1)
我不明白这是怎么回事？
我检查了这个 link 但我没有得到/不明白我的回答
Link
复杂性不在于移除项目，而在于定位它。
在双向链表中，您通常有一个指向列表中最后一个元素的指针，以便您可以追加。所以如果有人要求你删除最后一个元素，你可以删除它。
如果有人让你删除列表的第k个元素，你必须从头开始，遍历k个链接找到该元素，然后才能删除它。那将是 O(k)，在最坏的情况下将是 O(n-1)。
唯一从双向链表中删除最后一个节点的复杂度为 O(1) 的情况是当您可以直接访问该节点时，例如尾指针。否则你将不得不遍历整个列表，这需要 O(n).
如果你想删除节点A那么你只需要遍历一个，复杂度会O(1)
如果要删除节点C那么就得遍历两次，复杂度会O(n)
如果你想删除节点D那么你必须遍历三次并且复杂度可能是O(n) 但是，double linked 列表中最后一个节点的删除复杂度是 O(1)
我不明白这是怎么回事？
我检查了这个 link 但我没有得到/不明白我的回答 Link
复杂性不在于移除项目，而在于定位它。
在双向链表中，您通常有一个指向列表中最后一个元素的指针，以便您可以追加。所以如果有人要求你删除最后一个元素，你可以删除它。
如果有人让你删除列表的第k个元素，你必须从头开始，遍历k个链接找到该元素，然后才能删除它。那将是 O(k)，在最坏的情况下将是 O(n-1)。
唯一从双向链表中删除最后一个节点的复杂度为 O(1) 的情况是当您可以直接访问该节点时，例如尾指针。否则你将不得不遍历整个列表，这需要 O(n).