如果我们不知道节点的位置，那么单链接列表和双重链接列表是否确实需要O(n)删除时间？
我的理解是，我们需要遍历节点，以了解单个链接列表中节点的先前指针和节点的下一个指针。删除的单链接列表的时间复杂性是O(n)。
对于双重链接的列表，由于我们知道要删除节点的上一个和下一个指针，因此时间复杂性为O(1)。
它是 O(n) to 在两种情况下都定位 a节点(伪代码均遵循此处，在下面的所有情况下(：
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)在 singly 链接列表中删除一个节点，因为您需要首先在之前找到节点 您想删除：
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)操作是 stly O(n)，因为它是线性依赖于节点的数量的。
因此，要删除您尚未指向指针的节点，在这两种情况下都是O(n)，如果您天真地进行了单独链接的列表，这只是每个n所做的工作都会更大(例如"定位节点以删除"然后"在一个"之前定位节点"(。
通常，您不会做到这一点。您的删除函数在前进时会记住上一个节点，这样，一旦您找到要删除的节点，您也将拥有一个节点。 可以这样做的事情，我们实际上在要删除的元素
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.next
除了现有答案之外，如果我们允许移动节点的内容，则可以从单个链接的列表中删除节点的常数恒定时间。。我们将下一个节点的内容移至要删除的节点，然后将指针转到下一个节点之后的下一个节点点。