В информатике , А дважды связанный список представляет собой сшитую структуру данных , которая состоит из множества последовательно соединенных записей , называемых узлами . Каждый узел содержит три поля : два поля ссылок ( ссылки на предыдущий и следующий узел в последовательности узлов) и одно поле данных. Предыдущие и следующие ссылки начального и конечного узлов соответственно указывают на некоторый терминатор, обычно на контрольный узел или ноль., чтобы облегчить обход списка. Если имеется только один контрольный узел, то список циклически связан через контрольный узел. Его можно представить как два односвязных списка, сформированных из одних и тех же элементов данных, но в противоположных последовательных порядках.
Две связи узлов позволяют перемещаться по списку в любом направлении. Хотя добавление или удаление узла в двусвязном списке требует изменения большего количества ссылок, чем те же операции в односвязном списке, операции проще и потенциально более эффективны (для узлов, отличных от первых узлов), поскольку нет необходимости отслеживать предыдущий узел во время обхода или нет необходимости перемещаться по списку, чтобы найти предыдущий узел, чтобы его ссылку можно было изменить.
Номенклатура и реализация
Первый и последний узлы двусвязного списка доступны немедленно (т. Е. Доступны без обхода и обычно называются заголовком и хвостом ) и, следовательно, позволяют обход списка с начала или с конца списка, соответственно: например, обход списка от начала до конца или от конца до начала при поиске в списке узла с определенным значением данных. Любой узел двусвязного списка, однажды полученный, может использоваться для начала нового обхода списка в любом направлении (к началу или к концу) от данного узла.
Поля ссылок узла двусвязного списка часто называются следующим и предыдущим или вперед и назад . Ссылки, хранящиеся в полях ссылок, обычно реализуются как указатели , но (как и в любой связанной структуре данных) они также могут быть адресными смещениями или индексами в массиве, где находятся узлы.
Базовые алгоритмы
Рассмотрим следующие базовые алгоритмы, написанные на Аде:
Открытые двусвязные списки
record DoublyLinkedNode { next // Ссылка на следующий узел prev // Ссылка на данные предыдущего узла // Данные или ссылка на данные}
record DoublyLinkedList { DoublyLinkedNode firstNode // указывает на первый узел списка DoublyLinkedNode lastNode // указывает на последний узел списка}
Перемещение по списку
Обход двусвязного списка может происходить в любом направлении. Фактически, направление обхода при желании может меняться много раз. Обход часто называют итерацией , но такой выбор терминологии неудачен, поскольку итерация имеет четко определенную семантику (например, в математике), которая не аналогична обходу .
Нападающие
узел: = list.firstNode, а узел ≠ null <сделать что-нибудь с node.data> узел: = node.next
Назад
узел: = list.lastNode, а узел ≠ null <сделать что-нибудь с node.data> узел: = node.prev
Вставка узла
Эти симметричные функции вставляют узел после или до данного узла:
функция insertAfter ( список списка, узел узла, узел newNode) newNode.prev: = узел если node.next == null newNode.next: = null - (не всегда необходимо) list.lastNode: = newNode еще newNode.next: = node.next node.next.prev: = newNode node.next: = newNode
функция insertBefore ( список списка, узел узла, узел newNode) newNode.next: = узел если node.prev == null newNode.prev: = null - (не всегда необходимо) list.firstNode: = newNode еще newNode.prev: = node.prev node.prev.next: = newNode node.prev: = newNode
Нам также нужна функция для вставки узла в начало возможно пустого списка:
функция insertBeginning ( список списка, узел newNode), если list.firstNode == null list.firstNode: = newNode list.lastNode: = newNode newNode.prev: = null newNode.next: = ноль еще insertBefore (список, list.firstNode, newNode)
В конце вставляется симметричная функция:
функция insertEnd ( список списка, узел newNode), если list.lastNode == null insertBeginning (список, новый узел) еще insertAfter (список, список.lastNode, newNode)
Удаление узла
Удаление узла проще, чем вставка, но требует специальной обработки, если удаляемый узел является firstNode или lastNode :
функция удалить ( список списка, узел узла), если node.prev == null list.firstNode: = node.next еще node.prev.next: = node.next если node.next == null list.lastNode: = node.prev еще node.next.prev: = node.prev
Одним из тонких следствий вышеупомянутой процедуры является то, что при удалении последнего узла списка для firstNode и lastNode устанавливается значение NULL , и поэтому он правильно обрабатывает удаление последнего узла из одноэлементного списка. Обратите внимание, что нам также не нужны отдельные методы removeBefore или removeAfter, потому что в двусвязном списке мы можем просто использовать remove (node.prev) или remove (node.next), если они допустимы. Это также предполагает, что удаляемый узел гарантированно существует. Если узел не существует в этом списке, потребуется некоторая обработка ошибок.
Круговые двусвязные списки
Перемещение по списку
Предполагая, что someNode является некоторым узлом в непустом списке, этот код проходит через этот список, начиная с someNode ( подойдет любой узел):
Нападающие
узел: = someNode делать сделать что-нибудь с node.value узел: = node.nextпока узел ≠ someNode
Назад
узел: = someNode делать сделать что-нибудь с node.value узел: = node.prevпока узел ≠ someNode
Обратите внимание на перенос теста до конца цикла. Это важно для случая, когда список содержит только один узел someNode .
Вставка узла
Эта простая функция вставляет узел в дважды связанный список с круговой связью после заданного элемента:
функция insertAfter ( узел узла, узел newNode) newNode.next: = node.next newNode.prev: = узел node.next.prev: = newNode node.next: = newNode
Чтобы выполнить «insertBefore», мы можем просто «insertAfter (node.prev, newNode)».
Для вставки элемента в возможно пустой список требуется специальная функция:
функция insertEnd ( список списка, узел узла), если list.lastNode == null node.prev: = узел node.next: = узел еще insertAfter (список.lastNode, узел) list.lastNode: = узел
Чтобы вставить в начале, мы просто "insertAfter (list.lastNode, node)".
Наконец, удаление узла должно иметь дело со случаем, когда список пуст:
функция remove ( список списка, узел узла); если node.next == node list.lastNode: = null еще node.next.prev: = node.prev node.prev.next: = node.next если узел == list.lastNode list.lastNode: = node.prev; уничтожить узел
Удаление узла
Как и в двусвязных списках, «removeAfter» и «removeBefore» могут быть реализованы с помощью «remove (list, node.prev)» и «remove (list, node.next)».
Продвинутые концепции
Асимметричный двусвязный список
Асимметричный двусвязный список находится где-то между односвязным списком и обычным двусвязным списком. Он разделяет некоторые функции с односвязным списком (односторонний обход) и другими из двусвязного списка (простота модификации).
Это список, в котором предыдущая ссылка каждого узла указывает не на предыдущий узел, а на ссылку на себя. Хотя это не имеет большого значения между узлами (он просто указывает на смещение внутри предыдущего узла), он меняет заголовок списка: он позволяет первому узлу легко изменять ссылку firstNode . [1] [2]
Пока узел находится в списке, его предыдущая ссылка никогда не будет нулевой.
Вставка узла
Чтобы вставить узел перед другим, мы меняем ссылку, указывающую на старый узел, используя ссылку prev ; затем установите следующую ссылку нового узла так, чтобы она указывала на старый узел, и соответствующим образом измените предыдущую ссылку этого узла .
функция insertBefore ( узел узла, узел newNode), если node.prev == null ошибка "Узел отсутствует в списке" newNode.prev: = node.prev atAddress (newNode.prev): = newNode newNode.next: = узел node.prev = addressOf (новыйNode.next)
функция insertAfter ( узел узла, узел newNode) newNode.next: = node.next если newNode.next! = null newNode.next.prev = addressOf (newNode.next) node.next: = newNode newNode.prev: = addressOf (node.next)
Удаление узла
Чтобы удалить узел, мы просто изменяем ссылку, на которую указывает prev , независимо от того, был ли узел первым в списке.
функция удалить ( узел узла) atAddress (node.prev): = node.next если node.next! = null node.next.prev = node.prev уничтожить узел