Односвязный список

Односвязный список - это структура данных, состоящая из узлов (или, как их еще называют — нод). Каждая нода состоит из 2х полей:

• Значение
• Указатель

Значение - это некоторые данные, которые мы обычно храним в различных типах, как: int, float, bool и тд. Указатель - это ссылка на следующий элемент списка (иначе как по нему итерироваться?). А последний узел указывает на nil.

У списка есть голова (head) и хвост (tail). Голова указывает на 1-ый элемент в списке, а хвост — на самый последний. Итерироваться по списку можно в одном направлении — от головы к хвосту¹.

Пример с визуализацией:

[1] → [2] → [3] → nil
  ⤷ head      ⤷ tail

Как хранятся в памяти?

В памяти узлы односвязного списка могут лежать как вместе, так и в разных ее частях — это нам совсем не важно, т.к. каждый узел списка ссылается на следующий за ним, и мы без проблем найдем необходимый узел. Размер односвязного списка неограничен (как и у слайсов), поэтому при создании односвязного списка мы не указываем ее размер.

Реализация

Рассмотрим простой пример реализации односвязного списка (без поля Tail). Нам понадобятся 2 структуры:

type Node struct {
  // значение
  Value int
  // указатель на следующий Node
  Next  *Node
}

type SinglyLinkedList struct {
  // указатель на начало списка
  Head  *Node
  // кол-во узлов в списке
  count int
}

// пример без конструкторов

И напишем функцию, которая будет работать за О(n) и возвращать искомое² значение:

func (l *SinglyLinkedList) FindByIndex(index int) *Node {
  if l == nil || l.count == 0 || index < 0 {
    return nil
  }

  curr := l.Head

  // итерируемся по списку, пока не найдём нужный узел
  for i := 0; i < l.count; i++ {
    // если индекс совпал, то возвращаю его
    if i == index {
      return curr
    }

   // двигаемся по списку, пока условие выше НЕ истинно
    curr = curr.Next
  }

  return nil
}

В этом примере для итерации я использовал следующий цикл:

for i := 0; i < l.count; i++ {}

Вы также можете использовать и другой способ (так обычно и принято писать):

for curr.Next != nil {}

Т.к. мы 100% будем знать, что хвост нашего списка указывает на nil, то итерируемся, пока ссылка у узла не будет указывать на nil.

¹ есть циклические односвязные списки, где tail указывает на 1-ый элемент списка, поэтому, по такому списку можно итерироваться сколько угодно (бесконечный цикл).

² значение, которое необходимо найти, называют искомым.