单链表和双链表中节点删除的时间复杂度 [英] Time complexity of node deletion in singly- and doubly-linked lists

问题描述

为什么双链表(O(1))中节点删除的时间复杂度比单链表(O(n))中节点删除的时间复杂度为何?

Why is the time complexity of node deletion in doubly linked lists (O(1)) faster than node deletion in singly linked lists (O(n))?

推荐答案

该问题假定要删除的节点已知，并且指向该节点的指针可用.

The problem assumes that the node to be deleted is known and a pointer to that node is available.

为了删除一个节点并将上一个和下一个节点连接在一起，您需要知道它们的指针.在双向链接列表中，两个指针在要删除的节点中均可用.在这种情况下，时间复杂度是恒定的，即O(1).

In order to delete a node and connect the previous and the next node together, you need to know their pointers. In a doubly-linked list, both pointers are available in the node that is to be deleted. The time complexity is constant in this case, i.e., O(1).

在单链列表中，指向前一个节点的指针是未知的，只能通过从头开始遍历该列表直至到达具有下一个节点指针的节点才能找到该列表，该指针指向要删除的节点.在这种情况下，时间复杂度为O(n).

Whereas in a singly-linked list, the pointer to the previous node is unknown and can be found only by traversing the list from head until it reaches the node that has a next node pointer to the node that is to be deleted. The time complexity in this case is O(n).

在仅通过值知道要删除的节点的情况下，必须搜索列表，并且在单链接和双链接列表中时间复杂度都变为O(n).

In cases where the node to be deleted is known only by value, the list has to be searched and the time complexity becomes O(n) in both singly- and doubly-linked lists.

这篇关于单链表和双链表中节点删除的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！