Топ-8 структур данных для программиста OTUS
2026-03-10 15:24 Diff
https://otus.ru/journal/top-8-struktur-dannyh-dlya-programmista/screenshot_7-1-3/

В далеком 1976 году швейцарским ученым была написана книга «Алгоритмы + Структуры данных = Программы». Прошло уже более сорока лет, но это утверждение до сих пор актуально.  Вы должны знать структуры данных, если учите языки программирования и желаете стать разработчиком. И не только знать, но и уметь их применять. Причем не столь важно, закончили ли вы институт либо просто освоили курсы программирования, — на собеседовании при устройстве на работу у вас в 90 % случаев спросят про структуры данных.

Этот материал — адаптированный перевод статьи «The top data structures you should know for your next coding interview». В этом переводе будут вкратце рассмотрены основные структуры данных, которые могут понадобиться при программировании, плюс будут перечислены наиболее популярные вопросы, которые часто задают на собеседованиях.

Изучаем структуры данных: что это?

Если говорить простым языком, то структура данных представляет собой контейнер, в котором информация скомпонована специальным образом. Чего удается достичь благодаря такому строению? Для сравнения, скажем, что при выполнении одних операций определенная структура данных будет весьма эффективна, в то время как при выполнении других — не очень. Задача разработчика вне зависимости от языка программирования (language of programming) как раз в том и состоит, чтобы уметь выбирать наиболее подходящую структуру и знать, как сравнить их между собой с учетом поставленной задачи. Но это невозможно без ясного и единого представления о существующих способах организации информации. Именно это единое представление вы и получите в процессе изучения материалов этой статьи. И займет это совсем немного времени.

Изучаем структуры данных: зачем вообще они нужны?

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

Ниже перечислены самые распространенные способы структурирования данных:

  1. Массивы.
  2. Очереди.
  3. Стеки.
  4. Деревья.
  5. Связные списки.
  6. Графы.
  7. Боры.
  8. Хэш-таблицы.

Массивы

Самый распространенный способ структуризации. Ниже показан простейший массив из 4-х элементов:


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

Массивы бывают:

— одномерные (как на картинке);

— многомерные.

Простейшие операции:

  • Insert — вставка элемента на позицию с заданным индексом;
  • Get — возвращение элемента, занимающего позицию с заданным индексом;
  • Delete — удаление;
  • Size — получение общего числа элементов.

Какие вопросы, связанные с массивам, часто задают на собеседовании:

  • найдите 2-й минимальный элемент;
  • найдите неповторяющиеся целые числа;
  • выполните объединение двух отсортированных массивов;
  • выполните упорядочение положительных и отрицательных значений.

Стеки

Стек обычно сравнивают со стопкой книг. Когда нужно взять какую-либо книгу, к примеру, лежащую в центре стопки, вам надо сначала снять те книги, которые лежат выше. Это известный принцип LIFO (кто последний пришел, тот первый выйдет).

На картинке ниже — стек, который содержит 3 элемента:

Простейшие операции:

  • Push — вставка элемента в стек сверху;
  • Pop — возвращение верхнего компонента в стек после удаления;
  • isEmpty — возвращение true, когда стек пуст;
  • Top — возвращение верхнего компонента без удаления его из стека.

Вопросы о стеке:

  • вычислите постфиксное выражение посредством стека;
  • отсортируйте значения;
  • проверьте сбалансированные скобки в выражении.

Очереди

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

Изображение очереди:

Операции:

  • Enqueue() — добавление элемента в конец очереди;
  • Dequeue() — удаление элемента из начала;
  • isEmpty() — возвращение true, если очередь пуста;
  • Top() — возвращение первого элемента.

Вопросы:

  • реализовать стек посредством очереди;
  • обратить первые k-элементы в очереди;
  • сгенерировать двоичные числа от 1 до n, используя очередь.

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

Эта структура напоминает массив, но если выполнить сравнение, становится понятно, что связный список отличается по ряду характеристик:

— выделение памяти;

— внутренняя структура;

— особенности вставки и удаления.

Связный список можно назвать цепочкой узлов, причем каждый из них содержит информацию: к примеру, данные и указатель на последующий узел в цепочке. Существует головной указатель, который соответствует первому элементу в списке, а если список пуст, то указатель направлен на null.

Применение — реализация файловых систем, хэш-таблицы, списки смежности.

Типы:

  • односвязный (однонаправленный);
  • двусвязный (двунаправленный).

Простейшие действия:

  • InsertAtEnd — вставка заданного элемента в конец;
  • InsertAtHead — вставка в начало (с головы);
  • Delete — удаление из списка;
  • DeleteAtHead — удаление первого компонента;
  • Search — возвращение заданного компонента из списка;
  • isEmpty — возвращение true, если имеющийся список пуст.

Вопросы:

  • обратить связный список;
  • найти петлю;
  • вернуть N-ный узел с начала списка;
  • удалить дублирующиеся значения.

Графы

Графом называют множество узлов, которые соединены друг с другом, образуя сеть. Узлы = вершины. Пара (x, y) — это ребро, которое может иметь стоимость или вес, что характеризует, насколько затратным является переход от одной вершины к другой.

Типы:

  • неориентированные;
  • ориентированные.

В языке программирования популярны графы 2-х типов:

  • матрица смежности;
  • список смежности.

Также надо знать самые популярные алгоритмы обхода графа:

  • поиск в ширину;
  • поиск в глубину.

Вопросы к собеседованию, которые желательно проработать:

  • реализация поиска в ширину и глубину;
  • проверка, является ли граф деревом;
  • подсчет числа ребер;
  • поиск кратчайшего пути между 2-мя вершинами.

Деревья

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

Сегодня деревья применяются в сфере ИИ, а также в сложных алгоритмах, где они выступают в роли эффективного хранилища данных. С деревом знаком, по сути, любой программист.

Ниже — рисунок простого дерева:

Деревья бывают разных типов:

  • N-арное;
  • сбалансированное;
  • двоичное;
  • двоичное дерево поиска;
  • АВЛ-дерево;
  • красно-черное дерево;
  • 2—3 дерево.

Сегодня широко используют двоичные деревья.

На собеседовании у вас могут попросить найти:

  • высоту двоичного дерева;
  • k-ное максимальное значение в 2-чном древе поиска;
  • узлы, которые расположены на расстоянии “k” от корня;
  • предки заданной вершины в 2-чном дереве.

Бор

Второе название — «префиксное дерево». Речь идет о древовидной структуре, которая весьма эффективна в процессе решении задач на строки. Бор обеспечивает быстрое извлечение информации и часто используется при поиске слов в словаре, автоматических завершений в поисковике, а также в IP-маршрутизации.

Давайте посмотрим, как 3 слова «top», «thus» и «their» хранятся в бору:

Вопросы:

  • подсчет общего числа слов, которые сохранены в бору;
  • вывод на экран всех слов, сохраненных в бору;
  • сортировка элементов массива посредством бора;
  • построение слова из словаря;
  • создание словаря T9.

Хэш-таблица

Хэширование используется в целях уникальной идентификации и сохранения объектов по вычисленному индексу, который называют «ключом». В результате объект хранится в формате «ключ-значение», а коллекция этих объектов представляет собой «словарь». Поиск объекта осуществляется по его ключу. Есть разные структуры данных, которые построены по принципам хэширования, к примеру, широко известна хэш-таблица (обычно ее реализуют посредством массивов).
От чего зависит производительность хэширующей структуры:

  • от хэш-функции;
  • от размера хэш-таблицы;
  • от метода обработки коллизий.

Что могут спросить:

  • поиск симметричных пар;
  • отслеживание полной траектории пути;
  • поиск, является ли массив подмножеством другого массива;
  • проверка, можно ли назвать массивы непересекающимися.

Надеемся, этот перевод был вам полезен, и теперь вы имеете единое понимание основных структур данных, которые должен знать каждый разработчик. Мы уверены, что предоставленная информация обязательно поможет на собеседовании по программированию. Успехов!