Что такое структура данных

Представьте приложение, в котором хранятся миллионы записей.

Одной программе нужно постоянно находить запись по имени. Другой – обрабатывать задачи строго в порядке поступления. Третьей – хранить папки и файлы внутри других папок.

Во всех случаях программа работает с данными. Но просто сохранить данные недостаточно: нужно ещё решить, как их организовать, чтобы нужные операции было удобно выполнять.

Способ организации данных и работы с ними называется структурой данных.

Возьмём несколько чисел:

Мы можем расположить их последовательно:

Так числа лежат в массиве. Но те же значения можно представить иначе – связать каждое со следующим:

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

Можно организовать эти числа и в виде дерева:

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

Вернёмся к последовательности:

Если нам нужен элемент с индексом 3, мы можем обратиться к нему напрямую:

и получить:

Для массива такая операция естественна: каждый элемент имеет свою позицию.

Теперь рассмотрим связный список. У его элементов тоже есть порядок, но прямого доступа по индексу здесь уже нет. Чтобы добраться до 9, нужно начать с первого элемента и последовательно пройти по связям:

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

Массив удобен, когда нужно быстро обратиться к элементу по индексу: numbers[3]. Но теперь рассмотрим другую операцию – добавление нового элемента в начало.

Есть массив [4, 7, 9, 12], и нужно добавить 2 перед первым элементом. Просто поставить 2 перед 4 не получится: сначала нужно освободить место. Для этого все существующие элементы приходится сдвинуть на одну позицию вправо:

Если в массиве n элементов, при вставке в начало может потребоваться сдвинуть все n элементов.

Теперь посмотрим на связный список 4 → 7 → 9 → 12. У списка есть ссылка на первый элемент – head. Чтобы добавить 2 в начало, проходить по остальным элементам не нужно:

В массиве число сдвигов зависит от количества элементов. В связном списке всё проще: создаём новый узел, связываем его с текущим первым узлом и делаем новым head.

Это не значит, что связный список «лучше» массива: получить элемент по индексу он не может – до него нужно идти по связям. Одна структура удобнее для одной операции, другая – для другой.

Было бы удобно найти одну структуру данных и использовать её всегда. Но такой структуры нет:

Поэтому вопрос обычно звучит не «какая структура данных самая быстрая?», а «какие операции важны именно в этой задаче?»

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

Выбор зависит от задачи.

Когда мы видим массив, дерево или связный список, легко подумать, что разница только в том, как они нарисованы. Но структура данных определяет гораздо больше. Она задаёт:

Например, у стека есть операции:

У очереди:

А в структуре, которая хранит значения по ключам, можно обращаться к данным так:

То есть структура данных определяет не только способ хранения, но и способ взаимодействия с данными.

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

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

Последнее добавленное действие обрабатывается первым – именно такое поведение предоставляет стек.

Теперь другой пример. В программу поступают задачи: A, затем B, затем C. Если их нужно выполнять в том же порядке, сначала должна обработаться A, затем B, затем C:

В обоих примерах мы храним последовательность элементов. Но нужный порядок обработки отличается. Поэтому отличаются и структуры данных.

Возьмём несколько совершенно разных требований.

Нужно быстро получать элемент по его позиции – для этого хорошо подходит массив. Нужно, чтобы последнее добавленное значение извлекалось первым, – так ведёт себя стек. Нужно обрабатывать элементы в порядке поступления – так работает очередь.

Нужно находить значение по уникальному ключу – для этого часто используют хеш-таблицу. Нужно представить отношения «родитель – потомок» – подходит дерево. А если объекты могут быть связаны друг с другом произвольным образом, появляется граф.

Алгоритм описывает способ решения задачи. Но он всегда работает с какими-то данными, и то, как эти данные организованы, может сильно влиять на само решение.

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

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

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

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

Пока вам не нужно запоминать, какая структура для какой задачи используется. Важнее научиться задавать правильные вопросы:

Ответы на такие вопросы постепенно приводят к выбору подходящей структуры данных.