Какие встроенные и стандартные структуры данных есть в Go? Как реализовать классические структуры данных, отсутствующие в стандартной библиотеке?

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

Встроенные и стандартные структуры данных

1. Массивы (Arrays)

   • Последовательность элементов одного типа с фиксированной длиной. Размер массива является частью его типа. Являются value-типами (при присваивании или передаче в функцию происходит полное копирование).

     var arr [3]int = [3]int{1, 2, 3}

2. Срезы (Slices)

   • Динамический, гибкий и более удобный аналог массива. Срез — это легковесная структура-дескриптор, которая ссылается на непрерывный сегмент базового массива (backing array). Содержит указатель на начало сегмента, его длину (len) и ёмкость (cap). Является reference-типом.

     slice := []int{1, 2, 3}
     slice = append(slice, 4) // Длина и ёмкость могут меняться

3. Карты (Maps)

   • Хеш-таблица, хранящая пары "ключ-значение". Является reference-типом. Порядок итерации по элементам карты не гарантирован.

     m := make(map[string]int)
     m["age"] = 30

4. Строки (Strings)

   • Неизменяемая (immutable) последовательность байт. Внутренне похожа на срез байт []byte, но её содержимое нельзя изменить после создания.

5. Структуры (Structs)

   • Композитный тип данных, который объединяет поля разных типов в единое целое.

     type Person struct {
     Name string
     Age  int
     }

6. Пакет container

   • container/list: Реализация двусвязного списка.
   • container/heap: Интерфейс для реализации кучи (пирамиды). Может использоваться для создания min-heap или max-heap поверх среза.

Реализация классических структур данных

Поскольку стандартная библиотека Go минималистична, некоторые структуры данных реализуются вручную.

1. Стек (Stack) и Очередь (Queue)

   • Легко реализуются на основе среза. Стек использует LIFO (Last-In, First-Out), а очередь — FIFO (First-In, First-Out).

     // Стек
     stack := []int{}
     stack = append(stack, 10) // Push
     val := stack[len(stack)-1] // Peek
     stack = stack[:len(stack)-1] // Pop

2. Множество (Set)

   • Идиоматичный способ реализации множества в Go — это использование map с пустыми структурами в качестве значений, так как struct{} не занимает памяти.

     
     set := make(map[string]struct{})
     set["apple"] = struct{}{}
     set["orange"] = struct{}{}

   if _, exists := set["apple"]; exists { // Элемент существует }

3. Деревья (Trees) и Графы (Graphs)

   • Реализуются с помощью структур и указателей. Например, бинарное дерево:

     type TreeNode struct {
     Value int
     Left  *TreeNode
     Right *TreeNode
     }

   • Графы часто представляют списком смежности (map[T][]T) или матрицей смежности ([][]bool).