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