Структура данных — это способ организовать и хранить данные в компьютере так, чтобы их можно было эффективно использовать. Выбор правильной структуры часто важнее выбора алгоритма: даже идеальный алгоритм будет работать медленно на неподходящей структуре. В Go есть встроенные структуры (массивы, слайсы, map), но для многих задач приходится строить свои (связные списки, деревья, графы). Мы пройдём путь от простого к сложному, снабжая каждый раздел работающими примерами на Go.
1. Массивы и слайсы (Slice) — основа линейного хранения
Суть
Массив
— это фиксированная последовательность элементов одного типа,
расположенных в памяти непрерывно. Размер массива является частью его
типа, поэтому [5]int и [10]int — разные типы. Массивы в Go передаются по значению (копируются), что редко удобно. Поэтому на практике используют слайсы — динамические представления участков массива.
Слайс — это структура из трёх полей: указатель на первый элемент, длина (len) и ёмкость (cap). При добавлении элементов через append,
если ёмкость превышена, Go автоматически выделяет новый массив в два
раза больше (на небольших размерах) и копирует данные. Это делает слайсы
гибкими, но нужно помнить о возможном перевыделении.
Примеры на Go
go
package main
import "fmt"
func main() {
// Массив фиксированного размера
var arr [3]int = [3]int{1, 2, 3}
fmt.Println("Массив:", arr)
// Слайс — создание литералом
slice := []int{10, 20, 30, 40}
fmt.Println("Слайс:", slice, "len:", len(slice), "cap:", cap(slice))
// Создание через make
s2 := make([]int, 5, 10) // длина 5, ёмкость 10
s2[0] = 100
s2 = append(s2, 200) // добавляем в конец
fmt.Println("make-слайс:", s2, "len:", len(s2), "cap:", cap(s2))
// Срез из массива
sub := slice[1:3] // элементы с индексами 1 и 2
fmt.Println("Срез:", sub)
}
Когда использовать:
- Массивы — почти никогда, разве что для фиксированных константных наборов.
- Слайсы — везде, где нужна последовательность элементов с возможностью изменения размера.
Сложность операций:
- Доступ по индексу: O(1)
- Добавление в конец (амортизированное): O(1)
- Вставка в середину: O(n) из-за сдвига
- Удаление из середины: O(n)
2. Связный список (Linked List)
Суть
Связный
список — это структура, в которой элементы (узлы) не обязаны находиться
в памяти последовательно. Каждый узел содержит значение и ссылку
(указатель) на следующий узел (в двусвязном списке — ещё и на
предыдущий). Связные списки позволяют вставлять и удалять элементы в
середине за O(1), если у вас уже есть ссылка на узел. Однако доступ по
индексу требует прохода от головы списка (O(n)).
В Go стандартная библиотека не предоставляет готового связного списка (кроме container/list, который даёт двусвязный список, но часто разработчики пишут свой для лучшего понимания).
Реализация односвязного списка
go
package main
import "fmt"
// Узел списка
type Node struct {
value int
next *Node
}
// Односвязный список
type LinkedList struct {
head *Node
}
// Добавление в начало
func (l *LinkedList) Prepend(value int) {
newNode := &Node{value: value, next: l.head}
l.head = newNode
}
// Добавление в конец
func (l *LinkedList) Append(value int) {
newNode := &Node{value: value}
if l.head == nil {
l.head = newNode
return
}
current := l.head
for current.next != nil {
current = current.next
}
current.next = newNode
}
// Удаление по значению (первое вхождение)
func (l *LinkedList) Remove(value int) {
if l.head == nil {
return
}
if l.head.value == value {
l.head = l.head.next
return
}
current := l.head
for current.next != nil && current.next.value != value {
current = current.next
}
if current.next != nil {
current.next = current.next.next
}
}
// Поиск элемента
func (l *LinkedList) Find(value int) bool {
current := l.head
for current != nil {
if current.value == value {
return true
}
current = current.next
}
return false
}
// Печать списка
func (l *LinkedList) Print() {
current := l.head
for current != nil {
fmt.Printf("%d -> ", current.value)
current = current.next
}
fmt.Println("nil")
}
func main() {
list := &LinkedList{}
list.Append(10)
list.Append(20)
list.Prepend(5)
list.Print() // 5 -> 10 -> 20 -> nil
list.Remove(10)
list.Print() // 5 -> 20 -> nil
fmt.Println("Find 20:", list.Find(20))
}
Когда использовать:
- Частые вставки/удаления в середине последовательности.
- Нужна структура с динамическим размером без перемещения элементов.
- Реализация очереди или стека (хотя слайсы часто удобнее).
Недостатки:
- Медленный доступ по индексу.
- Дополнительная память на указатели (особенно в 64-битных системах — 8 байт на ссылку).
- Плохая локальность кэша (элементы разбросаны по памяти).
3. Стек (Stack) — LIFO
Суть
Стек — структура, работающая по принципу «последним пришёл — первым вышел» (Last In, First Out). Основные операции: push (добавить сверху), pop (извлечь сверху), peek
(посмотреть верхний элемент без удаления). Стек можно реализовать на
основе массива/слайса или связного списка. В Go удобно использовать
слайс.
Реализация на слайсе
go
package main
import "fmt"
type Stack struct {
items []int
}
// Push добавляет элемент
func (s *Stack) Push(item int) {
s.items = append(s.items, item)
}
// Pop удаляет и возвращает верхний элемент
func (s *Stack) Pop() (int, error) {
if len(s.items) == 0 {
return 0, fmt.Errorf("стек пуст")
}
lastIndex := len(s.items) - 1
item := s.items[lastIndex]
s.items = s.items[:lastIndex]
return item, nil
}
// Peek возвращает верхний элемент без удаления
func (s *Stack) Peek() (int, error) {
if len(s.items) == 0 {
return 0, fmt.Errorf("стек пуст")
}
return s.items[len(s.items)-1], nil
}
func (s *Stack) IsEmpty() bool {
return len(s.items) == 0
}
func main() {
stack := &Stack{}
stack.Push(1)
stack.Push(2)
stack.Push(3)
fmt.Println(stack.Pop()) // 3 nil
fmt.Println(stack.Peek())// 2 nil
}
Применение:
- Обратный порядок вызовов функций (call stack).
- Парсинг выражений (проверка скобок, обратная польская запись).
- Реализация отмены действий (undo/redo).
Сложность: все операции O(1) (амортизированно для push).
4. Очередь (Queue) — FIFO
Суть
Очередь — структура «первым пришёл — первым вышел» (First In, First Out). Операции: enqueue (добавить в конец), dequeue
(извлечь из начала). На слайсе простая реализация неэффективна, потому
что удаление из начала требует сдвига всех элементов (O(n)). Лучше
использовать кольцевую очередь на слайсе с индексами или связный список.
Реализация на двусвязном списке (или через container/list)
В Go есть container/list — двусвязный список, идеально подходящий для очереди.
go
package main
import (
"container/list"
"fmt"
)
type Queue struct {
items *list.List
}
func NewQueue() *Queue {
return &Queue{items: list.New()}
}
// Enqueue добавляет в конец
func (q *Queue) Enqueue(value int) {
q.items.PushBack(value)
}
// Dequeue удаляет из начала
func (q *Queue) Dequeue() (int, error) {
front := q.items.Front()
if front == nil {
return 0, fmt.Errorf("очередь пуста")
}
q.items.Remove(front)
return front.Value.(int), nil
}
func (q *Queue) IsEmpty() bool {
return q.items.Len() == 0
}
func main() {
q := NewQueue()
q.Enqueue(10)
q.Enqueue(20)
val, _ := q.Dequeue()
fmt.Println(val) // 10
}
Альтернатива — кольцевая очередь на слайсе:
go
type RingQueue struct {
items []int
head int
tail int
size int
cap int
}
func NewRingQueue(capacity int) *RingQueue {
return &RingQueue{
items: make([]int, capacity),
cap: capacity,
}
}
func (q *RingQueue) Enqueue(val int) bool {
if q.size == q.cap {
return false // переполнена
}
q.items[q.tail] = val
q.tail = (q.tail + 1) % q.cap
q.size++
return true
}
func (q *RingQueue) Dequeue() (int, bool) {
if q.size == 0 {
return 0, false
}
val := q.items[q.head]
q.head = (q.head + 1) % q.cap
q.size--
return val, true
}
Применение:
- Планировщики задач.
- Обработка запросов в порядке поступления.
- Ширина обхода графов (BFS).
5. Хеш-таблица (HashMap / Map в Go)
Суть
Хеш-таблица — это структура данных, которая отображает ключи на значения, используя хеш-функцию. В Go встроенный тип map
реализует хеш-таблицу с динамическим расширением и защитой от коллизий
(разрешение цепочками). Ключи могут быть любого сравниваемого типа (== и
!=). Доступ к элементу по ключу в среднем O(1).
Внутреннее устройство
(упрощённо): массив «корзин» (buckets), каждая корзина — связный список
пар ключ-значение. При загрузке выше определённого порога map
увеличивает число корзин и перехеширует все элементы.
Примеры использования
go
package main
import "fmt"
func main() {
// Объявление map
var m map[string]int
m = make(map[string]int) // инициализация обязательна
m["apple"] = 5
m["banana"] = 7
fmt.Println(m["apple"]) // 5
// Проверка существования
value, ok := m["orange"]
if !ok {
fmt.Println("orange not found")
}
// Удаление
delete(m, "banana")
// Итерация
for key, val := range m {
fmt.Printf("%s -> %d\n", key, val)
}
// Map с ключом-структурой
type Point struct { X, Y int }
points := make(map[Point]string)
points[Point{1, 2}] = "home"
}
Важные особенности Go map:
- Небезопасны для конкурентной записи (нужен мьютекс или sync.Map).
- Итерация по map не гарантирует порядок.
- Нельзя взять указатель на элемент map (из-за внутреннего перемещения).
Когда использовать:
- Быстрый поиск по уникальному ключу.
- Подсчёт частоты (счётчик).
- Кэширование.
Сложность: средняя O(1), в худшем (много коллизий) O(n). Но в Go хеш-функция хороша, и коллизии редки.
6. Деревья (Trees)
6.1. Бинарное дерево поиска (BST)
Суть:
Дерево, в котором каждый узел имеет не более двух потомков, причём все
значения в левом поддереве меньше значения узла, а в правом — больше.
Это обеспечивает быстрый поиск, вставку и удаление за O(log n) в
сбалансированном случае, но может выродиться в O(n) (например, если
вставлять отсортированные данные). В Go часто реализуют BST вручную,
либо используют сбалансированные варианты (AVL, красно-чёрные) из
сторонних библиотек.
Реализация BST с операциями
go
package main
import "fmt"
type BSTNode struct {
value int
left *BSTNode
right *BSTNode
}
type BST struct {
root *BSTNode
}
// Вставка
func (bst *BST) Insert(val int) {
newNode := &BSTNode{value: val}
if bst.root == nil {
bst.root = newNode
return
}
current := bst.root
for {
if val < current.value {
if current.left == nil {
current.left = newNode
break
}
current = current.left
} else {
if current.right == nil {
current.right = newNode
break
}
current = current.right
}
}
}
// Поиск
func (bst *BST) Search(val int) bool {
current := bst.root
for current != nil {
if val == current.value {
return true
} else if val < current.value {
current = current.left
} else {
current = current.right
}
}
return false
}
// Обход inorder (отсортированный порядок)
func (bst *BST) Inorder(node *BSTNode) {
if node != nil {
bst.Inorder(node.left)
fmt.Print(node.value, " ")
bst.Inorder(node.right)
}
}
func main() {
tree := &BST{}
tree.Insert(50)
tree.Insert(30)
tree.Insert(80)
tree.Insert(20)
tree.Insert(40)
tree.Inorder(tree.root) // 20 30 40 50 80
fmt.Println("\nSearch 40:", tree.Search(40)) // true
}
Удаление узла
— более сложная операция (три случая: нет детей, один ребёнок, два
ребёнка). Для краткости опущена, но реализуется заменой на наименьший
элемент в правом поддереве.
6.2. Куча (Heap) — приоритетная очередь
Суть:
Куча — это бинарное дерево, в котором для каждого узла выполняется
свойство: значение родителя больше (max-куча) или меньше (min-куча)
значений детей. Куча не является полностью отсортированной, но корень
всегда максимальный/минимальный. В Go можно использовать container/heap — пакет, требующий реализации интерфейса heap.Interface.
Пример min-кучи с использованием стандартного пакета
go
package main
import (
"container/heap"
"fmt"
)
// IntHeap реализует heap.Interface
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // Min-heap
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{5, 3, 8, 1}
heap.Init(h)
heap.Push(h, 2)
fmt.Println("Min:", (*h)[0]) // 1
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
} // 1 2 3 5 8
}
Применение кучи:
- Алгоритм Дейкстры (поиск кратчайшего пути).
- Сортировка HeapSort (O(n log n)).
- Поиск k наименьших/наибольших элементов.
7. Префиксное дерево (Trie)
Суть:
Trie (или «нагруженное дерево») используется для эффективного хранения
строк и операций с префиксами. Каждый узел соответствует символу, а путь
от корня до узла образует строку. Поиск строки или всех строк с
заданным префиксом выполняется за O(L), где L — длина строки, независимо
от количества сохранённых строк.
Реализация на Go
go
package main
import "fmt"
type TrieNode struct {
children map[rune]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
// Вставка слова
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
if node.children[ch] == nil {
node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[ch]
}
node.isEnd = true
}
// Поиск полного слова
func (t *Trie) Search(word string) bool {
node := t.root
for _, ch := range word {
if node.children[ch] == nil {
return false
}
node = node.children[ch]
}
return node.isEnd
}
// Проверка наличия префикса
func (t *Trie) StartsWith(prefix string) bool {
node := t.root
for _, ch := range prefix {
if node.children[ch] == nil {
return false
}
node = node.children[ch]
}
return true
}
func main() {
trie := NewTrie()
trie.Insert("hello")
trie.Insert("helium")
fmt.Println(trie.Search("hello")) // true
fmt.Println(trie.Search("hell")) // false
fmt.Println(trie.StartsWith("hel")) // true
}
Где применяется:
- Автодополнение в поисковых системах.
- Проверка орфографии.
- IP-маршрутизация (Longest Prefix Match).
8. Графы (Graphs)
Суть:
Граф — совокупность вершин и рёбер (связей между ними). Графы бывают
ориентированные (digraph) и неориентированные, взвешенные и
невзвешенные. Способы представления: матрица смежности (O(V²) памяти,
быстрый доступ) и список смежности (O(V+E) памяти, экономичнее для
разреженных графов).
В Go обычно используют список смежности: map[vertex][]vertex или map[vertex][]edge.
Реализация неориентированного графа
go
package main
import "fmt"
type Graph struct {
adj map[int][]int
}
func NewGraph() *Graph {
return &Graph{adj: make(map[int][]int)}
}
// Добавление ребра (неориентированное)
func (g *Graph) AddEdge(u, v int) {
g.adj[u] = append(g.adj[u], v)
g.adj[v] = append(g.adj[v], u)
}
// BFS (поиск в ширину) от вершины start
func (g *Graph) BFS(start int) {
visited := make(map[int]bool)
queue := []int{start}
visited[start] = true
for len(queue) > 0 {
vertex := queue[0]
queue = queue[1:]
fmt.Print(vertex, " ")
for _, neighbor := range g.adj[vertex] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
fmt.Println()
}
// DFS (поиск в глубину) рекурсивно
func (g *Graph) DFS(start int, visited map[int]bool) {
if visited == nil {
visited = make(map[int]bool)
}
visited[start] = true
fmt.Print(start, " ")
for _, neighbor := range g.adj[start] {
if !visited[neighbor] {
g.DFS(neighbor, visited)
}
}
}
func main() {
g := NewGraph()
g.AddEdge(1, 2)
g.AddEdge(1, 3)
g.AddEdge(2, 4)
g.AddEdge(3, 4)
fmt.Print("BFS: ")
g.BFS(1) // 1 2 3 4
fmt.Print("DFS: ")
g.DFS(1, nil) // 1 2 4 3
}
Алгоритмы на графах (кратко):
- Поиск кратчайшего пути: Дейкстра (невзвешенный – BFS), Беллман-Форд (отрицательные веса).
- Минимальное остовное дерево: Прим, Краскал.
- Топологическая сортировка (DAG).
Применение: социальные сети, карты (навигация), сети передачи данных.
9. Система непересекающихся множеств (DSU / Union-Find)
Суть:
DSU — структура, которая эффективно объединяет множества и проверяет,
принадлежат ли два элемента одному множеству. Используется в задачах о
связности компонент, алгоритме Краскала, кластеризации. Основные
операции: Find (с сжатием пути) и Union (по рангу/размеру).
Реализация
go
package main
import "fmt"
type DSU struct {
parent []int
rank []int
}
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
}
return &DSU{parent: parent, rank: rank}
}
// Find с сжатием пути
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x])
}
return d.parent[x]
}
// Union по рангу
func (d *DSU) Union(x, y int) {
xRoot := d.Find(x)
yRoot := d.Find(y)
if xRoot == yRoot {
return
}
if d.rank[xRoot] < d.rank[yRoot] {
d.parent[xRoot] = yRoot
} else if d.rank[xRoot] > d.rank[yRoot] {
d.parent[yRoot] = xRoot
} else {
d.parent[yRoot] = xRoot
d.rank[xRoot]++
}
}
// Connected проверяет связность
func (d *DSU) Connected(x, y int) bool {
return d.Find(x) == d.Find(y)
}
func main() {
dsu := NewDSU(5)
dsu.Union(0, 1)
dsu.Union(1, 2)
fmt.Println(dsu.Connected(0, 2)) // true
fmt.Println(dsu.Connected(0, 3)) // false
}
Сложность: Почти O(1) (обратная функция Аккермана) при использовании обеих эвристик.
Заключение
Мы
рассмотрели основные структуры данных, которые должен знать каждый
разработчик: от простых массивов до сложных графов и DSU. Каждая
структура имеет свои сильные и слабые стороны. Выбор правильной
структуры — это баланс между скоростью операций, потреблением памяти и
удобством реализации. В Go встроенные слайсы и map покрывают 80%
повседневных задач, но для остальных 20% нужно уметь строить связные
списки, деревья и графы.
Что делать дальше:
- Поэкспериментируйте с кодом: измените BST на AVL-дерево (добавьте балансировку).
- Реализуйте взвешенный граф и алгоритм Дейкстры.
- Напишите свою кучу без container/heap.
- Попробуйте решить задачи на LeetCode, помеченные тегами соответствующих структур данных.
Помните: структуры данных — это не просто теория, это инструмент, который делает код быстрым, понятным и масштабируемым. Удачи в программировании на Go!