Двусвязный список - Doubly linked list

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Двусвязный список»  – Новости  · газеты  · книги  · ученый  · JSTOR (Январь 2014) (Узнайте, как и когда удалить этот шаблон сообщения)

В Информатика, а двусвязный список это связанная структура данных который состоит из набора последовательно связанных записи называется узлы. Каждый узел содержит три поля: два поля ссылок (Рекомендации к предыдущему и следующему узлу в последовательности узлов) и одно поле данных. Начальный и конечный узлы ' предыдущий и следующий ссылки, соответственно, указывают на какой-то терминатор, обычно дозорный узел или же ноль, чтобы облегчить обход списка. Если имеется только один контрольный узел, то список циклически связан через контрольный узел. Его можно представить как два односвязные списки формируется из тех же элементов данных, но в противоположном последовательном порядке.

Двусвязный список, узлы которого содержат три поля: ссылку на предыдущий узел, целочисленное значение и ссылку на следующий узел.

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

Номенклатура и реализация

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

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

Базовые алгоритмы

Рассмотрим следующие базовые алгоритмы, написанные на Ada:

Открытые двусвязные списки

записывать DoublyLinkedNode {    следующий // Ссылка на следующий узел    предыдущий // Ссылка на предыдущий узел    данные // Данные или ссылка на данные}

записывать DoublyLinkedList {     DoublyLinkedNode firstNode // указывает на первый узел списка     DoublyLinkedNode lastNode // указывает на последний узел списка}

Перемещение по списку

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

Нападающие

узел: = list.firstNodeпока узел ≠ ноль    <сделать что-нибудь с node.data> node: = node.next

Назад

узел: = list.lastNodeпока узел ≠ ноль    <сделать что-нибудь с node.data> node: = node.prev

Вставка узла

Эти симметричные функции вставляют узел после или до данного узла:

функция insertAfter (Список список, Узел узел, Узел newNode) newNode.prev: = узел если node.next == ноль        newNode.next: = ноль - (не всегда необходимо)        list.lastNode: = newNode еще        newNode.next: = node.next node.next.prev: = newNode node.next: = newNode

функция insertBefore (Список список, Узел узел, Узел newNode) newNode.next: = узел если node.prev == ноль        newNode.prev: = ноль - (не всегда необходимо)        list.firstNode: = newNode еще        newNode.prev: = node.prev node.prev.next: = newNode node.prev: = newNode

Нам также нужна функция для вставки узла в начало возможно пустого списка:

функция insertBeginning (Список список, Узел newNode) если list.firstNode == ноль        list.firstNode: = newNode list.lastNode: = newNode newNode.prev: = null newNode.next: = null еще        insertBefore (список, list.firstNode, newNode)

В конце вставляется симметричная функция:

функция insertEnd (Список список, Узел newNode) если list.lastNode == ноль         insertBeginning (список, новый узел) еще         insertAfter (список, список.lastNode, newNode)

Удаление узла

Удаление узла проще, чем вставка, но требует специальной обработки, если удаляемый узел является firstNode или же lastNode:

функция удалять(Список список, Узел узел)    если node.prev == ноль        list.firstNode: = node.next еще        node.prev.next: = node.next если node.next == ноль        list.lastNode: = node.prev еще        node.next.prev: = node.prev

Одним из тонких следствий описанной выше процедуры является то, что при удалении последнего узла списка оба firstNode и lastNode к ноль, и поэтому он правильно обрабатывает удаление последнего узла из одноэлементного списка. Обратите внимание, что нам также не нужны отдельные методы «removeBefore» или «removeAfter», потому что в двусвязном списке мы можем просто использовать «remove (node.prev)» или «remove (node.next)», если они допустимы. Это также предполагает, что удаляемый узел гарантированно существует. Если узел не существует в этом списке, тогда потребуется некоторая обработка ошибок.

Круговые двусвязные списки

Перемещение по списку

При условии, что someNode это некоторый узел в непустом списке, этот код проходит через этот список, начиная с someNode (подойдет любой узел):

Нападающие

узел: = someNodeделать    сделайте что-нибудь с node.value node: = node.nextпока узел ≠ someNode

Назад

узел: = someNodeделать    сделайте что-нибудь с node.value node: = node.prevпока узел ≠ someNode

Обратите внимание на перенос теста до конца цикла. Это важно для случая, когда список содержит только один узел. someNode.

Вставка узла

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

функция insertAfter (Узел узел, Узел newNode) newNode.next: = node.next newNode.prev: = node node.next.prev: = newNode node.next: = newNode

Чтобы выполнить «insertBefore», мы можем просто «insertAfter (node.prev, newNode)».

Для вставки элемента в возможно пустой список требуется специальная функция:

функция insertEnd (Список список, Узел узел) если list.lastNode == ноль        node.prev: = node node.next: = node еще        insertAfter (list.lastNode, node) list.lastNode: = узел

Чтобы вставить в начале, мы просто "insertAfter (list.lastNode, node)".

Наконец, удаление узла должно иметь дело со случаем, когда список пуст:

функция удалять(Список список, Узел узел); если node.next == список узлов.lastNode: = ноль    еще        node.next.prev: = node.prev node.prev.next: = node.next если узел == список.lastNode list.lastNode: = node.prev; разрушать узел

Удаление узла

Как и в двусвязных списках, «removeAfter» и «removeBefore» могут быть реализованы с помощью «remove (list, node.prev)» и «remove (list, node.next)».

Продвинутые концепции

Асимметричный двусвязный список

Асимметричный двусвязный список находится где-то между односвязным списком и обычным двусвязным списком. Он разделяет некоторые функции с односвязным списком (односторонний обход) и другими из двусвязного списка (простота модификации).

Это список, в котором каждый узел предыдущий ссылка указывает не на предыдущий узел, а на ссылку на себя. Хотя это не имеет большого значения между узлами (он просто указывает на смещение внутри предыдущего узла), он изменяет заголовок списка: он позволяет первому узлу изменять firstNode ссылку легко.^[1][2]

Пока узел находится в списке, его предыдущий ссылка никогда не бывает нулевой.

Вставка узла

Чтобы вставить узел перед другим, мы меняем ссылку, указывающую на старый узел, используя предыдущий связь; затем установите новый узел следующий ссылка, чтобы указать на старый узел, и изменить этот узел предыдущий ссылку соответственно.

функция insertBefore (Узел узел, Узел newNode) если node.prev == ноль        ошибка «Узел отсутствует в списке» newNode.prev: = node.prev atAddress (newNode.prev): = newNode newNode.next: = node node.prev = addressOf (newNode.next)

функция insertAfter (Узел узел, Узел newNode) newNode.next: = node.next если newNode.next! = ноль        newNode.next.prev = addressOf (newNode.next) node.next: = newNode newNode.prev: = addressOf (node.next)

Удаление узла

Чтобы удалить узел, мы просто изменяем ссылку, на которую указывает предыдущий, независимо от того, был ли узел первым в списке.

функция удалять(Узел узел) atAddress (node.prev): = node.next если node.next! = ноль        node.next.prev = node.prev разрушать узел

Смотрите также

• Связанный список XOR
• SLIP (язык программирования)

Рекомендации