Зачем мне эти ваши структуры данных?

Какие бывают самые популярные классические структуры данных и под какой класс задач они подходят? Заметка построена без привязки к какому-либо языку программирования. Краткий обзор для простого и общего понимания.

1. Массив

Массив - некоторое количество непрерывной памяти, доступ к которой осуществляется по индексу. Бывают, как одномерные, так и многомерные. Главный недостаток - отсутствие динамики. И как следствие этого:

• невозможность удаления элемента (именно удаления, а не заNULLения);
• добавления в середину без сдвига других элементов;

Некоторые языки программирования предоставляют динамические массивы, но важно понимать, что под капотом такой динамики, как я понимаю, как правило, скрыто копирование массива целиком и вставка на другие ячейки памяти, что влечет за собой накладные расходы по быстродействию. То есть поиск элемента в массиве будет происходить по сложности алгоритма Big-O за O(N).

Под какие задачи выбирать: объем данных относительно невелик и сам объем известен заранее

2. Стек и очередь

2.1 Стек

Стек - структура данных, в которой элементы добавляются и удаляются в порядке "последним пришел - первым вышел" (LIFO - last in first out). Структура данных организована таким образом, что занесение и извлечение элементов из стека выполняется за O(1).

2.2 Очередь

Очередь - структура данных, в которой элементы добавляются в порядке "первым пришел - первым ушел" (FIFO - first in first out). Здесь организация, как у стека, вставка и извлечение выполняются за O(1).

Существую еще приоритетные очереди, у каких элементы упорядотачиваются по ключу. Новые элементы вставляются в позициях, сохраняющих порядок сортировки. У такой очереди вставка осуществляется за O(N), а извлечение за O(1). Приоритетная очередь может быть реализована на основе массива или пирамиды и во втором случае вставка и удаление будут за O(log N).

Под какие задачи выбирать: когда нужные операции выполняются только с последним или первым элементом.

4. Связные списки

Связный список - построен из объектов, что обычно называют ячейками. Этот класс содержит все данные, которые хранятся в списке и ссылку на другую/другие ячейки. Ссылка представляет собой справку или указатель на объект такого же класса. Поле типа указателя часто называют Next. Например, в Java, ссылка это число ассоциированное с объектом, соответствующее адресу объекта в памяти компьютера.

4.1 Однонаправленный связный список

В однонаправленном связном списке каждая ячейка связана со следующей с помощью одинарной ссылки.

4.2 Двусторонний список

Двусторонний список - хранит в себе ссылку не только на первый, но и на последний элемент, что позволяет вставлять новые элементы не только в начало, но и в конец списка, что позволяет не перебирать все содержимое до последние элемента.

Вставка и удаление в начале связного списка выполняется очень быстро, операция сводится к изменению одной или двух ссылок за время O(1). Поиск, удаление и вставка рядом с конкретным элементом за время O(N). У динамического массива эти операции выполняются за такое же время, но связный список работает быстрее, так как не требует перемещения элементов и происходит лишь смена ссылок.

Под какие задачи выбирать: объем данных неизвестен заранее. Или с данными часто выполняются операции вставки и удаления. Ведь в отличие от массива не требуется заполнения "дыр", оставленных при удалении.

5. Хэш-таблицы

Хэш-таблица - структура данных, хранящая данные в формате "ключ-значение" и обеспечивающая очень быструю вставку и поиск. Вставка, поиск (а иногда и удаление) обеспечиваются за время, близкое к постоянному O(1). По скорости значительно превосходят деревья.

Огромная проблема - коллизии. Коллизия - ситуация, когда для различных ключей генерируется один и тот же хэш. Поэтому, как правило, в самой структуре данных уже заложен метод решения коллизий (самые популярные - метод цепочек, метод открытой индексации).

Под какие задачи выбирать: когда есть уже какой-то большой объем данных, например, словарь из которого нужно как можно быстрее проверить много слов по определенным критериям.

6. Деревья

Дерево - состоит из узлов, соединенных ребрами. Деревья - самый обширный раздел, о котором, чтобы нормально написать нужно чуть ли не выделять отдельную заметку, поэтому здесь распишу в общем, так как деревья бывают очень разных типов. Ребра (соединительные линии между узлами) представляют собой отношения между узлами. Переходы между узлами возможны только по соединительным линиям. Ребра обычно представляются ссылками или указателями. Преимущество их использования в том, что операции добавления, удаления и поиска, как правило, в среднем происходят за время O(log N).

Под какие задачи выбирать: тогда, когда работа массивов, динамических массивов или связных списков оказывается слишком медленной.