Как ответить
Структуры данных — это способы организации и хранения данных в памяти, чтобы с ними можно было эффективно работать. Выбор структуры напрямую влияет на скорость операций: поиска, вставки, удаления. Для junior-разработчика важно понимать базовый набор: массивы, связные списки, хеш-таблицы, стеки и очереди, деревья.
Массивы — непрерывная область памяти с доступом по индексу за O(1). Минус — вставка и удаление в середину требуют сдвига элементов (O(n)). Использую, когда нужен быстрый доступ к элементам по порядковому номеру, например, для хранения списка ID пользователей.
Связные списки — каждый элемент хранит ссылку на следующий. Вставка и удаление в начало — O(1), но поиск элемента — O(n). На практике в продакшне редко встречаются в чистом виде, но на них построены очереди и кэши (LRU).
Хеш-таблицы (словари, HashMap) — хранят пары ключ-значение. В среднем операции вставки, удаления и поиска — O(1). В Java это HashMap, в Python — dict. Важно понимать коллизии: в Java они решаются цепочками, а при переполнении корзины > 8 — деревьями. Обычно использую для кэширования результатов запросов или группировки данных.
Стеки и очереди — стеки работают по принципу LIFO (Last In, First Out), очереди — FIFO (First In, First Out). Стек удобен для разбора скобок в парсерах или отмены действий (Ctrl+Z). Очередь — для обработки задач в порядке поступления (например, очередь запросов к API).
Деревья (бинарные, AVL, B-деревья) — для иерархических данных. В реальной работе чаще всего сталкиваешься с B-деревьями в базах данных (индексы в PostgreSQL — это B-tree). Для junior достаточно понимать, как работает BST и почему он может выродиться в список (если данные отсортированы).
Графы — используются в соцсетях (друзья друзей), рекомендательных системах, маршрутизации. Алгоритмы: BFS (поиск в ширину) для кратчайшего пути в невзвешенном графе, DFS (поиск в глубину) для проверки связности.
Пример из практики: если нужно быстро проверять, есть ли элемент в коллекции, беру HashSet (O(1)). Если нужно хранить порядок добавления — ArrayList. Если нужен быстрый поиск по ключу — HashMap. Если нужно сортировать при вставке — TreeSet (красно-чёрное дерево, O(log n)).
Главное правило: не существует идеальной структуры, всегда компромисс между скоростью чтения, записи и памятью. На собеседовании важно не просто перечислить, а объяснить, когда что выбираешь.