Тренды

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

19.12.2023

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

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

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

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

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

Узел — основа связного списка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также

7 инструментов для разработки веб-компонентов в 2019 году

SQL: загадки на сообразительность

10 рекомендаций, которые повысят производительность разработки на Flutter в 2023 году

Тесты

Насколько хорошо вы знаете JavaScript

Хорошо ли вы разбираетесь в структурах данных и алгоритмах?

Насколько хорошо вы разбираетесь в сетях?