Data Structures

Структура данных – это контейнер, который хранит информацию в определенном виде.

Из-за такой «компоновки» она может быть эффективной в одних операциях и неэффективной в других.

Цель разработчика – выбрать из существующих структур оптимальный для конкретной задачи вариант.

Массив (Array)

Стек (Stack)

Очередь (Queue)

Связный список (Linked List)

Дерево (Tree)

Граф (Graph)

Префиксное дерево (Trie)

Хэш-Таблица (Hash Table)

Массив – это самая простая и наиболее широко используемая из структур.

Стеки и очереди являются производными от массивов.

Одномерные массивы.

Многомерные массивы (массивы элементами которых являются массивы).

insert – вставка.

get – получение элемента.

delete – удаление.

size – получение общего количества элементов в массиве.

Пример стека из реальной жизни – куча книг, лежащих друг на друге.

Чтобы получить книгу, которая находится где-то в середине

вам нужно удалить все, что лежит сверху.

Так работает метод LIFO (Last In First Out, последним пришел – первым ушел).

push – вставка элемента наверх стека.

pop – получение верхнего элемента и его удаление.

isEmpty – возвращает true, если стек пуст.

top – получение верхнего элемента без удаления.

Как и стек, очередь – это линейная структура данных

которая хранит элементы последовательно.

Единственное существенное различие заключается в том, что вместо использования метода LIFO, очередь реализует метод FIFO

FIFO (First in First Out, первым пришел – первым ушел).

enqueue – вставка в конец.

dequeue – удаление из начала.

isEmpty – возвращает true, если очередь пуста.

top – получение первого элемента.

Линейная структура данных

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

но отличается:

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

Также есть указатель на первый элемент – head.

Если список пуст, то он указывает на null.

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

Однонаправленный

Двунаправленный

insertAtEnd – вставка в конец.

insertAtHead – вставка в начало.

delete – удаление указанного элемента.

deleteAtHead – удаление первого элемента.

search – получение указанного элемента.

isEmpty – возвращает true, если связный список пуст.

Граф представляет собой набор узлов, соединенных друг с другом в виде сети.

Узлы также называются вершинами.

Пара (x, y) называется ребром, которое указывает, что вершина x соединена с вершиной y.

Ребро может содержать вес/стоимость, показывая, сколько затрат требуется, чтобы пройти от x до y.

Неориентированный

Ориентированный

Матрица смежности

Список смежности

В ширину

В глубину

Дерево – это иерархическая структура данных, состоящая из вершин (узлов) и ребер, соединяющих их.

Они похожи на графы, но есть одно важное отличие: в дереве не может быть цикла.

N-арное дерево;

сбалансированное дерево;

бинарное дерево;

бинарное дерево поиска;

дерево AVL;

красно-чёрное дерево;

2-3 дерево.

Префиксные деревья (tries) – древовидные структуры данных, эффективные для решения задач со строками.

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

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

Итак, объект хранится в виде пары ключ-значение, а коллекция таких элементов называется словарем.

Каждый объект можно найти с помощью его ключа.

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

функция хеширования

размер хеш-таблицы

метод обработки коллизий