Сложность времени удаления элементов с двойным списком списков?

Ответ 1

Для двусвязного списка это постоянное время для удаления элемента, когда вы знаете, где он находится.

Для односвязного списка это постоянное время для удаления элемента, когда вы знаете, где он и его предшественник.

С этой ссылкой вы указываете, что удаление одиночного связанного списка в качестве O(n) и дважды связанное в качестве O(1), это означает, что, когда вы уже знаете, где элемент, который вы хотите удалить, но не что-то еще.

В этом случае для двусвязного списка вы можете просто использовать указатели prev и next, чтобы удалить его, предоставив вам O(1). Игнорируя края, где вы находитесь в голове или хвосте, это означает что-то вроде:

corpse->prev->next = corpse->next
corpse->next->prev = corpse->prev
free (corpse)

Однако в одном единственном списке, где вы знаете только node, который хотите удалить, вы не можете использовать corpse->prev, чтобы получить тот, который предшествует ему, потому что нет ссылки prev.

Вместо этого вы должны найти предыдущий элемент, пройдя список из головы, ища тот, у которого есть next элемента, который вы хотите удалить. Это займет O(n), после чего еще раз O(1) для фактического удаления, например (опять же, игнорируя случаи краев для простоты):

lefty = head
while lefty->next != corpse:
    lefty = lefty-> next
lefty->next = corpse->next
free (corpse)

Вот почему две сложности различны в этой статье.

Ответ 2

Как указано, где ваша ссылка указывает на:

Стоимость изменения внутреннего элемента основана на том, что уже имеет указатель на него, если вам нужно сначала найти элемент, будет также затрата на извлечение элемента.

Итак, для линейного поиска DLL и SLL существует O (n), а удаление с помощью указателя - O (1).

Ответ 3

Сложность удаления в DLL O(1). Он также может быть O(1) в SLL, если предоставлен указатель на предшествующий элемент, а не на сам элемент.

Эта сложность предполагает, что вы знаете, где находится элемент.

т.е. сигнатура операции сродни remove_element(list* l, link* e) Поиск элемента O(n) в обоих случаях.

Ответ 4

@Матуку: Ты прав.

Я смиренно не согласен с большинством ответов здесь, пытаясь оправдать, как операция удаления для DLL - это O (1). Это не так.

Позвольте мне объяснить.

Почему мы рассматриваем сценарий, что мы "будем иметь указатель на node, который удаляется? LinkedLists (Singlely/Doubly) пересекаются линейно, что их определение. У них есть указатели только на голову/хвост. Как мы можем внезапно установить указатель на какой-то node между ними? Это нарушает цель этой структуры данных. И, исходя из этого предположения, если у меня есть список DLL, скажем, 1 миллион узлов, то мне также нужно поддерживать 1 млн. Указателей (пусть их называют указателями доступа), указывающих на каждый из этих узлов, чтобы я мог их удалить в O ( 1)? Итак, как я могу хранить эти 1 миллионные указатели доступа? И как узнать, какой указатель доступа указывает на правильные данные /node, которые я хочу удалить?

У нас есть пример реального мира, где у нас есть "указатель на данные, которые нужно удалить в 100% случаев?

И если вы знаете точное местоположение/указатель/ссылку/на node для удаления, зачем даже использовать LinkedList? Просто используйте массив! Для чего нужны массивы - прямой доступ к тому, что вы хотите!

Предполагая, что у вас есть прямой доступ к любому node, который вы хотите в DLL, противоречит идее LinkedList как концептуальной структуры данных. Поэтому я согласен с ОП, он прав. Я буду придерживаться этого - Doubly LinkedLists не может иметь O (1) для удаления любого node. Вам все равно нужно начинать с головы или хвоста, что сводит его к O (n).

" Если" у нас есть указатель на node, который нужно удалить, скажем X, то, конечно, это O (1), потому что у нас есть указатели на следующий и prev node мы можем удалить X. Но это большое, если это мнимое, а не реальное.

Мы не можем играть с определением священной структуры данных, называемой LinkedLists, для некоторых странных предположений, которые мы можем иметь время от времени.