Массив (Array): коллекция элементов фиксированной длины, размещённых в непрерывной области памяти.
Обеспечивает доступ по индексу за O(1).
Матрица (двумерный массив, Matrix): Массив с двумя или более измерениями, часто используется для представления таблиц, сеток, графов, а также при решении задач динамического программирования.
Связный список (Linked List): Динамическая структура, состоящая из узлов, каждый из которых содержит данные и ссылку на следующий (или предыдущий) элемент.
Виды: односвязный, двусвязный, кольцевой.
Стек (Stack): Структура данных типа LIFO («последним пришёл — первым ушёл»).
Операции: добавление (push), удаление (pop) и просмотр вершины (peek) — все за O(1).
Очередь (Queue): структура данных типа FIFO («первым пришёл — первым ушёл»). Операции: добавление в конец (enqueue) и удаление из начала (dequeue) — обе за O(1). Используется для последовательной обработки элементов.
Хэш-таблица (Hash Table, HashMap): Структура «ключ-значение», обеспечивающая быстрый доступ, вставку и удаление в среднем за O(1) с помощью хэш-функции. В худшем случае — O(N) (при коллизиях).
Дерево (Tree): иерархическая структура с корневым и дочерними узлами. Важные разновидности: бинарное дерево, N-арное дерево, AVL-дерево, красно-чёрное дерево.
Бинарное дерево поиска (BST): частный случай дерева: значения в левом поддереве меньше значения корня, в правом — больше.
В сбалансированном дереве операции поиска, вставки и удаления выполняются за O(log N).
Куча (Heap, приоритетная очередь): Бинарное дерево, элемент в котором больше (max-куча) или меньше (min-куча) своих потомков.
Вставка и удаление — O(log N), получение min/max — O(1).
Префиксное дерево (Trie): Специализированное дерево для эффективного хранения и поиска строк по префиксам. Операции выполняются за O(M), где M — длина строки.
Граф (Graph): Множество узлов (вершин), соединённых рёбрами. Часто представляется с помощью списка или матрицы смежности. Виды: ориентированный/неориентированный, взвешенный/невзвешенный.
Система непересекающихся множеств (Union-Find, Disjoint Set): Структура для отслеживания динамических компонент связности. Операции объединения (Union) и поиска (Find) выполняются почти за O(1) при использовании сжатия пути. Применяется, например, для поиска циклов и компонент связности в графах.
Сохраняйте шпаргалку, а поблагодарить можете лайком
