Как выбрать структуру
По задаче
| Задача |
Структура |
| Отмена действий (undo), обход в глубину, разбор скобок |
Stack |
| Очередь задач, обход в ширину, буферизация |
Queue |
| Скользящее окно, вставка и удаление с обоих концов |
Deque |
| Хранить только последние N событий (логи, история) |
CircularBuffer |
| Частые вставки и удаления в середине по ссылке на узел |
DoublyLinkedList |
| Отсортированное множество с поиском соседей и диапазонов |
RedBlackTree, AVLTree, SkipList |
| Отсортированный словарь «ключ → значение» |
SortedMap |
| Постоянно доставать минимум или максимум |
MinHeap, MaxHeap, BinaryHeap |
| Планировщик задач с приоритетами |
PriorityQueue |
| Автодополнение, поиск по префиксу |
Trie |
| Сумма, минимум или максимум на отрезке с изменениями |
SegmentTree |
| Только префиксные суммы с изменениями |
FenwickTree |
| Большой набор флагов или небольших целых чисел |
BitSet |
| «Видели ли мы это раньше?» на миллионах элементов при малой памяти |
BloomFilter |
| Объединение групп, компоненты связности |
DisjointSet |
| Ключ с несколькими значениями, группировка |
MultiMap |
| Кэш ограниченного размера |
LRUCache |
| Маршруты, зависимости, сети |
Graph |
Сравнение упорядоченных множеств
|
BinarySearchTree |
AVLTree |
RedBlackTree |
SkipList |
| Поиск |
O(log n)…O(n) |
O(log n) |
O(log n) |
O(log n) в среднем |
| Вставка/удаление |
O(log n)…O(n) |
O(log n) |
O(log n) |
O(log n) в среднем |
| Высота |
не ограничена |
≤ 1.44·log₂ n |
≤ 2·log₂ n |
— |
| Когда выбирать |
учебные цели, заведомо случайные данные |
много чтений |
много изменений |
простота, предсказуемый код |
BinarySearchTree не балансируется: на отсортированных данных он вырождается в список.
Если не уверены, берите RedBlackTree.
Сложность операций
n — число элементов, L — длина строки, k — число хэш-функций, α — обратная функция Аккермана.
Звёздочкой отмечена амортизированная оценка.
| Структура |
Доступ |
Поиск |
Вставка |
Удаление |
| Stack |
вершина O(1) |
— |
O(1)* |
O(1) |
| Queue |
начало O(1) |
— |
O(1)* |
O(1) |
| Deque |
по индексу O(1) |
— |
O(1)* с обоих концов |
O(1) с обоих концов |
| CircularBuffer |
по индексу O(1) |
— |
O(1) |
O(1) с обоих концов |
| LinkedList |
O(n) |
O(n) |
O(1) в начало и в конец |
O(1) из начала |
| DoublyLinkedList |
концы O(1) |
O(n) |
O(1) |
O(1) по узлу |
| AVLTree / RedBlackTree |
min/max O(log n) |
O(log n) |
O(log n) |
O(log n) |
| SkipList |
min O(1) |
O(log n) |
O(log n) |
O(log n) |
| SortedMap |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| BinaryHeap |
вершина O(1) |
— |
O(log n) |
вершина O(log n) |
| PriorityQueue |
вершина O(1) |
— |
O(log n) |
вершина O(log n) |
| Trie |
— |
O(L) |
O(L) |
O(L) |
| SegmentTree |
O(1) |
запрос O(log n) |
— |
изменение O(log n) |
| FenwickTree |
O(log n) |
запрос O(log n) |
— |
изменение O(log n) |
| BitSet |
O(1) |
O(1) |
O(1) |
O(1) |
| BloomFilter |
— |
O(k) |
O(k) |
не поддерживается |
| DisjointSet |
— |
find O(α(n)) |
O(1) |
— |
| LRUCache |
O(1) |
O(1) |
O(1) |
O(1) |