Связные списки

Связные списки — это стандартная структура данных в информатике. Связный список можно использовать, к примеру, для представления музыкального плейлиста или отслеживания истории действий.

Обзор

Связный список представляет собой линейную структуру данных, в которой каждый элемент хранит ссылку на следующий элемент в списке. Каждый элемент связного списка называется узлом. Узел — это контейнер, который содержит определённые данные и ссылку на следующий узел.

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

Когда использовать

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

Когда не использовать

В связных списках отсутствует возможность случайного доступа к элементам (к примеру, для выбора случайного игрока из списка). Эти списки не такие эффективные, как массивы, когда нужно получить доступ к узлу в середине списка, ведь вам придётся начать с начала, чтобы добраться до нужного узла.

Реализация в Verse

API Verse не имеет встроенной реализации связных списков, но вы можете реализовать их самостоятельно.

Связные списки состоят из узлов, и вам нужно определить класс для их представления. Вот пример общего типа узла:

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    var Next:?list_node = false
    Data:any = {}

Здесь есть переменная Next типа option, которая хранит ссылку на следующий узел в списке типа list_node. Обратите внимание, что Next должна быть переменной option, поскольку один узел не всегда содержит ссылку на следующий узел (например, в конечном узле связного списка нет такой ссылки). Если нужно изменить связи в списке динамически, Next должна быть переменной (var). Узел также содержит определённое значение, которое хранится в поле Data. Поскольку это узел общего типа, для Data задан тип any, а сам узел может содержать данные любого типа. Это может быть общий тип, контейнер или даже другой связный список!

Node1 := list_node{ Next := false, Data := 1 } # An int
Node2 := list_node{ Next := false, Data := "String" } # A string
Node3 := list_node{ Next := false, Data := []int} # An array
Node4 := list_node{ Next := false, Data := list_node } # list_node class
Node5 := list_node{ Next := false, Data := Node1 } # The first node

Благодаря спецификатору <unique> объект list_node является сопоставимым. Это позволяет проверить, совпадает ли узел с каким-либо другим узлом. Например, вы можете узнать, является ли этот узел начальным или конечным в списке.

Если вам нужна более специфическая реализация, например узел, который поддерживает только числа или строки, не забудьте соответствующим образом изменить тип Data. Если для Data будет задан сопоставимый тип, вы сможете сравнивать значение Data с другим значением, чтобы найти определённый узел.

# A container node that contains integer data and a reference
# to the next node in the list.
list_node_int := class(list_node):
    # Reference to the next node in the list.
    var Next<override>:?list_node = false
    Data<override>:int

# A container node that contains string data and a reference
# to the next node in the list.
list_node_string := class(list_node):

Односвязные списки

Наиболее распространённый тип связных списков — это односвязные списки, в которых каждый узел содержит единственную ссылку на следующий узел. Чтобы составить список из узлов, объедините их с помощью ссылок Next в каждом узле.

# Link each Node to the next Node in the list
set Node1.Next = option{Node2}
set Node2.Next = option{Node3}
set Node3.Next = option{Node4}
set Node4.Next = option{Node5}

Несмотря на то что ваши узлы связаны, необходимо определить связный список в качестве класса. Это облегчает выполнение функций по сравнению с тем, чтобы всякий раз использовать ссылку на первый узел.

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

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

# Create a Linked List with node1 as the head.
BasicList:linked_list = linked_list{Head := Node1}

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

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.linked_list := class:
    var Head:list_node

    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node
        Print("Starting at the Head Node...")
        # If the current node has a next node, set the current node to
        # the next node in the list

Здесь функция TraverseList() проверяет, содержит ли CurrentNode ссылку Next, и сохраняет её в NextNode. Если ссылка есть, функция будет последовательно задавать для CurrentNode значение NextNode, пока не достигнет конечного узла. В конечном узле не будет ссылки Next, поэтому на нём цикл завершится.

Двусвязные списки

В отличие от односвязных списков, в двусвязном списке узлы содержат ссылку также и на предыдущий узел.

# A container node that contains data and a reference to both
# the next and previous nodes in the list.
doubly_linked_node := class<unique>:
    var Next:?doubly_linked_node = false
    var Previous:?doubly_linked_node = false
    Data:any = {}

Как и в случае с односвязными узлами, если вам нужна более специфическая реализация, которая будет обрабатывать только определённые типы данных, изменить тип Data на необходимый.

# A container node that contains integer data and a reference to both
# the next and previous nodes in the list.
doubly_linked_int_node := class(doubly_linked_node):
    Data<override>:int

# A container node that contains string data and a reference to both
# the next and previous nodes in the list.
doubly_linked_string_node := class(doubly_linked_node):
    Data<override>:string

Это значит, что вы можете перемещаться по узлам в двусвязном списке вперёд и назад. Это можно делать во внешней функции или в функции класса. Ниже представлен пример функции, которая перемещается по списку от начального узла до конечного.

# A data structure that links multiple list_node structures together to create a chain. 
# Uses doubly linked nodes which contain references to both the next and previous nodes.
doubly_linked_list := class():
    var Head:doubly_linked_node

    # Traverse a LinkedList, but both backward and forward!
    TraverseDoublyLinkedList():void=
        var CurrentNode:?doubly_linked_node := option{Head}
        var NodeNumber:int = 1
        Print("Starting at the Head Node, and going forward...")

Циклические связные списки

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

Итераторы

Итератор — это объект, который позволяет перебирать элементы в контейнере, выполняя при этом некоторые операции. Его можно представить в виде вагона поезда с пассажирами. Поезд движется по рельсам, останавливаясь на каждой станции. На станции он выполняет некоторую задачу, к примеру посадку или высадку пассажиров. Применительно к связным спискам каждая станция — это узел в списке. Поезд (итератор) перемещается по списку к каждому узлу и может выполнять операции в месте остановки.

Итераторы удобны для связных списков, поскольку позволяют выполнять операции в определённых местах, а не только в начальном или конечном узле.

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node
    Next()<transacts><decides>:list_node=
        set CurrentNode = CurrentNode.Next?

В этом примере итератор содержит ссылку на список, по которому он проходит, а также узел CurrentNode, на котором он остановился. Функция Next() проверяет, есть ли после узла CurrentNode ещё один узел, и переходит на этот узел. Обратите внимание, что Next() здесь включает спецификаторы <transacts> и <decides>. Функция должна иметь спецификатор <transacts>, поскольку она обновляет var узла CurrentNode, при этом также необходимо указать спецификатор <decides>, поскольку, сделав Next() выражением с неоднозначным результатом, мы узнаем, произошёл ли переход к следующему узлу или нет.

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

Чтобы при инициализации итератор оказался перед начальным узлом, можно инициализировать CurrentNode фиктивным узлом, для которого следующим узлом будет начальный узел списка. В Verse нельзя получить доступ к List при инициализации CurrentNode, потому что доступ к переменной членов класса невозможен из той же области видимости; она доступа только из другой области видимости, например внутри функции.

linked_list_iterator := class:
    List:linked_list
    # The below line will fail because you can't access List from this scope
    var CurrentNode:list_node := list_node{Next := option{List.Head}}

Вместо этого для создания экземпляра итератора используйте функцию конструктора. Конструктор — это составной тип, который создаёт экземпляр связанного с ним класса. Конструктор инициализирует начальные значения объекта, позволяет получить доступ к значению в списке и присвоить переменной CurrentNode начальный узел списка.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeIterator<constructor>(List:linked_list) := linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= list_node{Next := option{List.Head}}

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

Процесс инициализации итератора для двусвязного списка почти такой же, только при его инициализации нужно использовать узлы с двумя связями.

# Construct an Iterator with CurrentNode as a dummy node before the head of the given list.
MakeDoublyLinkedIterator<constructor>(List:doubly_linked_list) := doubly_linked_list_iterator:
    List := List
    # You can access List from this scope in a constructor function
    CurrentNode:= doubly_linked_node{Next := option{List.Head}}

# Iterates over a doubly_linked_list and can add nodes or remove nodes as it iterates.
doubly_linked_list_iterator := class:
    List:doubly_linked_list
    var CurrentNode:doubly_linked_node

Перемещение между узлами путём итерации

Вы можете перемещать итератор вперёд или назад в соответствии со связями в списке. Итераторы в односвязном списке можно перемещать только вперёд, а в двусвязном — и вперёд, и назад. Данная возможность реализована в двух функциях: Next() и Previous(). Важно помнить, что в односвязных списках нет функции Previous(). Циклические связные списки могут иметь любую из этих функций в зависимости от того, являются ли они односвязными или двусвязными.

# If there is a NextNode for the iterator to travel to, travel to that node
Next()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Next?

# If there is a PreviousNode for the iterator to travel to, travel to that node
Previous()<transacts><decides>:doubly_linked_node=
    set CurrentNode = CurrentNode.Previous?

Добавление узлов

Итераторы можно использовать для добавления узлов в определённые позиции связного списка. При добавлении важно выбрать, куда добавляется узел. Вы можете добавить узел до или после текущего узла, но возможность такого добавления зависит от структуры списка. Из-за отсутствия ссылки на узел Previous в односвязном списке узлы можно добавлять только после других узлов. В двусвязном списке узлы можно добавлять и до, и после других узлов.

# Adds a new node after CurrentNode.
AddNextNode(NewNode:list_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}
        Print("Successfully added a new node to the tail of the list!")

В этом примере функция AddNode добавляет узел между CurrentNode и следующим за ним узлом. Это делается следующим образом:

• В качестве ссылки Next узла CurrentNode задаётся узел NewNode.

• В качестве ссылки Next узла NewNode задаётся узел NextNode. Если узла NextNode нет (то есть текущий узел является конечным), функция ограничивается установкой NewNode в качестве следующего узла.

В двусвязном списке узлы можно добавлять до или после CurrentNode. Эти возможности можно присвоить двух функциям: AddNodeBefore() и AddNodeAfter() соответственно. Реализация очень похожа на ту, что рассмотрена в примере для односвязного списка, с тем лишь отличием, что нужно также задать ссылку Previous для каждого узла.

# Adds a new node after CurrentNode.
AddNodeAfter(NewNode:doubly_linked_node):void=
    if(NextNode := CurrentNode.Next?):
        set NewNode.Next = option{NextNode}
        set NewNode.Previous = option{CurrentNode}
        set CurrentNode.Next = option{NewNode}
        set NextNode.Previous = option{NewNode}
        Print("Successfully added a new node!")
    else:
        set CurrentNode.Next = option{NewNode}

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

Чтобы удалить узлы, нужно удалить все ссылки на эти узлы, сохранив при этом порядок узлов в списке. Поэтому если узел, который вы хотите удалить, имеет какие-либо узлы после него, вам нужно связать все узлы перед удалённым узлом с узлами после него. В односвязном списке можно удалить только узлы после CurrentNode, поскольку у вас нет ссылки на узел Previous.

# Remove the next node after CurrentNode. If the next node
# has a Next reference, set that node to the next node of CurrentNode.
RemoveNextNode():void=
    if(RemovedNode := CurrentNode.Next?):
        if(NodeAfter := RemovedNode.Next?, set RemovedNode.Next = false):
            set CurrentNode.Next = option{NodeAfter}
            Print("Removed the node between CurrentNode and the node after it")
            # If the removed node is the Head node, set the next node as the new Head.
            if(RemovedNode = List.Head):
                Print("Removed node was the head node, setting the node after as the new head")

Удаление начального узла требует особой процедуры. В этом случае нужно сделать узел, следующий за начальным, начальным узлом в списке. В противном случае в списке не будет начального узла.

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

# Remove the node after CurrentNode
RemoveNodeAfter():void=
    if(RemovedNode := CurrentNode.Next?):
        if:
            NodeAfter := RemovedNode.Next?
            set RemovedNode.Next = false
            set RemovedNode.Previous = false
            set NodeAfter.Previous = option{CurrentNode}
            set CurrentNode.Next = option{NodeAfter}
        then:

Полный код

Ниже приведён полный код для каждого из классов в этом примере.

list_node

# A container node that contains data and a reference
# to the next node in the list.
list_node := class<unique>:
    # Reference to the next node in the list.
    var Next:?list_node = false
    Data:any = {}


# A container node that contains integer data and a reference
# to the next node in the list.

linked_list

# A data structure that links multiple list_node structures together to create a chain. 
# Uses singly linked nodes which contain a reference to the next node in the chain.
linked_list := class:
    # The first node in the list.
    var Head:list_node
 
    # Traverses the linked list forward starting from the CurrentNode.
    TraverseList():void=
        var CurrentNode:?list_node := option{Head} # The node you're currently on
        var NodeNumber:int = 1 # The number of the current node.

linked_list_iterator

# Iterates over a linked_list and can add nodes or remove nodes as it iterates.
linked_list_iterator := class:
    List:linked_list
    var CurrentNode:list_node

    # If there is a NextNode for the iterator to travel to, travel to that node.
    Next()<transacts><decides>:list_node=
        NextNode := CurrentNode.Next?
        set CurrentNode = NextNode

Самостоятельная работа

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

• Что если бы в каждом списке также хранилась ссылка на конечный узел?

• Сможете ли вы реализовать метод ToString() для вывода содержимого узлов?

• Как насчёт изменения порядка элементов в списке на обратный? Сможете ли вы реализовать функцию Length()?

• Сможете ли вы добавить в итератор методы для выполнения новых операций?