Массив — линейная структура данных, где элементы хранятся в непрерывной области памяти.
- Доступ по индексу: O(1)
- Вставка/удаление в середине: O(n) из-за сдвига элементов
- В Python:
list
Связный список — линейная структура данных, где каждый элемент (узел) содержит данные и ссылку на следующий узел.
- Доступ по индексу: O(n)
- Вставка/удаление при наличии указателя: O(1)
- В Python:
collections.deque для двусвязного списка
Стек (Stack) — структура данных с принципом LIFO (Last In First Out).
- Операции: push (добавление), pop (извлечение) — O(1)
- Применения: вызов функций (call stack), undo/redo, проверка скобок, DFS
- В Python:
list.append() и list.pop()
Очередь (Queue) — структура данных с принципом FIFO (First In First Out).
- Операции: enqueue (добавление), dequeue (извлечение) — O(1)
- Применения: BFS, задачи планирования, буферизация
- В Python:
collections.deque для очереди
Хэш-таблица — структура данных для хранения пар ключ-значение с высокой производительностью.
- Поиск, вставка, удаление: O(1) в среднем случае
- Коллизии решаются через chaining (связные списки) или open addressing
- В Python:
dict
Дерево — специальный вид графа без циклов с одним корнем и ровно одним путём между любыми двумя узлами.
- Высота дерева влияет на сложность операций: O(log n) для сбалансированного, O(n) для вырожденного
- BST (Binary Search Tree): поиск/вставка/удаление за O(h)
Граф — более общая структура с произвольными рёбрами, которые могут образовывать циклы.
- Дерево является частным случаем графа
- Применения: социальные сети, карты дорог, зависимости пакетов
#Практические рекомендации
- Используйте
deque вместо list для очередей (O(1) vs O(n) для операций с начала)
- Для часто используемых операций поиска выбирайте хэш-таблицы
- Учитывайте баланс между временем выполнения и потреблением памяти
- Выбирайте структуру данных в зависимости от типичных операций в вашей задаче