Data structs

Ось перелік найпоширеніших структур даних у програмуванні, приблизно відсортований за частотою практичного використання в реальних проєктах (від найчастіших до більш спеціалізованих).

Місце	Структура даних	Для чого використовується
1	Масив (Array)	Зберігання послідовностей елементів, швидкий доступ за індексом
2	Динамічний масив (Vector, ArrayList, List)	Масив зі змінним розміром
3	Хеш-таблиця (Hash Map, Dictionary, Hash Table)	Швидкий пошук за ключем
4	Множина (Set, HashSet)	Зберігання унікальних значень
5	Зв’язний список (Linked List)	Часті вставки та видалення елементів
6	Черга (Queue)	Обробка в порядку FIFO
7	Стек (Stack)	Обробка в порядку LIFO
8	Дерево (Tree)	Ієрархічні дані
9	Бінарне дерево пошуку (BST)	Впорядковане зберігання даних
10	Купа (Heap, Priority Queue)	Робота з пріоритетами
11	Граф (Graph)	Мережі, маршрути, залежності
12	Trie (Префіксне дерево)	Пошук слів, автодоповнення
13	Збалансовані дерева (AVL, Red-Black Tree)	Впорядковані колекції з гарантованою швидкістю
14	B-Tree, B+Tree	Бази даних та файлові системи
15	Deque (двостороння черга)	Додавання та видалення з обох кінців
16	Skip List	Альтернатива збалансованим деревам
17	Segment Tree	Швидкі запити на відрізках
18	Fenwick Tree (BIT)	Префіксні суми
19	Disjoint Set (Union-Find)	Об’єднання множин
20	Suffix Tree / Suffix Array	Обробка рядків
21	Bloom Filter	Імовірнісна перевірка належності
22	KD-Tree	Просторовий пошук
23	QuadTree / OctTree	Геометрія, ігри
24	Rope	Ефективна робота з великими текстами

Найважливіші структури для співбесід і повсякденної роботи

Якщо вчити структури даних за пріоритетом, я б рекомендував такий порядок:

Масиви (Array)
Хеш-таблиці (HashMap)
Stack
Queue
Linked List
Tree
Heap / Priority Queue
Graph
Set
Trie
Union-Find
Segment Tree

Ці структури покривають приблизно 90–95% задач, які зустрічаються на співбесідах та в повсякденній розробці.

За складністю вивчення

Початковий рівень:

Array
Dynamic Array
Stack
Queue
Set
Hash Map

Середній рівень:

Linked List
Tree
Heap
Binary Search Tree
Graph

Просунутий рівень:

AVL Tree
Red-Black Tree
Trie
Union-Find
Segment Tree
Fenwick Tree
B-Tree

Експертний рівень:

Suffix Tree
KD-Tree
Bloom Filter
Skip List
Rope
QuadTree

Ось дорожня карта структур даних для співбесід і алгоритмічного програмування. Вона побудована так, щоб кожна наступна структура спиралася на попередні.

1. Масив (Array)

Найважливіша структура даних.

[10, 20, 30, 40]
 0   1   2   3

Основні операції

Операція	Складність
Доступ за індексом	O(1)
Зміна елемента	O(1)
Пошук	O(n)
Вставка в кінець	O(1)
Вставка всередину	O(n)
Видалення	O(n)

Типові задачі

Two Sum
Maximum Subarray
Sliding Window
Prefix Sum

2. Хеш-таблиця (HashMap)

Зберігає пари ключ → значення.

"apple" -> 5
"banana" -> 8

Операції

Операція	Складність
Пошук	O(1)
Вставка	O(1)
Видалення	O(1)

Типові задачі

Підрахунок частот
Кешування
Швидкий пошук

Приклад:

freq = {}

for x in nums:
    freq[x] = freq.get(x, 0) + 1

3. Множина (Set)

Зберігає лише унікальні значення.

{1, 5, 7}

Операції

Операція	Складність
Перевірка наявності	O(1)
Додавання	O(1)
Видалення	O(1)

Типові задачі

Пошук дублікатів
Перевірка унікальності

4. Стек (Stack)

Принцип LIFO:

3 ← top
2
1

Операції

Операція	Складність
push	O(1)
pop	O(1)
top	O(1)

Типові задачі

Дужки
Undo/Redo
DFS
Обчислення виразів

5. Черга (Queue)

Принцип FIFO:

1 -> 2 -> 3

Операції

Операція	Складність
enqueue	O(1)
dequeue	O(1)
front	O(1)

Типові задачі

BFS
Планувальники задач
Потоки повідомлень

6. Зв’язний список (Linked List)

10 -> 20 -> 30 -> null

Операції

Операція	Складність
Доступ за індексом	O(n)
Вставка на початку	O(1)
Видалення вузла	O(1)

Типові задачі

Reverse Linked List
Detect Cycle
Merge Lists

7. Бінарне дерево (Binary Tree)

      10
     /  \
    5   15

Обходи

DFS

Preorder
Inorder
Postorder

BFS

Рівень за рівнем.

Типові задачі

Maximum Depth
Tree Traversal
Lowest Common Ancestor

8. Бінарне дерево пошуку (BST)

      8
     / \
    3  10

Ліві значення менші, праві більші.

Складність

Операція	Середня
Пошук	O(log n)
Вставка	O(log n)
Видалення	O(log n)

9. Купа (Heap)

Зазвичай використовують Min Heap.

      1
     / \
    3   5

Операції

Операція	Складність
Отримати мінімум	O(1)
Вставка	O(log n)
Видалення мінімуму	O(log n)

Типові задачі

Top K Elements
Kth Largest
Планувальники

10. Граф (Graph)

A --- B
|     |
C --- D

Представлення

Список суміжності

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D']
}

Обходи

Типові задачі

Найкоротший шлях
Соціальні мережі
Маршрути

11. Trie

Для роботи з рядками.

Типові задачі

Автодоповнення
Словники
Пошук префіксів

Складність

Операція	Час
Вставка	O(L)
Пошук	O(L)

де L — довжина слова.

12. Union-Find (Disjoint Set)

Відстежує групи елементів.

1 - 2 - 3

4 - 5

Операції

Операція	Складність
Find	майже O(1)
Union	майже O(1)

Типові задачі

Пошук компонент зв’язності
Алгоритм Крускала
Графи

13. Segment Tree

Для швидких запитів на відрізках.

Наприклад:

сума [2..8]
максимум [5..10]

Операції

Операція	Складність
Запит	O(log n)
Оновлення	O(log n)

Мінімальний набір для 80% співбесід

Якщо часу мало, достатньо освоїти:

✅ Array ✅ HashMap ✅ Set ✅ Stack ✅ Queue ✅ Linked List ✅ Tree (DFS/BFS) ✅ Heap ✅ Graph (DFS/BFS)

Ці дев’ять структур покривають більшість задач на платформах на кшталт LeetCode, HackerRank та Codeforces.

Орієнтовний розподіл задач

Структура	Частка задач
Array + HashMap	~40%
Tree	~20%
Graph	~15%
Stack/Queue	~10%
Heap	~10%
Інші	~5%

Так. Насправді структур даних значно більше, ніж 24. Той список охоплює найвідоміші та найпрактичніші. Якщо враховувати академічні, спеціалізовані, розподілені, геометричні та ймовірнісні структури, їх можна нарахувати сотні.

Ось додаткові структури даних, яких не було в попередньому списку.

Лінійні структури

Circular Array (кільцевий масив)
Circular Linked List
Doubly Linked List
Unrolled Linked List
XOR Linked List
Gap Buffer (використовується в текстових редакторах)
Piece Table (редактори тексту)

Черги та стеки

Circular Queue
Deque (якщо не враховувати окремо)
Monotonic Queue
Monotonic Stack
Concurrent Queue
Lock-Free Queue
Blocking Queue

Дерева

Крім BST, AVL та Red-Black:

Splay Tree
Treap
AA Tree
Scapegoat Tree
Cartesian Tree
Tournament Tree
Interval Tree
Range Tree
Order Statistic Tree
Van Emde Boas Tree
Finger Tree
Radix Tree
Patricia Trie
Ternary Search Tree

Купи (Heap)

Окрім звичайної Binary Heap:

Binomial Heap
Fibonacci Heap
Pairing Heap
Leftist Heap
Skew Heap
D-ary Heap
Soft Heap

Структури для рядків

Окрім Trie та Suffix Tree:

Suffix Automaton
Aho-Corasick Automaton
Directed Acyclic Word Graph
Palindromic Tree

Структури для діапазонних запитів

Окрім Segment Tree та Fenwick Tree:

Sparse Table
Wavelet Tree
Li Chao Tree
Merge Sort Tree

Геометричні структури

Окрім KD-Tree та QuadTree:

R-Tree
R+ Tree
R* Tree
BSP Tree
Bounding Volume Hierarchy
k-d-B Tree

Ймовірнісні структури

Окрім Bloom Filter:

Counting Bloom Filter
Cuckoo Filter
Quotient Filter
HyperLogLog
Count-Min Sketch
MinHash

Графові структури

Adjacency Matrix
Adjacency List
Incidence Matrix
Edge List
Dynamic Graph
Compressed Sparse Row (CSR)
Compressed Sparse Column (CSC)

Структури для баз даних

Окрім B-Tree:

LSM Tree
Bε Tree
Fractal Tree
Adaptive Radix Tree

Конкурентні та розподілені структури

Lock-Free Stack
Lock-Free Queue
Concurrent HashMap
Concurrent Skip List
Distributed Hash Table (DHT)
Consistent Hash Ring

Функціональні (immutable) структури

Persistent Array
Persistent Segment Tree
Persistent Trie
Persistent Heap
Persistent Queue
Persistent Map

Якщо говорити про фундаментальні структури, з яких будуються майже всі інші, то їх небагато:

Масив (Array)
Зв’язний список (Linked List)
Хеш-таблиця (Hash Table)
Дерево (Tree)
Купа (Heap)
Граф (Graph)
Стек (Stack)
Черга (Queue)

Близько 90% усіх інших структур — це модифікації, комбінації або оптимізації цих восьми базових ідей. Наприклад, Trie — це спеціалізоване дерево, HashSet — хеш-таблиця без значень, Priority Queue зазвичай реалізується через Heap, а B-Tree є різновидом дерева пошуку для дисків і баз даних.