2022 подписчика

🦫Реализация односвязного списка в 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 — такой контейнер для связного списка, где инкапсулируется весь список, и кроме того, способ контролировать поведение списка.

Вставка данных в связный список

📌Читать

@golang

2 минуты

19 декабря 2023