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