Массив

Определение:

• Хранит элементы данных на основе последовательного индекса, чаще всего с нулевой базой.
• В его основе лежат кортежи из теории множеств.
• Массив — одна из старейших и наиболее используемых структур данных.

Особенности:

• Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива).
• Основная разновидность — линейные массивы, или одноразмерные.
  • Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.
• Динамические массивы подобны линейным, но в них зарезервировано пространство для дополнительных элементов.
  • При заполнении динамического массива его содержимое копируется в массив большего размер.
• Двумерные массивы имеют два индекса x и y, как сетки или вложенные массивы.

Эффективность («О» большое):

• Индексирование: линейный массив — O(1), динамический массив — O(1).
• Поиск: линейный массив — O(n), динамический массив — O(n).
• Оптимизированный поиск: линейный массив — O(log n), динамический массив — O(log n).
• Вставка: линейный массив — недопустимо, динамический массив — O(n).

Связный список

Определение:

• Данные хранятся в узлах, указывающих на другие узлы.
  • Узел содержит один элемент данных и одну ссылку (на другой узел).
  • Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.

Особенности:

• Связный список разработан для оптимизирования вставки и удаления. Медленно работает при индексировании и поиске.
• Двусвязный список содержит узлы, которые ссылаются на предыдущие узлы.
• Кольцевой связный список — это простой связный список, хвост которого (последний узел) ссылается на голову (первый узел).
• Стек обычно реализуется с помощью связных списков, но может быть создан и из массивов.
  • Стеки — это LIFO - структуры данных (last in, first out).
  • Голова связного списка, лежащего в основе стека, единственное место для вставки и удаления элементов.
• Очереди тоже могут быть реализованы с помощью связного списка или массива.
  • Очереди — это FIFO - структуры данных (first in, first out).
  • Очередь представляет собой двусвязный список, в котором элементы удаляются из головы, а добавляются в хвост.

Эффективность («О» большое):

• Индексирование: связный список — O(n).
• Поиск: связный список — O(n).
• Оптимизированный поиск: связный список — O(n).
• Вставка: связный список — O(1).

Хэш-таблица

Определение:

• Данные хранятся в виде пар ключ-значение.
• Хэш-функции принимают ключ и возвращают выходные данные, соответствующие только этому ключу.
  • Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.
  • Хэш-функции возвращают для данных уникальные адреса в памяти.

Особенности:

• Хэш-функции разработаны для оптимизирования поиска, вставки и удаления.
• Хэш-коллизиями называются ситуации, когда для двух разных входных данных функция возвращает одинаковые выходные данные.
  • Эта проблема свойственна всем хэш-функциям.
  • Часто она решается с помощью увеличения хэш-таблиц до огромного размера.
• Хэши важны для ассоциативных массивов и индексирования баз данных.

Эффективность («О» большое):

• Индексирование: хэш-таблицы — O(1).
• Поиск: хэш-таблицы — O(1).
• Вставка: хэш-таблицы — O(1).

Двоичное дерево

Определение:

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

Особенности:

• Деревья разработаны для оптимизирования списка и сортировки.
• Вырожденное дерево — это несбалансированное дерево. Если оно полностью одностороннее, то представляет собой, по сути, связный список.
• Деревья относительно просты в реализации по сравнению с другими структурами данных.
• Используются для создания двоичных деревьев поиска:
  • Двоичное дерево с помощью сравнивания ключей решает, в каком направлении следовать к дочернему узлу.
  • Ключ левого дочернего узла меньше, чем у родительского.
  • Ключ правого дочернего узла больше, чем у родительского.
  • Не может быть дублирующих узлов.
  • В связи с вышесказанным такое дерево чаще используется как структура данных, чем двоичное дерево.

Эффективность («О» большое):

• Индексирование: двоичное дерево поиска — O(log n).
• Поиск: двоичное дерево поиска — O(log n).
• Вставка: двоичное дерево поиска — O(log n).