13,9 тыс подписчиков

Реализация односвязного списка в Golang

19 декабря 202319 дек 2023

324

14 мин

Оглавление

Введение в односвязные списки
Узел — основа связного списка
Вставка данных в связный список

Связные списки — это фундаментальные структуры данных информатики и программирования, часто применяемые для хранения и управления набором данных, элементы которого не хранятся в смежных участках памяти. Рассмотрим реализацию односвязного списка на 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 — такой контейнер для связного списка, где инкапсулируется весь список, и кроме того, способ контролировать поведение списка.

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

Обычно я вставляю данные в связный список четырьмя способами.

После последнего узла

func (list *LinkedList) insertAtBack(data int) {
newNode := &Node{data: data, next: nil}

if list.head == nil {
list.head = newNode
return
}

current := list.head
for current.next != nil {
current = current.next
}

current.next = newNode
}

В конец связного списка новый узел с заданным data вставляется методом insertAtBack(data int).

Начинается метод созданием нового узла newNode с указываемыми данными.
Если связный список пуст, то есть значение list.head — nil, голова head списка устанавливается в новый узел, который фактически становится первым узлом списка.
Если список не пуст, выполняется его итеративный обход в поисках последнего узла: следуем от head за указателями next, пока не дойдем до узла, где next равен nil — конец списка.
После нахождения последнего узла — на него указывается current — его next устанавливается в newNode, а сам он фактически добавляется в конец списка.

Так этим методом вновь вставленный узел гарантированно становится последним элементом связного списка.

Перед первым узлом

func (list *LinkedList) insertAtFront(data int) {
if list.head == nil {
newNode := &Node{data: data, next: nil}
list.head = newNode
return
}

newNode := &Node{data: data, next: list.head}
list.head = newNode
}

В начало связного списка новый узел с заданным data вставляется методом insertAtFront(data int).

Если связный список пуст, то есть значение list.head — nil, создается новый узел newNode с указываемыми данными, который устанавливается в качестве головы head и фактически становится первым узлом списка.
Если список не пуст, создается новый узел newNode с указываемыми данными и его указатель next устанавливается на текущей head. Затем голова head списка обновляется: ею указывается на вновь созданный узел, который становится новым первым узлом списка.

Так этим методом новый элемент фактически вставляется в начало связного списка.

После значения узла

func (list *LinkedList) insertAfterValue(afterValue, data int) {
newNode := &Node{data: data, next: nil}

current := list.head

for current != nil {
if current.data == afterValue {
newNode.next = current.next
current.next = newNode
return
}
current = current.next
}

fmt.Printf("Cannot insert node, after value %d doesn't exist", afterValue)
fmt.Println()
}

Новый узел с заданным data вставляется методом insertAfterValue(afterValue, data int) сразу после первого появления в связном списке конкретного afterValue.

Начинается метод созданием нового узла newNode с указываемыми данными.
Затем от головы head начинается проход списка в поисках узла, чьи данные data соответствуют afterValue.
Когда такой узел находится и current.data == afterValue, то newNode подключается к следующему за текущим current узлу, обновляя указатели next. Так newNode фактически вставляется после узла с указываемым afterValue.
Если узел с afterValue не найден, выводится сообщение об ошибке с указанием, что значение в списке не найдено.

Так этим методом новый элемент вставляется сразу после конкретного, имеющегося в связном списке элемента.

Перед значением узла

func (list *LinkedList) insertBeforeValue(beforeValue, data int) {
if list.head == nil {
return
}

if list.head.data == beforeValue {
newNode := &Node{data: data, next: list.head}
list.head = newNode
return
}

current := list.head
for current.next != nil {
if current.next.data == beforeValue {
newNode := &Node{data: data, next: current.next}
current.next = newNode
return
}
current = current.next
}
fmt.Printf("Cannot insert node, before value %d doesn't exist", beforeValue)
fmt.Println()
}

Новый узел с заданным data вставляется методом insertBeforeValue(beforeValue, data int) непосредственно перед первым появлением в связном списке конкретного beforeValue.

Начинаем с проверки, не пуст ли связный список. Если пуст, функция возвращается раньше, так как узла для вставки перед ним нет.
Если beforeValue совпадает с данными data текущего головного head узла, создается новый узел newNode с указываемыми данными и его указатель next устанавливается на текущей head. Затем голова head списка обновляется: ею указывается на вновь созданный узел newNode, который фактически вставляется перед головой head.
Если beforeValue в головном узле head не найден, выполняется итеративный обход списка в поисках узла, данные следующего узла next которого идентичны beforeValue. Когда такой узел находится и current.next.data == beforeValue, то newNode вставляется между current и current.next, соответственно обновляя указатели next.
Если узел с beforeValue не найден, выводится сообщение об ошибке с указанием, что значение в списке не найдено.

Так этим методом новый элемент вставляется непосредственно перед конкретным, имеющимся в связном списке элементом.

Кроме этих четырех, имеются и другие способы вставки данных: в конкретное место, пакетная или даже сортированная вставка.

Удаление данных в связном списке

Вот мои предпочтительные способы удаления данных в связном списке:

Удаление первого узла

func (list *LinkedList) deleteFront() {
if list.head != nil {
list.head = list.head.next
fmt.Printf("Head node of linked list has been deleted\n")
return
}
}

Первый, головной узел связного списка удаляется методом deleteFront().

Проверяем, не пуст ли связный список, то есть list.head != nil.
Если список не пуст, указатель head обновляется: им указывается на следующий узел, а первый фактически удаляется.

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

Удаление последнего узла

func (list *LinkedList) deleteLast() {
if list.head == nil {
fmt.Printf("Linked list is empty\n")
}

if list.head.next == nil {
list.head = nil
fmt.Printf("Last node of linked list has been deleted\n")
return
}

var current *Node = list.head
for current.next.next != nil {
current = current.next
}
current.next = nil

fmt.Printf("Last node of linked list has been deleted")
}

Последний узел связного списка удаляется методом deleteLast().

Сначала проверяем, не пуст ли связный список, то есть list.head == nil; этот случай обрабатывается выводом сообщения с указанием, что список пуст.
Если список не пуст, проверяем, не один ли в нем узел, то есть list.head.next == nil; этот случай обрабатывается установкой head в nil.
Если в списке более одного узла, проходимся по нему, пока не доберемся до предпоследнего узла.
Затем указатель next предпоследнего узла обновляется и становится nil, то есть current.next = nil, а последний узел фактически удаляется.

Так этим методом из связного списка удаляется последний узел — с учетом различных сценариев.

Удаление после значения узла

func (list *LinkedList) deleteAfterValue(afterValue int) {
var current *Node = list.head

for current != nil && current.data != afterValue {
current = current.next
}

if current == nil {
fmt.Printf("Node with after value %d doesn't exist\n", afterValue)
return
}

if current.next == nil {
fmt.Printf("Node with after value %d is the last node\n", afterValue)
return
}

var temp *Node = current.next
fmt.Printf("Node after value %d has data %d and will be deleted", afterValue, temp.data)

current.next = current.next.next
}

Узел, следующий за узлом с конкретным значением afterValue, удаляется методом deleteAfterValue(afterValue int).

Начинается метод проходом связного списка от головного узла.
При этом сравниваются данные текущего узла с указываемым afterValue.
Если совпадение не найдено, то есть current == nil, выводится сообщение с указанием об отсутствии узла с afterValue.
Если совпадающий узел — последний, то есть current.next == nil, выводится сообщение с указанием, что этот узел — последний.
Если совпадающий узел найден и он не последний, выводится информация о подлежащем удалению узле, затем обновляется указатель next текущего узла: удаляемый узел им пропускается, то есть current.next = current.next.next.

Так этим методом удаляется узел, следующий за узлом с конкретным значением, учитывая различные сценарии.

Удаление перед значением узла

func (list *LinkedList) deleteBeforeValue(beforeValue int) {
var previous *Node
current := list.head

if current == nil || current.next == nil {
fmt.Printf("Node with before value %d doesn't exist\n", beforeValue)
return
}

for current.next != nil {
if current.next.data == beforeValue {
if previous == nil {
fmt.Printf("Node before value %d has data %d and will be deleted\n", beforeValue, current.data)
list.head = current.next
} else {
fmt.Printf("Node before value %d has data %d and will be deleted\n", beforeValue, current.data)
previous.next = current.next
}
return
}
previous = current
current = current.next
}
fmt.Printf("Node before value %d not found\n", beforeValue)
}

Узел, предшествующий узлу с конкретным значением beforeValue, удаляется методом deleteBeforeValue(beforeValue int).

При проходе связного списка текущий и предыдущий узлы отслеживаются двумя указателями: current и previous. Так проще манипулировать указателями для удаления.
В самом начале проверяется, не пуст ли список или не один ли в нем узел.
Если пуст или один, выводится соответственное сообщение с возвращением и лишний проход не выполняется.
Затем список проходится при проверке данных следующего узла.
Если предыдущий узел previous — nil, первый узел удаляется, поэтому голова head обновляется.
В противном случае обновляется указатель next предыдущего узла previous: удаляемый узел пропускается.
Если цикл завершается без нахождения целевого значения, выводится сообщение с указанием, что узел с целевым значением не найден.

Так этим методом удаляется узел, предшествующий узлу с конкретным значением, учитывая различные сценарии.

Удаление узла связного списка, как и вставка, не ограничивается этими четырьмя способами — попробуйте и другие.

Прочие операции над связным списком

Вот другие операции, выполняемые со связным списком:

Подсчет общего числа узлов

func (list *LinkedList) countNodes() (count int) {
current := list.head
for current != nil {
current = current.next
count++
}
return
}

Количество узлов в связном списке подсчитывается методом countNodes().

Нулем инициализируется переменная count, в которой сохранится число узлов, и с головного узла head начинается проход списка.
На каждой итерации цикла переход к следующему узлу выполняется через поле next текущего, и счетчик count увеличивается на 1.
Процесс продолжается функцией до конца списка, где current становится nil.
Наконец, возвращается значение count — общее количество узлов в списке.

Нахождение узла по заданному индексу

func (list *LinkedList) findNodeAt(index int) *Node {
var count int = 0
var current *Node = list.head

for current != nil {
count++
current = current.next
}

if index <= 0 || index > count {
return nil
}

current = list.head
for count = 1; count < index; count++ {
current = current.next
}
return current
}

Поиск и возвращение узла по заданному индексу выполняются в связном списке методом findNodeAt(index int) *Node.

Переменная count инициализируется единицей, указатель current устанавливается в голову head списка. Затем список проходится, и подсчитывается общее число узлов, count на каждой итерации обновляется.
Если задан недопустимый индекс index: не больше нуля или больше общего числа узлов count — после подсчета всех узлов возвращается nil.
Если index допустимый, указатель current переустанавливается в голову head списка, который снова проходится, и по заданному индексу index находится узел.
Указатель возвращается в найденный узел.

Вывод связного списка

func (list *LinkedList) print() {
var current *Node = list.head
for current != nil {
fmt.Printf("%d -> ", current.data)
current = current.next
}
fmt.Println()
}

Значения данных всех узлов в связном списке выводятся на консоль методом print().

Указатель current устанавливается в голову head списка.
Затем входим в цикл, который продолжается до конца списка, где current становится nil.
На каждой итерации выводится значение данных текущего узла current.data, сопровождаемое стрелочкой -> и символом новой строки.

Всеми этими методами обеспечиваются основные операции, выполняемые со связным списком: подсчет узлов, поиск узла по заданному индексу, вывод содержимого списка. Они пригодятся и при решении задач посложнее.

Настройка функции «main»

Проверим операции в простой функции main, включать в этот блок кода разные импорты или даже объявление main package я посчитал излишним:

func main() {
// Создаем пустой связный список
myList := LinkedList{}

// Сначала вставляем данные
myList.insertFront(10)
myList.insertFront(20)
myList.insertFront(30)

// Выводим содержимое связного списка
fmt.Println("Linked List Contents:")
myList.print()

// Подсчитываем узлы в связном списке
count := myList.countNodes()
fmt.Printf("Total number of nodes: %d\n", count)

// Находим и выводим узел по заданному индексу
indexToFind := 2
foundNode := myList.findNodeAt(indexToFind)
if foundNode != nil {
fmt.Printf("Node at index %d has data: %d\n", indexToFind, foundNode.data)
} else {
fmt.Printf("Node at index %d not found\n", indexToFind)
}

// При необходимости выполняем другие операции...

// Удаляем последний узел
myList.deleteLast()

// Выводим обновленный связный список
fmt.Println("Linked List After Deletion:")
myList.print()
}

Теперь структура данных связного списка создается полностью в новом пакете, который затем импортируется, или просто создается интерфейс и реализуется с типом LinkedList, опять же в main или другом определенном пакете.

Способы ее реализации с различными операциями ограничены лишь воображением программиста.

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