Наиболее популярные структуры данных. Основы Javascript

Текст рассчитан на людей, которые понимают, что такое цикл, массив и прочие базовые вещи любого распространенного языка программирования.

Итак, что же такое структуры данных?

Структура данных — это определенный формат хранения, который упрощает обработку данных.

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

Итак, рассмотрим самую базовую из структур данных — список.

Список (list) — набор однотипных (не всегда) данных, следующих друг за другом по цепочке. Для начала рассмотрим одно- и двунаправленные списки.

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

В случае начала списка ссылка на элемент, предшествующий первому, = указывается как нулевая (null). С последним элементом всё наоборот — указатель на следующий элемент указывается как null.

Таким образом, независимо от того, сколько элементов в списке, их всегда можно по очереди обойти.

Javascript data structure 1

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

Стек (stack) — разновидность списка, в котором операции доступа к данным определены как FILO (First-In-Last-Out).

То есть стек это такой список, в который мы можем добавить элемент, либо извлечь его. Представьте, как вы выбираете в библиотеке книги: вы находите на полках книгу 1, кладете ее в руки, далее находите книгу 2, и кладете на книгу 1, далее книга 3 и т. д. После этого, поставив стопку книг на стол, вы начинаете смотреть книгу, которую взяли последней, потом предпоследней и т. д., пока не дойдёте до первой книги.

Очередь (queue) — разновидность списка, в котором операции доступа к данным определены как FIFO (First-In-First-Out). Представьте себя на кассе в магазине: вы подошли к кассе, а там уже стоят 3 человека. Вы становитесь 4-ым, и до того, как «элементы очереди» перед вами не извлекутся из очереди, вас не обслужат.

 

Перейдём к теории графов.

Граф (graph) — это структура данных, которая состоит из вершин и ребер (связи между вершинами). Графически отображается как набор точек, которые соединены линиями.

Графы используются не только для хранения данных, но и для указания зависимости между ними.

Вершины графа обозначаются как v1, v2, v3,…, а рёбра обозначаются как пары индексов смежных (то есть соседних) вершин (1,2), (2,3) и т. д. Если существуют рёбра, которые связывают одну и ту же вершину, то они называются петлями.

Графы бывают ориентированными и неориентированными. В ориентированных графах у рёбер есть направление.

Javascript data structure 2

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

Таблица смежности представляет из себя матрицу NxN, где N — количество вершин в графе. Таблица заполняется с учётом того, ориентированный граф или нет.

В неориентированном графе на пересечении i-ого столбца и j-ой строки ставится 1, если существует ребро, и 0 — если его нет. Для ориентированного графа ставится 1, если ребро направлено от i-ой вершины к j-ой, и -1 – если наоборот.

Таблица инцидентности представляет из себя матрицу NxM, где N — количество вершин, а M — количество рёбер. Заполняется таблица так же, как и таблица смежности (условие направленности сохраняется), но с учётом того, принадлежит j-ое ребро i-ому или нет.

Такие способы представления слишком избыточны для неплотных графов (то есть таких, где связей между вершинами мало). Более оптимизированным по затратам памяти является список смежности.

Список смежности является «списком списков», где в списке для каждой вершины создаётся список вершин, с которыми смежна исходная вершина. Соответственно, длиной такого списка является сумма количества вершин и ребер.

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

Граф называется связным, если в нём нет вершин, которые не соединены ни с какой другой.

Маршрут — это список рёбер, которые соединяют 2 различные вершины. Маршрут называется циклом, если начальная вершина совпадает с конечной.

Эйлеров цикл — это цикл, в котором каждое ребро используется ровно один раз.

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

Если граф связный и ацикличный (то есть отсутствуют циклы), то он называется деревом.

Дерево — один из распространённых типов графов. С помощью такой структуры можно отобразить, например, категории каталога в интернет-магазине. Представляется дерево в виде «списка списков»: изначально в список помещается одна вершина, называемая корнем, в которой содержится список её потомков, в каждом из которого может содержаться список из потомков, и т. д. Если у вершины нет потомков, то она называется листом.

Javascript data structure 3

Одна из интересных вариаций дерева — бинарное дерево поиска.

Для его создания должны соблюдаться 3 условия:

  • Оба поддерева должны быть бинарными деревьями
  • Все ключи левого поддерева должны быть меньше ключа корня
  • Все ключи правого поддерева должны быть больше либо равны ключу корня

Javascript data structure 4

Допустим, нам нужно найти элемент с ключом 4. Начиная от корня, обходим вершины и проверяем на то, меньше, больше либо равно текущее значение значению ключа. В данном примере для поиска 4 мы пройдём по вершинам 8 → 3 → 6 → 4.

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

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

Конечно же, это не все, что нужно знать о структурах данных, но описать всё за раз не представляется возможным. Поэтому продолжайте изучать эту тему и стремиться к совершенству!

 

Поделиться

Последние статьи

8 способов применения Интернета вещей в производстве

BLAKIT признана лидирующей компанией по мобильной и веб-разработке

Штатный дизайнер vs дизайн-студия: Почему мы выбрали второе и что лучше для клиента

Как мы запустили социальную сеть для создания, поиска и посещения мероприятий

Как проходит тестирование программного обеспечения в нашей компании

BLAKIT выступила партнером студенческой IT Олимпиады Bit-Cup 2018!

Как IoT-проект Neurosonic привлек клиентов из США, Европы, Азии, Великобритании на Orgatec

Как мы создали IoT-решение для управления продуктами & релаксации

Решения IoT в здравоохранении. Интернет медицинских вещей

8 технологических решений для поставщиков медицинских услуг