2024 подписчика
🦫Реализация односвязного списка в Golang
Связные списки — это фундаментальные структуры данных информатики и программирования, часто применяемые для хранения и управления набором данных, элементы которого не хранятся в смежных участках памяти. Рассмотрим реализацию односвязного списка на Go.
Введение в односвязные списки
Связный список — это структура данных с последовательностью узлов, в каждом из которых содержатся данные и ссылка на следующий узел последовательности. Различают односвязные, двусвязные и кольцевые связные списки.
У односвязного списка:
⬅️ В каждом узле содержатся данные.
⬅️ В каждом узле имеется ссылка — указатель next — на следующий узел последовательности.
⬅️ В последнем узле обычно имеется ссылка nil, которой указывается на конец списка.
Узел — основа связного списка
В сердце связного списка находится понятие узла.
УЗЕЛ — ЭТО СТРОИТЕЛЬНЫЙ БЛОК ИЛИ КОНТЕЙНЕР, В КОТОРОМ СОДЕРЖАТСЯ: 1) СОХРАНЯЕМЫЕ ДАННЫЕ — ЧТО БЫ ВЫ НИ ВЫБРАЛИ — И 2) УКАЗАТЕЛЬ НА ТО, ЧТО СЛЕДУЕТ ДАЛЬШЕ.
Этой простой структурой формируется основа для создания односвязных — с последовательно связанными узлами — списков и двусвязных, где у узлов имеются ссылки на следующий и предыдущий узлы:
type Node struct {
data int
next *Node
}
type LinkedList struct {
head *Node
}
Структура Node здесь фундаментальный строительный блок односвязного списка. В ней инкапсулируются основные компоненты каждого узла списка:
▪️Поле data — это хранимые в узле данные или значение. Мы задали ему целочисленный int, хотя на практике это может быть любой тип данных, необходимый конкретному приложению.
▪️Поле next — это ссылка или указатель на следующий узел связанного списка. Ею узлы связываются в последовательную цепочку. Когда узел в списке последний, полем next указывается на nil — конец списка.
Фактически структурой Node определяется, как выглядит отдельный элемент связного списка — с данными, которые в нем содержатся, и ссылкой на следующий элемент.
Структура LinkedList — это связный список в целом, ею управляется набор узлов:
▪️Поле head — ссылка или указатель на первый узел связного списка. Это точка входа в список, через которую получается доступ ко всей последовательности узлов для манипулирования ими.
Вместе структуры Node и LinkedList — основа односвязного списка на Go. Структурой Node определяется то, как структурируются отдельные элементы, структурой LinkedList — как эти элементы организуются в целостную структуру данных.
Хотя связный список создается и без типа LinkedList, предпочитаю как первичную структуру данных именно его LinkedList — такой контейнер для связного списка, где инкапсулируется весь список, и кроме того, способ контролировать поведение списка.
Вставка данных в связный список
2 минуты
19 декабря 2023