Связные списки — это фундаментальные структуры данных информатики и программирования, часто применяемые для хранения и управления набором данных, элементы которого не хранятся в смежных участках памяти. Рассмотрим реализацию односвязного списка на 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
или другом определенном пакете.
Способы ее реализации с различными операциями ограничены лишь воображением программиста.
В совокупности эти операции — мощные инструменты эффективного управления и манипулирования данными связного списка для эффективной их вставки, удаления, извлечения и визуализации.
Читайте также:
- 10 проектов для изучения Golang в 2023 году
- Малоизвестный пакет Go, который пригодится при выполнении SQL-миграций
- Что возвращать в Go: структуры или интерфейсы?
Читайте нас в Telegram, VK и Дзен
Перевод статьи Jaydevsinh Chauhan: Implementing Single Linked List in Golang