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

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

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

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

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 или другом определенном пакете.

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

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

Источник