main

7 структур данных JavaScript, которые вы должны знать

Наши соц. сети: instagram, fb, tg

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

Возможно, ты только начинаешь изучение структуры данных, или, может быть, ты кодишь уже 100 лет и просто нуждаешься в апдейте. Сегодня мы расскажем тебе о 7 лучших структурах данных, которые должен знать любой разработчик JS.

Вот что мы расскажем сегодня

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

Топ 7 структур данных JS

Вопросы интервью структур данных

Ресурсы

Погнали!

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

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

Структуры данных позволяют нам:

Управлять и использовать большие наборы данных

Заниматься поиском конкретных данных из базы данных

Разрабатывать алгоритмы, адаптированных к конкретным программам

Обрабатывать несколько запросов от пользователей одновременно

Упрощать и ускорять обработку данных

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

JavaScript имеет примитивные и не примитивные структуры данных. Примитивные структуры данных и типы данных являются встроенными для языка программирования. К ним относятся boolean, null, number, string и т. д. Не примитивные структуры данных определяются не языком программирования, а программистом. К ним относятся линейные структуры данных, статические структуры данных и динамические структуры данных, такие как очереди и связанные списки.

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

7 структур данных JavaScript, которые вы должны знать

Массив

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

1

Преимущества

• Прост в создании и использовании

• Основополагающий строительный блок для сложных структур данных

Недостатки

• Фиксированный размер

• Дорого для вставки / удаления или повторной последовательности значений

• Неэффективен в сортировке

Приложения

• Основные таблицы

• В сложных структурах, таких как хеш-таблицы

Очереди

Очереди концептуально похожи на стеки; оба являются последовательными структурами, но очереди обрабатывают элементы в порядке их ввода, а не самый последний элемент. В результате очереди можно рассматривать стеки FIFO (First In, First Out). Они полезны в качестве буфера для запросов, сохраняя каждый запрос в том порядке, в котором он был получен, до его обработки.

2

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

Преимущества

• Динамический размер

• Данные о заказах в порядке их получения

• Низкое время выполнения

Недостатки

• Можно получить только самый старый элемент

Приложения

• Эффективен в качестве буфера при получении частых данных

• Удобный способ хранения чувствительных к заказу данных, таких как сохраненные голосовые сообщения

• Гарантирует, что самые старые данные обрабатываются первыми

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

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

3

Преимущества

• Эффективная вставка и удаление новых элементов

• Менее сложный, чем реструктуризация массива

Недостатки

• Использует больше памяти, чем массивы

• Неэффективное получение определенного элемента

• Неэффективное обхождение списка в обратном направлении

Приложения

• Лучше всего использовать, когда данные должны быть добавлены и удалены в быстрой последовательности из неизвестных мест

Деревья

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

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

Узлы со связанными дочерними узлами называются внутренними узлами, а узлы без дочерних узлов являются внешними узлами. Распространенным типом дерева является «двоичное дерево поиска», которое используется для простого поиска хранимых данных. Эти поисковые операции очень эффективны, так как их длительность поиска зависит не от количества узлов, а от количества уровней вниз по дереву.

4

Этот тип дерева определяется четырьмя строгими правилами:

Левое поддерево содержит только узлы с элементами, меньшими, чем корень.

Правое поддерево содержит только узлы с элементами больше, чем корень.

Левое и правое поддеревья также должны быть двоичным деревом поиска. Они должны следовать вышеуказанным правилам с «корнем» своего дерева.

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

Преимущества

• Идеально подходит для хранения иерархических отношений

• Динамический размер

• Быстрая вставка и удаление

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

• Двоичные деревья поиска эффективны при поиске; длина только O (высота).

Недостатки

• Медленно переставлять узлы

• Дочерние узлы не содержат информации об их родительском узле

• Деревья бинарного поиска работают не так быстро, как более сложная хеш-таблица

• Деревья бинарного поиска могут вырождаться в линейный поиск (сканирование всех элементов), если не реализованы со сбалансированными поддеревьями.

Приложения

• Хранение иерархических данных, таких как местоположение файла.

• Двоичные деревья поиска отлично подходят для задач, требующих поиска или упорядочения данных.

Графы

Графы - это структура данных на основе отношений, полезная для хранения веб-подобных отношений. Каждый узел или вершина, как их называют в графах, имеет заголовок (A, B, C и т. д.), Значение, содержащееся в нем, и список связей (называемых ребрами), которые он имеет с другими вершинами.

5

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


V = {a, b, c, d}

E = {ab, ac, bc, cd}


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

Преимущества

• Может быстро передавать визуальные эффекты над текстом

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

Недостатки

• На более высоком уровне текст может занять много времени для преобразования в изображение.

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

Приложения

• Сетевые представительства

• Моделирование социальных сетей, таких как Facebook.

Хеш-таблицы (Карта)

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

6

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

Преимущества

• Ключ может быть в любой форме, а индексы массива должны быть целыми числами

• Высокоэффективная функция поиска

• Постоянное количество операций для каждого поиска

• Постоянные затраты на операции вставки или удаления

Недостатки

• Столкновения: ошибка, возникающая, когда два ключа преобразуются в один и тот же хэш-код или два хеш-кода указывают на одно и то же значение.

• Эти ошибки могут быть общими и часто требуют пересмотра хэш-функции.

Приложения

• Хранение базы данных

• Поиск адресов по имени

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