Структуры данных, которые надо знать OTUS
2026-03-10 01:09 Diff
https://otus.ru/journal/struktury-dannyh-kotorye-nado-znat/screenshot_1-5-2/

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

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

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

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

— фактические данные, которые хранятся;

— ссылку-указатель на следующий в последовательности узел.

Также выделяют дважды связанные списки, где каждый узел имеет указатель как на следующий элемент в списке, так и на предыдущий.

Основные операции:

  • добавление элемента;
  • удаление элемента;
  • поиск в списке.

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

Особенности массива:

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

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

Массив a имеет только одну строку и размер 16 ячеек. Доступ к элементу осуществляется по индексу, причем максимальный индекс равняется 15, так как нумерация начинается с нуля.

Бывают массивы с двумя измерениями (двухмерные), тремя (трехмерные) и т. п., то есть они могут быть n-мерными. Двумерный массив уже можно назвать матрицей. Доступ к элементу такой матрицы уже будет осуществляться по i-й строке и j-м столбце — a[i][j].

Кратко о том, зачем вообще нужны массивы:

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

На практике в программировании чаще используют в качестве структур данных одномерные и двумерные массивы.

Стеки

Стек напоминает стопку, содержащую книги или учебники: если нужна книга из середины, надо сначала взять те книги, которые находятся сверху. То есть это структура данных, при работе с которой можно вставлять либо удалять элементы только в начале. Последний добавленный элемент является первым, который из этого стека выходит (Last In First Out — LIFO), то есть компоненты добавляются и удаляются лишь с одного конца — так называемой вершины стека.

Очереди

Просто вспоминаем очередь в продуктовом гипермаркете. Тот, кто стоит первым, первым и обслуживается.

Но эта структура данных, в отличие от предыдущей, организована по принципу First In First Out (FIFO). Элементы добавляются с одного конца (enqueue), а удаляются с противоположного (dequeue). Кто первый пришел, первый и уйдет (будет «обслужен на кассе»).

Множества

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

Map

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

Можно добавлять/удалять пары из коллекции, менять уже существующие пары, искать значения, связанные с конкретным ключом.

Хэш-таблицы

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

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

Дерево (древо) представляет собой структуру данных, состоящих из узлов, причем:

  1. У каждого дерева есть корневой узел (расположен сверху).
  2. У каждого корневого узла есть 0 и более дочерних узлов.
  3. У каждого дочернего тоже есть 0 и более дочерних узлов и так далее.

Двоичное дерево обладает двумя дополнительными свойствами:

  1. У каждого узла — до 2 потомков (детей).
  2. Для каждого узла значения левых потомков меньше значения текущего узла и меньше значения правых потомков.

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

Префиксное дерево

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

Каждый узел — это одна буква слова. Чтобы записать слово, надо следовать ветвям. На картинке выше содержатся следующие слова:

Двоичная куча

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


Графы

Это совокупности узлов, называющимися вершинами, и ребер (связей между этими вершинами). Еще графы называют сетями. Понять суть можно, вспомнив социальную сеть в интернете. Вершины — это люди, ребра — дружеские связи между людьми.


Графы бывают:

— ориентированными (с направлением);

— неориентированными (без какого-нибудь направления на ребрах между вершинами).

Частные способы представления графа — матрица смежности и список смежности.

Источник: https://www.freecodecamp.org/news/10-common-data-structures-explained-with-videos-exercises-aaff6c06fb2b/.

Нашли ошибку во время чтения материала? Пишите комментарий!