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

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

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

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

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

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

Линейная структура данных имеет элементы данных, расположенные последовательно, и каждый элемент-член связан со своим предыдущим и следующим элементом. Обход структуры данных или повторение структуры данных, что означает «посещение» или «прикосновение» к каждому элементу структуры, является последовательным. Эти структуры данных легко реализовать, поскольку компьютерная память также является последовательной. Примерами линейных структур данных являются массивы, связанные списки, стек и очередь.

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

Давайте кратко рассмотрим различные структуры данных:

Массив

  • Массив — это простейший тип структуры данных, который содержит элементы одного и того же типа данных (целое число, число с плавающей запятой, строка и т. д.).
  • Это линейный тип данных
  • Данные, хранящиеся в каждой позиции массива, получают положительное значение, называемое индексом.
  • Значение индекса начинается с 0 для первого элемента массива.

Скажем, у нас есть цены на 6 элементов продуктов и их положение в индексе. Мы можем хранить все целые числа в массиве.

Этот массив можно записать так:

константа обр = [10, 5, 23, 8, 12, 7]

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

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

Основные свойства структуры данных связанного списка:
- size: количество элементов в связанном списке
- head: первый элемент в связанном списке
- tail: последний элемент в связанном списке

  • Первый узел (содержащий 2) называется головным узлом, потому что на него не указывает ни один узел.
  • Узел 2 хранит адрес узла, содержащего 4, и так далее.
  • Хвостовой узел указывает на ноль, что указывает на конец списка.

Некоторые практические применения связанного списка включают:

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

Если вы хотите больше узнать о связанных списках, ознакомьтесь с этими замечательными ресурсами:

NoobCoder — Связанный список в JavaScript для начинающих
Beiatrix — Связанные списки | Структуры данных в JavaScript

Хеш-таблица

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

Если вам нужна дополнительная информация о хеш-таблицах. Ресурс ниже погружается глубже в тему:

ComputerScience — хеш-таблицы и хеш-функции

Стек

  • Стек — это структура данных, которая помогает упорядочивать данные в определенном порядке и следует принципу «последний пришел — первый ушел» (LIFO). Это означает, что последний элемент, вставленный в стек, удаляется первым.
  • Думайте о стопке как о куче книг, где вы можете взять только верхний элемент из стопки, чтобы удалить из нее книги, и вы можете добавить новую книгу только наверху. Этот тип доступа к данным называется «последним пришел — первым вышел».

Очередь

  • Линейная структура данных, которая следует принципу «первым поступил — первым обслужен» (FIFO). Элемент, вставленный первым, удаляется первым.
  • Типичными примерами очереди являются очереди людей, ожидающих услуги или получения чего-либо. Первый человек в очереди обслуживается первым, а последний в очереди обслуживается последним.

График

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

  • На приведенной выше диаграмме:
    Вершины = {A, B, C, D, E}
    Ребра = {AB, BE, ED, DC, CA, AD, BD}

Дерево

  • Нелинейная иерархическая структура данных, состоящая из узлов, соединенных ребрами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел.
  • Примеры иерархической организации — генеалогическое древо, в HTML — объектная модель документа (DOM) работает как дерево.

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