В информатике двусвязный список — это связанная структура данных , состоящая из набора последовательно связанных записей , называемых узлами . Каждый узел содержит три поля : два поля ссылки ( ссылки на предыдущий и следующий узел в последовательности узлов) и одно поле данных. Предыдущая и следующая ссылки начального и конечного узлов соответственно указывают на какой-то терминатор, обычно сторожевой узел или null , чтобы облегчить обход списка. Если существует только один дозорный узел, то список циклически связан через дозорный узел. Его можно представить как два односвязных списка, сформированных из одних и тех же элементов данных, но в противоположном последовательном порядке.
Две связи узла позволяют перемещаться по списку в любом направлении. Хотя добавление или удаление узла в двусвязном списке требует изменения большего количества связей, чем те же операции в односвязном списке, эти операции проще и потенциально более эффективны (для узлов, отличных от первых узлов), поскольку нет необходимости отслеживать предыдущий узел во время обхода или нет необходимости просматривать список, чтобы найти предыдущий узел, чтобы его ссылку можно было изменить.
Первый и последний узлы двусвязного списка для всех практических приложений доступны немедленно (т. е. доступны без обхода и обычно называются головой и хвостом ) и, следовательно, позволяют обход списка с начала или конца списка соответственно: например , обход списка от начала до конца или от конца к началу при поиске в списке узла с определенным значением данных. Любой узел двусвязного списка, однажды полученный, можно использовать для начала нового обхода списка в любом направлении (к началу или концу) от данного узла.
Поля ссылок узла двусвязного списка часто называются next и previous или вперед и назад . Ссылки, хранящиеся в полях ссылок, обычно реализуются как указатели , но (как и в любой связанной структуре данных) они также могут быть смещениями адресов или индексами в массиве , в котором находятся узлы.
Рассмотрим следующие базовые алгоритмы, написанные на языке Ada:
запись DoubleLinkedNode { next // Ссылка на следующий узел prev // Ссылка на данные предыдущего узла // Данные или ссылка на данные}запись DoublyLinkedList { DoublyLinkedNode firstNode // указывает на первый узел списка DoublyLinkedNode LastNode // указывает на последний узел списка}Обход двусвязного списка может осуществляться в любом направлении. На самом деле, при желании направление обхода можно менять много раз. Обход часто называют итерацией , но такой выбор терминологии неудачен, поскольку итерация имеет четко определенную семантику (например, в математике), которая не аналогична обходу .
Нападающие
узел:= list.firstNode , пока узел ≠ ноль <сделайте что-нибудь с node.data> узел := узел.следующий
Назад
узел:= list.lastNode , пока узел ≠ ноль <сделайте что-нибудь с node.data> узел := node.prev
Эти симметричные функции вставляют узел после или перед данным узлом:
функция InsertAfter( Список списка , Узел узла, Узел newNode) newNode.prev := узел if node.next == null newNode.next := null -- (не всегда необходимо) list.lastNode:= новыйNode еще новыйУзел.следующий := узел.следующий node.next.prev := новыйузел node.next := новыйузел
функция InsertBefore ( Список списка , Узел узла, Узел newNode) новыйNode.next := узел if node.prev == null newNode.prev := null -- (не всегда необходимо) list.firstNode := новыйNode еще новыйNode.prev := node.prev node.prev.next := новыйузел node.prev := новыйузел
Нам также нужна функция для вставки узла в начало возможно пустого списка:
функция InsertBeginning ( список списка , узел newNode), если list.firstNode == null list.firstNode := новыйNode list.lastNode:= новыйNode newNode.prev := ноль новыйNode.next: = ноль еще InsertBefore (список, список.firstNode, новыйNode)
Симметричная функция вставляется в конец:
функция InsertEnd ( список списка , узел newNode), если list.lastNode == null InsertBeginning (список, новый узел) еще InsertAfter (список, список.lastNode, новыйNode)
Удаление узла проще, чем вставка, но требует специальной обработки, если удаляемый узел является firstNode или LastNode :
функция удаления ( список списка , узел узла), если node.prev == null list.firstNode := node.next еще node.prev.next := node.next если node.next == ноль 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 узел := узел.следующийв то время как узел ≠ someNode
Назад
узел := someNode сделать сделайте что-нибудь с node.value узел := node.prevв то время как узел ≠ someNode
Обратите внимание на отсрочку теста до конца цикла. Это важно для случая, когда список содержит только один узел someNode .
Эта простая функция вставляет узел в двусвязный циклический список после заданного элемента:
функция InsertAfter( Узел узла, Узел newNode) новыйУзел.следующий := узел.следующий newNode.prev := узел node.next.prev := новыйузел node.next := новыйузел
Чтобы выполнить «insertBefore», мы можем просто «insertAfter(node.prev, newNode)».
Для вставки элемента в возможно пустой список требуется специальная функция:
функция InsertEnd ( список списка , узел узла), если list.lastNode == null node.prev := узел node.next := узел еще InsertAfter(list.lastNode, узел) list.lastNode := узел
Для вставки в начале мы просто «insertAfter(list.lastNode, node)».
Наконец, удаление узла должно учитывать случай, когда список пуст:
функция удаления ( список списка , узел узла); если node.next == узел list.lastNode:= ноль еще 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 ( Node node, Node newNode), если node.prev == null ошибка «Узел отсутствует в списке» новыйNode.prev := node.prev atAddress(newNode.prev) := newNode новыйNode.next := узел node.prev = адресOf(newNode.next)
функция InsertAfter( Узел узла, Узел newNode) новыйУзел.следующий := узел.следующий если newNode.next != ноль newNode.next.prev = адресOf(newNode.next) node.next := новыйузел newNode.prev := адресOf(node.next)
Чтобы удалить узел, мы просто изменяем ссылку, на которую указывает prev , независимо от того, был ли узел первым в списке.
функция удаления ( узел Node ) atAddress(node.prev) := node.next если node.next != ноль node.next.prev = node.prev уничтожить узел