Связный список >
Связный список представляет цепь
элементов узлов, каждый из которых, кроме последнего, связан, то
есть имеет ссылку на один следующий элемент (однонаправленный
список) и для двунаправленного списка каждый элемент, кроме
первого, связан с одним предыдущим элементом.
Не все промышленные языки имеют встроенную поддержку связного списка как структуры данных. Впрочем, его нетрудно реализовать самостоятельно как класс или структуру. Для комфортной работы с релевантными алгоритмами мы добавим встроенные двунаправленные связные списки уже в базовое определение языка Hi.
Для начала создадим экземпляр нашего экспериментального списка:
VAR list = <"I", "will", "be">
В примере выше для трех узлов автоматически создаются двунаправленные ссылки.
Связанный непустой список в языке Hi всегда имеет один узел, который является текущим или активным. По умолчанию это последний добавленный элемент, то есть сейчас это be. Проверим это:
PRINT list.current # печатает "be"
Добавим в наш список еще два элемента:
list.insert "back", "!" # теперь list включает элементы: "I", "will", "be", "back", "!"
Встроенный метод insert добавляет новые элементы сразу после активного узла, автоматически выстраивает новые связи и делает текущим последний добавленный элемент.
Удаление осуществляется похожим образом для текущего элемента:
list.remove 1 # list включает элементы: "I", "will", "be", "back"
Впрочем, можно сразу удалить и несколько элементов, для этого нужно предварительно установить указатель на первый удаляемый узел:
VAR secList = listsecList.prev 2secList.remove 2 # secList сейчас включает элементы: "I", "back"
При этом узел, предыдущий перед удаляемым, становится текущим. Если удаляется первый элемент списка, то текущим становится новый первый элемент.
Можно заменить текущий узел на другой, просто присвоив элементу новое значение:
secList.сurrent = "smile" # secList включает элементы: "smile ", "back"
Удалить все узлы, то есть сделать список пустым можно так:
secList = <>
Переходить на первый и последний узел удобно следующим образом:
list.firstLET last = list.last # одновременно мы присваиваем новой константе значение активного элемента
Таким образом можно достаточно легко осуществлять разнообразные операции со списком:
PRINT list # печатает "I", "will", "be", "back"list.firstlist.nextlist.insert "not"LET be = list
