Двусвязный список
 | Эта статья нуждается в дополнительных цитатах для проверки . ( январь 2014 г. ) |
В информатике — двусвязный список это связанная структура данных , состоящая из набора последовательно связанных записей, называемых узлами . Каждый узел содержит три поля : два поля ссылки ( ссылки на предыдущий и следующий узел в последовательности узлов) и одно поле данных. и конечного узлов ссылки начального Предыдущая и следующая , соответственно, указывают на какой-то терминатор, обычно сторожевой узел или null , чтобы облегчить обход списка. Если существует только один дозорный узел, то список циклически связан через дозорный узел. Его можно представить как два односвязных списка, сформированных из одних и тех же элементов данных, но в противоположном последовательном порядке.
Две связи узла позволяют перемещаться по списку в любом направлении. Хотя добавление или удаление узла в двусвязном списке требует изменения большего количества связей, чем те же операции в односвязном списке, эти операции проще и потенциально более эффективны (для узлов, отличных от первых узлов), поскольку нет необходимости отслеживать предыдущий узел во время обхода или нет необходимости просматривать список, чтобы найти предыдущий узел, чтобы его ссылку можно было изменить.
Номенклатура и реализация
[ редактировать ]Первый и последний узлы двусвязного списка для всех практических приложений доступны немедленно (т. е. доступны без обхода и обычно называются головой и хвостом ) и, следовательно, позволяют обход списка с начала или конца списка соответственно: например , обход списка от начала до конца или от конца к началу при поиске в списке узла с определенным значением данных. Любой узел двусвязного списка, однажды полученный, можно использовать для начала нового обхода списка в любом направлении (к началу или концу) от данного узла.
Поля ссылок узла двусвязного списка часто называются next и previous или вперед и назад . Ссылки, хранящиеся в полях ссылок, обычно реализуются как указатели , но (как и в любой связанной структуре данных) они также могут быть смещениями адресов или индексами в массиве , в котором находятся узлы.
Основные алгоритмы
[ редактировать ]Рассмотрим следующие базовые алгоритмы, написанные на языке Ada:
Открытие двусвязных списков
[ редактировать ]record DoublyLinkedNode {
next // A reference to the next node
prev // A reference to the previous node
data // Data or a reference to data
}
record DoublyLinkedList {
DoublyLinkedNode firstNode // points to first node of list
DoublyLinkedNode lastNode // points to last node of list
}
Обход списка
[ редактировать ]Обход двусвязного списка может осуществляться в любом направлении. На самом деле, при желании направление обхода можно менять много раз. Обход часто называют итерацией , но такой выбор терминологии неудачен, поскольку итерация имеет четко определенную семантику (например, в математике), которая не аналогична обходу .
Нападающие
node := list.firstNode
while node ≠ null
<do something with node.data>
node := node.next
Назад
node := list.lastNode
while node ≠ null
<do something with node.data>
node := node.prev
Вставка узла
[ редактировать ]Эти симметричные функции вставляют узел после или перед данным узлом:
function insertAfter(List list, Node node, Node newNode)
newNode.prev := node
if node.next == null
newNode.next := null -- (not always necessary)
list.lastNode := newNode
else
newNode.next := node.next
node.next.prev := newNode
node.next := newNode
function insertBefore(List list, Node node, Node newNode)
newNode.next := node
if node.prev == null
newNode.prev := null -- (not always necessary)
list.firstNode := newNode
else
newNode.prev := node.prev
node.prev.next := newNode
node.prev := newNode
Нам также нужна функция для вставки узла в начало возможно пустого списка:
function insertBeginning(List list, Node newNode)
if list.firstNode == null
list.firstNode := newNode
list.lastNode := newNode
newNode.prev := null
newNode.next := null
else
insertBefore(list, list.firstNode, newNode)
Симметричная функция вставляется в конец:
function insertEnd(List list, Node newNode)
if list.lastNode == null
insertBeginning(list, newNode)
else
insertAfter(list, list.lastNode, newNode)
Удаление узла
[ редактировать ]Удаление узла проще, чем вставка, но требует специальной обработки, если удаляемый узел является firstNode или LastNode :
function remove(List list, Node node)
if node.prev == null
list.firstNode := node.next
else
node.prev.next := node.next
if node.next == null
list.lastNode := node.prev
else
node.next.prev := node.prev
Одним из тонких последствий описанной выше процедуры является то, что удаление последнего узла списка устанавливает для firstNode и LastNode значение null , и поэтому удаление последнего узла из одноэлементного списка выполняется правильно. Обратите внимание, что нам также не нужны отдельные методы «removeBefore» или «removeAfter», поскольку в двусвязном списке мы можем просто использовать «remove(node.prev)» или «remove(node.next)», если они допустимы. Это также предполагает, что удаляемый узел гарантированно существует. Если узел не существует в этом списке, потребуется некоторая обработка ошибок.
Круговые двусвязные списки
[ редактировать ]Обход списка
[ редактировать ]Предполагая, что someNode — это некоторый узел в непустом списке, этот код проходит через этот список, начиная с someNode (подойдет любой узел):
Нападающие
node := someNode
do
do something with node.value
node := node.next
while node ≠ someNode
Назад
node := someNode
do
do something with node.value
node := node.prev
while node ≠ someNode
Обратите внимание на отсрочку теста до конца цикла. Это важно для случая, когда список содержит только один узел someNode .
Вставка узла
[ редактировать ]Эта простая функция вставляет узел в двусвязный циклически связанный список после заданного элемента:
function insertAfter(Node node, Node newNode)
newNode.next := node.next
newNode.prev := node
node.next.prev := newNode
node.next := newNode
Чтобы выполнить «insertBefore», мы можем просто «insertAfter(node.prev, newNode)».
Для вставки элемента в возможно пустой список требуется специальная функция:
function insertEnd(List list, Node node)
if list.lastNode == null
node.prev := node
node.next := node
else
insertAfter(list.lastNode, node)
list.lastNode := node
Для вставки в начале мы просто «insertAfter(list.lastNode, node)».
Наконец, удаление узла должно учитывать случай, когда список пуст:
function remove(List list, Node node);
if node.next == node
list.lastNode := null
else
node.next.prev := node.prev
node.prev.next := node.next
if node == list.lastNode
list.lastNode := node.prev;
destroy node
Удаление узла
[ редактировать ]Как и в двусвязных списках, «removeAfter» и «removeBefore» можно реализовать с помощью «remove(list, node.prev)» и «remove(list, node.next)».
Расширенные концепции
[ редактировать ]Асимметричный двусвязный список
[ редактировать ]Асимметричный двусвязный список находится где-то между односвязным списком и обычным двусвязным списком. Он разделяет некоторые функции с односвязным списком (однонаправленный обход), а другие - с двусвязным списком (простота модификации).
Это список, в котором предыдущая ссылка каждого узла указывает не на предыдущий узел, а на ссылку на самого себя. Хотя это не имеет большого значения между узлами (оно просто указывает на смещение внутри предыдущего узла), оно меняет заголовок списка: это позволяет первому узлу firstNode . легко изменять ссылку [1] [2]
Пока узел находится в списке, его предыдущая ссылка никогда не равна нулю.
Вставка узла
[ редактировать ]Чтобы вставить узел перед другим, мы меняем ссылку, указывающую на старый узел, используя ссылку prev ; ссылку нового узла затем установите следующую этого узла так, чтобы она указывала на старый узел, и соответствующим образом измените предыдущую ссылку .
function insertBefore(Node node, Node newNode)
if node.prev == null
error "The node is not in a list"
newNode.prev := node.prev
atAddress(newNode.prev) := newNode
newNode.next := node
node.prev = addressOf(newNode.next)
function insertAfter(Node node, Node newNode)
newNode.next := node.next
if newNode.next != null
newNode.next.prev = addressOf(newNode.next)
node.next := newNode
newNode.prev := addressOf(node.next)
Удаление узла
[ редактировать ]Чтобы удалить узел, мы просто изменяем ссылку, на которую указывает prev , независимо от того, был ли узел первым в списке.
function remove(Node node)
atAddress(node.prev) := node.next
if node.next != null
node.next.prev = node.prev
destroy node
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Предотвращение сбоев игры, связанных со связанными списками» . 9 сентября 2012 г.
- ^ «Кохо, за «Кодекс чести» » . Гитхаб . 20 апреля 2022 г.