Для двусвязного списка это постоянное время для удаления элемента , когда вы знаете, где он находится.
Для односвязного списка это постоянное время для удаления элемента, когда вы знаете, где он и его предшественник.
Поскольку эта ссылка, на которую вы указываете, показывает удаление односвязного списка как O(n) и двусвязное как O(1), наверняка вы уже знаете, где находится элемент, который хотите удалить, но не что-нибудь еще.
В этом случае для двусвязного списка вы можете просто использовать указатели prev и next, чтобы удалить его, давая вам O(1). Игнорирование крайних случаев, когда вы находитесь в голове или хвосте, это означает что-то вроде:
corpse->prev->next = corpse->next
corpse->next->prev = corpse->prev
free (corpse)
Однако в односвязном списке, в котором вы знаете только узел, который хотите удалить, вы не можете использовать corpse->prev для получения предыдущего, потому что - это нет prev ссылки.
Вместо этого вы должны найти предыдущий элемент, пройдя по списку из головы, ища тот, у которого есть next элемента, который вы хотите удалить. Это займет O(n), после чего еще раз O(1) для фактического удаления, например (опять же, игнорируя крайние случаи для простоты):
lefty = head
while lefty->next != corpse:
lefty = lefty-> next
lefty->next = corpse->next
free (corpse)
Вот , почему эти две сложности отличаются в этой статье.
Кроме того, в односвязном списке есть оптимизации, которые могут сделать удаление O(n) (удаление фактически равно O (1), как только вы нашли элемент, который хотите удалить, и предыдущий элемент) , В терминах кода это выглядит примерно так:
# Delete a node, returns true if found, otherwise false.
def deleteItem(key):
# Special cases (empty list and deleting head).
if head == null: return false
if head.data == key:
curr = head
head = head.next
free curr
return true
# Search non-head part of list (so prev always exists).
prev = head
curr = head.next
while curr != null:
if curr.data == key:
# Found it so delete (using prev).
prev.next = curr.next
free curr
return true
# Advance to next item.
prev = curr
curr = curr.next
# Not found, so fail.
return false