# Структуры данных

> Способы организации данных в памяти — массивы, списки, стеки, очереди, хеш-таблицы, деревья, кучи и графы — определяющие, какие операции выполняются быстро.

Источник: https://llmdocs.ru/wiki/data-structures/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Определение**: способ хранения и организации данных для эффективного доступа и изменения
- **Линейные**: массив, связный список, стек, очередь, дек
- **Ассоциативные**: хеш-таблица, множество, словарь
- **Иерархические**: деревья, кучи, префиксные деревья
- **Сетевые**: графы
- **Ключевая книга**: Никлаус Вирт «Алгоритмы + структуры данных = программы» (1976)
**Структура данных** — способ организации и хранения данных в памяти компьютера, определяющий, какие операции с ними выполняются быстро, а какие медленно. Один и тот же набор чисел можно хранить в массиве, связном списке, хеш-таблице или дереве, и от этого выбора зависит, займёт поиск элемента наносекунды или секунды. Никлаус Вирт выразил эту связь названием книги «Алгоритмы + структуры данных = программы» (1976).

Различают **абстрактный тип данных** — что структура умеет (например, «очередь: добавить в конец, взять из начала») — и его **реализацию** — как это устроено в памяти (кольцевой буфер или связный список). Скорость операций описывают с помощью [O-нотации](https://llmdocs.ru/wiki/big-o.md).

## Основные структуры

| Структура | Доступ по индексу | Поиск | Вставка / удаление | Особенности |
|---|---|---|---|---|
| Массив (динамический) | O(1) | O(n) | O(n), в конец — O(1) амортизированно | непрерывная память, дружит с кэшем процессора |
| Связный список | O(n) | O(n) | O(1) при известной позиции | нет перераспределения памяти, но медленный обход |
| Стек | — | — | O(1) на вершине | последним вошёл — первым вышел (LIFO) |
| Очередь, дек | — | — | O(1) с концов | первым вошёл — первым вышел (FIFO) |
| [Хеш-таблица](https://llmdocs.ru/wiki/hash-table.md) | — | O(1) в среднем | O(1) в среднем | нет порядка, нужна хорошая хеш-функция |
| Сбалансированное дерево поиска | — | O(log n) | O(log n) | хранит ключи упорядоченно, диапазонные запросы |
| Куча (двоичная) | — | минимум за O(1) | O(log n) | очередь с приоритетом |
| Граф | — | зависит от алгоритма | — | связи «многие ко многим» |

### Массив

Элементы лежат в памяти подряд, поэтому адрес любого вычисляется по индексу мгновенно, а последовательный проход очень быстр благодаря кэшу процессора. **Динамический массив** (`list` в [Python](https://llmdocs.ru/wiki/python.md), `Vec` в [Rust](https://llmdocs.ru/wiki/rust.md), срез в [Go](https://llmdocs.ru/wiki/go.md)) при переполнении выделяет память с запасом и копирует элементы, поэтому добавление в конец в среднем стоит O(1). Вставка в середину требует сдвига всех последующих элементов.

### Связный список

Каждый элемент хранит значение и ссылку на следующий (в двусвязном — и на предыдущий). Вставка и удаление в известном месте дешевы, но доступ к *i*-му элементу требует прохода от начала, а разбросанные по памяти узлы плохо используют кэш. На практике связные списки нужны реже, чем кажется по учебникам; их основа — в реализации очередей, LRU-кэшей и аллокаторов.

### Стек и очередь

**Стек** — как стопка тарелок: кладём и берём сверху. Он используется для вызовов функций (стек вызовов), отмены действий, разбора скобок и обхода в глубину. **Очередь** — как очередь в магазине: обработка задач в порядке поступления, обход графа в ширину, буферы сообщений. **Дек** (*deque*) позволяет добавлять и забирать с обоих концов.

### Хеш-таблица

Хеш-функция превращает ключ в номер ячейки, и поиск, вставка и удаление в среднем выполняются за O(1). На хеш-таблицах построены словари и множества почти во всех языках, кэши, индексы и дедупликация. Подробнее — в статье [Хеш-таблица](https://llmdocs.ru/wiki/hash-table.md).

### Деревья и кучи

**Деревья поиска** (красно-чёрные, AVL, [B-деревья](https://llmdocs.ru/wiki/b-tree.md)) хранят ключи упорядоченно и находят, вставляют и удаляют за O(log n), поддерживая запросы по диапазону; B-деревья лежат в основе [индексов баз данных](https://llmdocs.ru/wiki/database-index.md). **Куча** — дерево, где родитель не больше потомков; она быстро выдаёт минимальный элемент и используется в очередях с приоритетом, планировщиках и алгоритме Дейкстры. **Префиксное дерево** (*trie*) хранит строки по символам — для автодополнения и маршрутизации. Подробнее — в статье [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md).

### Графы

Граф — множество вершин и рёбер между ними: дороги между городами, зависимости пакетов, связи в соцсети, ссылки между страницами. Хранится списками смежности (экономно для редких связей) или матрицей смежности (быстрая проверка ребра).

## Структуры в Python

```python
from collections import deque, Counter, defaultdict
import heapq

stack = []; stack.append(1); stack.pop()           # список как стек
queue = deque(); queue.append("a"); queue.popleft()  # очередь O(1) с обоих концов
index = {"alice": 1, "bob": 2}                       # dict — хеш-таблица
unique = set(["a", "b", "a"])                        # множество
counts = Counter("mississippi")                      # подсчёт элементов
graph = defaultdict(list); graph["a"].append("b")    # список смежности

tasks = []
heapq.heappush(tasks, (2, "написать тесты"))
heapq.heappush(tasks, (1, "починить прод"))
print(heapq.heappop(tasks))                          # (1, 'починить прод') — минимальный приоритет
```

Модули `collections` и `heapq` стандартной библиотеки покрывают большинство повседневных задач;[3][4] сложность операций со встроенными типами сведена в таблицу на Python Wiki.[5] В других языках есть аналоги — например, модуль `std::collections` в Rust.[6]

## Как выбирать

1. Определите самые частые операции: поиск по ключу, доступ по порядку, добавление в конец, извлечение минимума, диапазонные запросы.
2. Подберите структуру, где именно они дешевы: частая проверка «есть ли элемент» — множество, а не список; извлечение самого срочного — куча; упорядоченный обход — дерево или отсортированный массив.
3. Учитывайте память и кэш: для небольших объёмов простой массив часто быстрее «правильной» структуры.
4. Используйте готовые реализации стандартной библиотеки — они отлажены и оптимизированы.

Систематическое изложение с доказательствами — в учебнике Кормена и соавторов.[1] Подробно о встроенных структурах Python — в официальном руководстве.[2]

## См. также

- [Алгоритм и O-нотация](https://llmdocs.ru/wiki/big-o.md)
- [Хеш-таблица](https://llmdocs.ru/wiki/hash-table.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)
- [B-дерево](https://llmdocs.ru/wiki/b-tree.md)
- [Сортировка](https://llmdocs.ru/wiki/sorting.md)

## Источники

1. [T. Cormen et al. — Introduction to Algorithms, 4th ed. (MIT Press)](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
2. [Python Tutorial — Data Structures](https://docs.python.org/3/tutorial/datastructures.html)
3. [Python — collections module](https://docs.python.org/3/library/collections.html)
4. [Python — heapq module](https://docs.python.org/3/library/heapq.html)
5. [Python Wiki — TimeComplexity](https://wiki.python.org/moin/TimeComplexity)
6. [Rust — std::collections](https://doc.rust-lang.org/std/collections/index.html)