Главная

А вы точно знаете все структуры данных?

Список наиболее распространенных структур данных.

Поделиться:
 

4+

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

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

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

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

Давайте всё же рассмотрим некоторые из наиболее важных структур данных, которые помогут вам принимать эффективные решения!

Массив

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

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

Основные операции с массивами
Get: получить элемент массива по заданному индексу.
Insert: вставить элемент массива по указанному индексу.
Length: получить количество элементов в заданном массиве.
Delete: удалить элемент массива по заданному индексу. Это можно сделать либо сделав значение элемента неопределенным, либо скопировав элементы массива, исключая удаляемый элемент, в новый массив.
Update: обновить значение элемента массива по заданному индексу.
Traverse: проход по массиву для выполнения функций с элементами массива.
Search: поиск определенного элемента в заданном массиве с помощью выбранного алгоритма поиска.

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

Image for post
Image for post

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

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

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

Основные операции со связным списком:
Insertion: добавление нового узла в список. Новый узел можно вставить в начало, конец или в где-то между другими элементами связного списка.
Delete: удаление узла в начале/конце списка или на основе заданного ключа.
Display: отображение данных, которые хранятся в связном списке.
Search: поиск узла в связном списке.
Update: обновление значение узла по заданному ключу.

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

Стек

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

Image for post

Основные операции со стеком
Push: вставить элемент в верхнюю часть стека
Pop: удалить элемент из верхней части стека и вернуть его.
Peek: просмотр элемента в верхней части стека.
isEmpty: проверяет, пуст ли стек

Где используется?
1. в истории навигации браузера.
2. для реализации рекурсии.
3. при распределении памяти на основе стека.

Image for post

Очередь

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

Image for post

Основные операции с очередью
Enqueue: вставить элемент в конец очереди.
Dequeue: удалить элемент из начала очереди.
Top / Peek: возвращает элемент из начала очереди без удаления.
isEmpty: проверяет, пуста ли очередь.

Где используется?
1. Обслуживание нескольких запросов на сервере.
2. Управление потоками в многопоточных средах.
3. Балансировка нагрузки.

Image for post

Граф

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

Основные термины:
Размер (size): количество ребер в графе.
Порядок (order): количество вершин в графе.
Смежность (adjacency): когда два узла соединены одним ребром.
Петля (self-looped): вершина, соединенная с собой ребром.
Изолированный (isolated): вершина, которая не связана ни с какой другой вершиной.


Есть два типа графов. Графы различаются в основном направлением пути между двумя вершинами.
Направленные графы: графы, в которых все ребра имеют направления, указывающие на начальную и конечную точку (вершину).
Ненаправленные графы: графы, в которых ребра не имеют направлений, позволяющих делать обход в любом направлении.

Часто используемые алгоритмы обхода графа:
Поиск в ширину (BFS): метод для поиска кратчайшего пути в графе, основанный на вершинах.
Поиск в глубину (DFS): метод, основанный на ребрах.

Основные операции с графом
Добавить вершину: добавление вершины в граф
Добавить ребро: добавление ребра между двумя вершинами.
Отображение: отображение вершины
Общая стоимость обхода: нахождение общей стоимости пути.

Где используется?
1. для представления потока вычислений.
2. при распределении ресурсов операционной системой.
3. реализация алгоритмов подбора друзей(Facebook).
4. расчет кратчайшего пути между двумя точками (Google Maps).

Image for post

Дерево

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

Image for post

Есть несколько видов деревьев:
1. N-арное дерево
2. Сбалансированное дерево
3. Двоичное дерево
4. Дерево двоичного поиска (BST)
5. AVL Tree
6. Красно-Черное Дерево
7. 2–3 Дерево

BST — это особый вид двоичных деревьев. Эти деревья являются наиболее часто используемыми.

Image for post

Операции с BST
Insert: вставить элемент в дерево.
Search: поиск элемента в дереве.
PreorderTraversal: обход дерева в порядке предварительного заказа.
InorderTraversal: обход дерева по порядку.
PostorderTraversal: обход дерева в режиме пост-заказа.

Где используется BST?
1. Репрезентация какой-либо организации
2. Представление компьютерной файловой системы
3. Представление химической формулы
4. В деревьях решений
5. JVM (виртуальная машина Java) для хранения объектов Java

Хеш-таблица

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

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

h (k) = k% m
h: функция хеширования
k: ключ, хеш-значение которого должно быть определено
m: размер хеш-таблицы.

Например, рассмотрите возможность использования хеш-функции k% 17. Если исходный ключ равен 20, хешированный ключ будет 20% 17 = 3. Это означает, что значение будет сохранено в индексе 3 нашей хеш-таблицы.

Image for post

Зачем нужно хэширование?
У некоторых возникает вопрос, зачем проходить этот дополнительный процесс хеширования, если мы можем просто сопоставить значения напрямую с ключом. Хотя прямое сопоставление звучит просто, но оно может стать неэффективным решением при использовании больших сетов данных. С помощью хеширования мы можем достичь сложности в O(1).
Коллизии
Поскольку для преобразования всех ключей используется общая хеш-функция, возможны конфликты. Давайте посмотрим на приведенный ниже пример с нашей хэш-функцией k% 17.

Когда k = 18, h (18) = 18% 17 = 1.
Когда k = 20, h (20) = 20% 17 = 3.
Когда k = 35, h (35) = 35% 17 = 1.

Из примера видно, что при ключах 18 и 35, происходит конфликт, так как оба ключа имеют индекс 1. Коллизии можно разрешить с помощью раздельного связывания и открытой адресации.

Основные операции с хеш-таблицей:
Search: поиск элемента в хеш-таблице.
Insert: вставка элемент в хеш-таблицу.
Delete: удаление элемента из хеш-таблицы

Где используется?
1. при индексировании базы данных
2. в средствах проверки правописания
3. при реализации структуры данных Set
4. кэш

Заключение

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

4+