Сложность времени удаления узлов в одно- и двусвязных списках

Question

Почему временная сложность удаления узла в дважды связанных списках (O (1)) быстрее, чем удаление узлов в односвязных списках (O (n))?

Answer 1

Это связано со сложностью фиксации следующего указателя в узле, предшествующего тому, который вы удаляете.

Answer 2

Потому что вы не можете смотреть назад ...

Answer 3

Проблема предполагает, что узел должен быть удален, как известно, и указатель на этот узел доступен.

Чтобы удалить узел и связать предыдущий и следующий узел вместе, вам необходимо знать их указатели. В двусвязном списке оба указателя доступны в узле, который необходимо удалить. Временная сложность в этом случае постоянна, т. Е. O (1).

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

В тех случаях, когда удаляемый узел известен только по значению, список необходимо искать, а временная сложность становится O (n) как в одиночных, так и в двусвязных списках.

Answer 4

Вставка и удаление в известном положении - O (1). Однако найти эту позицию O (n), если она не является головкой или хвостом списка.

Когда мы говорим о сложности ввода и удаления, мы обычно предполагаем, что мы уже знаем, где это произойдет.

Answer 5

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

Answer 6

Фактическое удаление в односвязных списках также может быть реализовано в O (1).

Учитывая односвязанны список со следующим состоянием:

SinglyLinkedList: 
    Node 1 -> Node 2 
    Node 2 -> Node 3 
    Node 3 -> None 

    Head = Node 3 

Мы можем реализовать delete Note 2 таким образом:

Node 2 Value <- Node 3 Value 
Node 2 -> None 

Здесь мы заменяем значение Node 2 со значением его следующей node (Node 3) и установите следующий указатель на значение следующего указателя значения Node 3 (None), пропустив теперь фактически «дубликат» Node 3. Таким образом, никакого обхода не требуется.