在单列和双链表中删除的时间复杂度是多少？
在单列和双链表中删除的时间复杂度是多少？
提问于 2019-05-19 09:36:08
如果我们不知道节点的位置，那么单链接列表和双链接列表都需要O(n)时间删除是真的吗？
我的理解是，我们需要遍历到节点，才能知道单链表中节点的前一个指针和节点的下一个指针。因此，单链接列表删除的时间复杂性是O(n)。
对于双链接列表，由于我们知道要删除的节点的前一个和下一个指针，所以时间复杂性是O(1)。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-05-19 09:50:18
在这两种情况下都需要O(n)来定位节点(下面是伪代码，在以下所有情况下都是如此)：
def locate(key):
ptr = head
while ptr != null:
if ptr.key == key:
return ptr
ptr = ptr.next
return null仅给出双链接列表中的节点指针，删除一个节点是O(1)，因为您可以很容易地到达前一个节点：
def del (ptr):
if ptr == head: # head is special case
head = ptr.next
free ptr
return
ptr.prev.next = ptr.next
free ptr对于相同的条件(只有指针)，删除单链接列表中的节点是O(n)，因为您需要首先找到要删除的节点之前的节点：
def del (ptr):
if ptr == head: # head is special case
head = ptr.next
free ptr
return
prev = head
while prev.next != ptr:
prev = prev.next
prev.next = ptr.next
free ptr但是，两个O(n)操作仍然是O(n)，因为它与节点数成线性关系。
因此，要删除一个还没有指针的节点，在这两种情况下都是O(n)，如果您天真地这样做，那么对于单个链接列表来说，为每个n所做的工作就会更大(比如“定位节点删除”，然后“在该节点之前定位节点”)。
通常情况下，你不会那么做的。您的delete函数在前进时会记住前一个节点，这样，一旦找到要删除的节点，就会在它之前有一个节点，这样就不需要再进行搜索了。
这可能是这样的，我们实际上是在要删除的元素之前搜索元素：
def del (key):
if head == null: # no action on empty list
return
if head.key == key: # head is special case
temp = head
head = head.next
free temp
return
prev = head
while prev.next != null:
if prev.next.key == key:
temp = prev.next
prev.next = temp.next
free temp
return
prev = prev.nextStack Overflow用户
发布于 2019-05-21 00:33:07
除了现有的答案之外，如果允许移动节点的内容，还可以从单链接列表常量时间中删除节点，只要给出指向它的指针。我们会将下一个节点的内容移到要删除的节点中，并使指向下一个节点的指针指向下一个节点之后的节点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56206535
复制相关文章
相似问题
腾讯云开发者
