Назовите распространённые структуры данных и объяснить их практическое применение в разработке программного обеспечения.

Подсказки:

• Рассмотрите структуры, используемые для хранения коллекций элементов.
• Какие есть структуры данных, оптимизированные для конкретных операций, таких как поиск, вставка или извлечение данных?
• Примеры могут включать структуры, используемые для реализации кэшей, управления вызовами функций или представления иерархических отношений.

Выше ожиданий:

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

Массивы

Массивы — это непрерывные блоки памяти, хранящие элементы одного типа. Каждый элемент доступен по индексу.

Временная сложность:

• Доступ: O(1)
• Поиск: O(n) для несортированных, O(log n) для сортированных (бинарный поиск)
• Вставка/Удаление: O(n) (требует перемещения элементов)

Применение:

• "Строительные блоки" для более сложных структур данных
• Реализация матриц и векторов
• Хранение и обработка изображений (массивы пикселей)
• Управление буферами в потоковых приложениях

Связанные списки

Коллекции узлов, где каждый узел содержит данные и ссылку на следующий узел (и предыдущий узел в двусвязанных списках).

Временная сложность:

• Доступ: O(n)
• Поиск: O(n)
• Вставка/Удаление: O(1), если позиция известна, O(n) для поиска позиции

Применение:

• Реализация стеков, очередей и хэш-таблиц
• Управление памятью (выделение/освобождение)
• Музыкальные плейлисты (следующая/предыдущая песня)
• Навигация по истории браузера

Стеки

Структуры данных LIFO (Last In, First Out), поддерживающие операции push и pop. То положить на верх стока и убрать сверху стека.

Временная сложность:

• Push/Pop (вставка/удаление): O(1)
• Доступ/Поиск: O(n)

Применение:

• Управление вызовами функций (стек вызовов)
• Вычисление выражений и синтаксический разбор
• Механизмы отмены в приложениях
• Алгоритмы с возвратом (backtracking)

Визуализация стека:
| D | <- Вершина
| C |
| B |
| A |
----

Очереди

Структуры данных FIFO (First In, First Out), поддерживающие операции enqueue и dequeue - поставить в конец очереди и взять элемент из головы очереди.

Временная сложность:

• Enqueue/Dequeue: O(1)
• Доступ/Поиск: O(n)

Применение:

• Планирование задач в операционных системах
• Обработка запросов в веб-серверах
• Алгоритм поиска в ширину
• Управление заданиями печати

Голова -> | A | -> | B | -> | C | -> | D | <- Хвост

Хэш-таблицы

Структуры данных, которые сопоставляют ключи значениям, используя хеш-функцию.

Временная сложность:

• Поиск/Вставка/Удаление: O(1) в среднем случае, O(n) в худшем случае

Применение:

• Реализация словарей и карт
• Индексация баз данных
• Механизмы кэширования (кэш LRU)
• Подсчёт частот (например, подсчёт слов)
• Таблицы символов в компиляторах

 _______________________________________________________________
|                                                              |
| [0] -> [ключ|значение]                                       |
|                                                              |
| [1] -> [ключ|значение] -> [ключ|значение]                    |
|                                                              |
| [2]                                                          |
|                                                              |
| [3] -> [ключ|значение]                                       |
|                                                              |
| [4] -> [ключ|значение] -> [ключ|значение] -> [ключ|значение] |
|                                                              |
| [5]                                                          |
|______________________________________________________________|

hash(ключ) % размер_массива = индекс_ведёрка

Деревья

Иерархические структуры с корневым узлом и дочерними узлами.

Двоичные деревья поиска

Деревья, в которых для каждого узла левое поддерево содержит меньшие значения, а правое поддерево — большие значения.

Временная сложность:

• Поиск/Вставка/Удаление: O(log n) в среднем, O(n) в худшем случае

Применение:

• Эффективный поиск и сортировка
• Приоритетные очереди
• Разбор выражений
• Таблицы маршрутизации в сетях

Двоичное дерево поиска:
    8
   / \
  3   10
 / \    \
1   6    14

Кучи

Полные двоичные деревья, удовлетворяющие свойству кучи (Min Heap or Max Heap).

Временная сложность:

• Найти Минимум/Максимум: O(1)
• Вставка/Удаление: O(log n)

Применение:

• Приоритетные очереди
• Алгоритм сортировки кучей
• Алгоритмы обработки графов (алгоритм Дейкстры)
• Управление памятью

Max Heap

      9
    /   \
   6     8
  / \   / \
 5   3 7   2

Представление в виде массива: [9, 6, 8, 5, 3, 7, 2]

Для максимальной кучи:

• Родитель(i) = floor((i-1)/2)
• ЛевыйПотомок(i) = 2i + 1
• ПравыйПотомок(i) = 2i + 2

Графы

Коллекции узлов (вершин), соединённых рёбрами.

Временная сложность:

• Зависит от представления и алгоритма

Применение:

• Моделирование социальных сетей
• Дорожные сети и навигация
• Разрешение зависимостей
• Алгоритмы маршрутизации
• Задачи потоков в сетях

Взаимозаменяемость структур данных

1. Массивы против связанных списков:

   • Массивы обеспечивают доступ O(1), но вставка/удаление дорогостоящие
   • Связанные списки предлагают вставку/удаление O(1), но доступ медленнее

2. Хэш-таблицы против деревьев:

   • Хэш-таблицы обеспечивают более быстрый поиск в среднем случае
   • Деревья сохраняют порядок и гарантируют производительность в худшем случае

3. Потребление памяти:

   • Массивы используют непрерывные блоки памяти
   • Структуры со ссылками имеют накладные расходы на указатели
   • Хэш-таблицы могут тратить память на разреженные массивы