Когда список с двойной связью более эффективен, чем отдельный список?

В интервью сегодня мне задали вопрос.

Помимо ответа на реверсирование списка и как на обратный, так и на задний ход, в нем было что-то "фундаментальное", которое продолжал подчеркивать интервьюер. Я сдался и, конечно, после интервью провел несколько исследований. Кажется, что вставка и удаление более эффективны в двусвязном списке, чем в одиночном списке. Я не совсем уверен, как это может быть более эффективным для двусвязного списка, поскольку очевидно, что для изменения требуется больше ссылок. Кто-нибудь может объяснить секрет? Я, честно говоря, провел довольно много исследований и не понял, с моей главной проблемой, являющейся фактом, что поиск O (n) по-прежнему необходим для двойного связанного списка.

Ответ 1

Вставка явно меньше работает в односвязном списке, если вы довольствуетесь всегда вставкой в голову или после некоторого известного элемента. (То есть вы не можете вставить перед известным элементом, но смотрите ниже.)

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

Один из способов сделать это - заставить API удаления работать с предшественником элемента, который нужно удалить. Это отражает API-интерфейс вставки, который принимает элемент, который будет предшественником нового элемента, но он не очень удобен и трудно документировать. Это обычно возможно. Вообще говоря, вы попадаете в элемент списка, перемещая список.

Конечно, вы можете просто искать список с самого начала, чтобы найти элемент, который нужно удалить, чтобы вы знали, что его предшественник. Это предполагает, что API-интерфейс удаления включает в себя заголовок списка, что также неудобно. Кроме того, поиск тупо медленный.

То, что вряд ли кто-либо использует, но на самом деле довольно эффективно, заключается в том, чтобы определить одноименный итератор списка как указатель на элемент, предшествующий текущей цели итератора. Это просто, только одна косвенность медленнее, чем использование указателя непосредственно к элементу, и делает как вставку, так и удаление быстрым. Недостатком является то, что удаление элемента может привести к недействительности других итераторов для перечисления элементов, что раздражает. (Это не отменяет итератор для удаляемого элемента, что приятно для обходов, которые удаляют некоторые элементы, но это не так много компенсации.)

Если удаление не важно, возможно, из-за того, что структуры данных неизменяемы, односвязные списки предлагают другое действительно полезное свойство: они позволяют совместное использование структуры. Односвязный список может с радостью быть хвостом нескольких головок, что невозможно для двусвязного списка. По этой причине односвязные списки традиционно были простой структурой данных для функциональных языков.

Ответ 2

Вот какой код, который дал мне яснее... Имея:

class Node{
      Node next;
      Node prev;
}

УДАЛИТЬ a node в ОДИНОЧНОМ СПИСКЕ -O (n) -

Вы не знаете, что является предшествующим node, поэтому вам нужно пройти этот список до тех пор, пока не найдете его:

deleteNode(Node node){
    prevNode = tmpNode;
    tmpNode = prevNode.next;

    while (tmpNode != null) {
        if (tmpNode == node) {
            prevNode.next = tmpNode.next;
        }
        prevNode = tmpNode;
        tmpNode = prevNode.next;
    }
}

УДАЛИТЬ a node в ДВОЙНОМ СПИСОК ЛИНИИ -O (1) -

Вы можете просто обновить ссылки следующим образом:

deleteNode(Node node){
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Ответ 3

Вот мои мысли о двусвязном списке:

У вас есть готовый доступ\вставка на обоих концах.
он может работать как очередь и стек одновременно.
Node Для удаления не требуется никаких дополнительных указателей.
Вы можете применить обход Hill-Climb, поскольку у вас уже есть доступ на обоих концах.
Если вы храните числовые значения и сортируете свой список, вы можете сохранить указатель/переменную для медианы, тогда операция поиска может быть очень оптимальной с использованием статистического подхода.

Ответ 4

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

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

Ответ 5

'Помимо ответа на вспять список и как перемотку вперед, так и назад, было что-то "фундаментальное".

Никто, кажется, не упомянул: в дважды связанном списке можно повторно вставить удаленный элемент, просто указав на удаленный элемент. См. Документ Knuth Dancing Links. Я думаю, что это довольно фундаментальный.