12 важнейших структур данных для технических собеседований

1. Массивы
* Коллекция элементов фиксированного размера, хранящихся в непрерывной области памяти
* Обеспечивает доступ по индексу за O(1)

2. Матрица (двумерный массив)
* Многомерная структура данных для представления сеток, графов и решения задач динамического программирования

3. Связный список
* Динамическая структура данных, где элементы (узлы) связаны через указатели
* Типы: односвязный список, двусвязный список, кольцевой связный список

4. Стек
* Структура данных типа Last-In-First-Out (LIFO), где последний добавленный элемент удаляется первым
* Поддерживает операции push, pop и peek за O(1)

5. Очередь
* Структура данных типа First-In-First-Out (FIFO)
* Позволяет добавлять элементы в конец (enqueue) и удалять из начала (dequeue) за O(1)
* Используется для обработки элементов в том же порядке, в котором они были добавлены

6. Хеш-таблица
* Структура данных типа "ключ-значение", использующая хеш-функцию для быстрого поиска
* Обеспечивает среднее время O(1) для операций вставки/удаления/поиска, в худшем случае O(N) (из-за коллизий)

7. Дерево
* Иерархическая структура данных с корневым узлом и дочерними узлами
* Типы: бинарное дерево, N-арное дерево, AVL-дерево, красно-чёрное дерево

8. Бинарное дерево поиска (BST)
* Специальное дерево, где левый потомок < корень < правый потомок
* Обеспечивает O(log N) для поиска, вставки и удаления в сбалансированных BST

9. Куча (приоритетная очередь)
* Структура данных на основе бинарного дерева, где родительский элемент всегда больше (max heap) или меньше (min heap) дочерних
* Обеспечивает O(log N) для вставки/удаления и O(1) для получения минимума/максимума

10. Префиксное дерево (Trie)
* Дерево для быстрого поиска строк
* Обеспечивает O(M) для операций вставки/поиска/удаления, где M — длина строки

11. Граф
* Набор узлов (вершин), соединённых рёбрами
* Представляется с помощью списка смежности (эффективно) или матрицы смежности
* Типы: ориентированный, неориентированный, взвешенный, невзвешенный

12. Система непересекающихся множеств (Union-Find / Disjoint Set)
* Структура данных для эффективной обработки динамической связности
* Поддерживает операции Union(x, y) и Find(x) почти за O(1) (с сжатием путей)
* Применяется для обнаружения циклов и поиска компонент связности в графе