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