10 структур данных, которые вы должны знать (+видео и задания)
Бо Карнс – разработчик и преподаватель расскажет о наиболее часто используемых и общих структурах данных. Специально для вас мы перевели его статью.
«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях ». — Линус Торвальдс, создатель Linux
Структуры данных являются важной частью разработки программного обеспечения и одной из наиболее распространенных тем для вопросов на собеседованиях с разработчиками.
Хорошая новость в том, что они в основном являются просто специализированными форматами для организации и хранения данных.
Из этой статьи вы узнаете о 10 наиболее распространенных структурах данных. Также сюда добавлены видеоролики (на английском языке) по каждой из структур, и код их реализации на JS. А чтобы вы немного попрактиковались, я добавил сюда задачи из бесплатной учебной программы freeCodeCamp.
Обратите внимание, что некоторые из этих структур данных включают временную сложность в нотации Big O. Это не относится ко всем из них, поскольку временная сложность иногда основана на реализации. Если вы хотите узнать больше о нотации Big O, посмотрите видео от Briana Marie .
Тем не менее, знание того, как реализовать эти структуры данных, даст вам огромное преимущество в поиске работы и может пригодиться, когда вы попытаетесь написать высокопроизводительный код.
Связный список является одной из самых основных структур данных. Его часто сравнивают с массивом, поскольку многие другие структуры данных могут быть реализованы либо с помощью массива, либо с помощью связного списка. У каждого из них есть свои преимущества и недостатки.
Связный список состоит из группы узлов, которые вместе представляют последовательность. Каждый узел содержит две вещи: фактические данные, которые хранятся (которые могут быть представлены любым типом данных), и указатель (или ссылка) на следующий узел в последовательности. Существуют также дважды связанные списки, в которых каждый узел имеет указатель и на следующий, и на предыдущий элемент в списке.
Самые основные операции в связанном списке включают добавление элемента в список, удаление элемента из списка и поиск в списке для элемента.
Реализация на JavaScript
Временная сложность связного списка ╔═══════════╦═════════╦══════════════╗ ║ Алгоритм ║В среднем║Худший случай ║ ╠═══════════╬═════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════╩══════════════╝
Задания с freeCodeCamp:
Стек — это базовая структура данных, в которой вы можете только вставлять или удалять элементы в начале стека. Он напоминает стопку книг. Если вы хотите взглянуть на книгу в середине стека, вы сначала должны взять книги, лежащие сверху.
Стек считается LIFO (Last In First Out) — это означает, что последний элемент, который добавлен в стек, — это первый элемент, который из него выходит.
Существует три основных операции, которые могут выполняться в стеках: вставка элемента в стек (называемый «push»), удаление элемента из стека (называемое «pop») и отображение содержимого стека (иногда называемого «pip»).
Реализация на JavaScript
Временная сложность стека ╔═══════════╦═════════╦══════════════╗ ║ Алгоритм ║В среднем║Худший случай ║ ╠═══════════╬═════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════╩══════════════╝
Задания с freeCodeCamp:
Вы можете думать об этой структуре, как об очереди людей в продуктовом магазине. Стоящий первым будет обслужен первым. Также как очередь.
Если рассматривать очередь с точки доступа к данным, то она является FIFO (First In First Out). Это означает, что после добавления нового элемента все элементы, которые были добавлены до этого, должны быть удалены до того, как новый элемент будет удален.
В очереди есть только две основные операции: enqueue и dequeue. Enqueue означает вставить элемент в конец очереди, а dequeue означает удаление переднего элемента.
Реализация на JavaScript
Временная сложность очереди ╔═══════════╦═════════╦══════════════╗ ║ Алгоритм ║В среднем║Худший случай ║ ╠═══════════╬═════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════╩══════════════╝
Задания с freeCodeCamp:
Множества хранят данные без определенного порядка и без повторяющихся значений. Помимо возможности добавления и удаления элементов, есть несколько других важных функций, которые работают с двумя наборами одновременно.
- Union (Объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор (без дубликатов).
- Intersection (Пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.
- Difference (Разница). Вернет список элементов, которые находятся в одном множестве, но НЕ повторяются в другом.
- Subset(Подмножество) — возвращает булево значение, показывающее, содержит ли одно множество все элементы другого множества.
Реализация на JavaScript
Задания с freeCodeCamp:
Map — это структура данных, которая хранит данные в парах ключ / значение, где каждый ключ уникален. Map иногда называется ассоциативным массивом или словарем. Она часто используется для быстрого поиска данных. Map’ы позволяют сделать следующее:
- Добавление пары в коллекцию
- Удаление пары из коллекции
- Изменение существующей пары
- Поиск значения, связанного с определенным ключом
Реализация на JavaScript
Задания с freeCodeCamp:
Хэш-таблица — это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.
Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше.
Реализация на JavaScript
Временная сложность хэш-таблицы ╔═══════════╦═════════╦═══════════════╗ ║ Алгоритм ║В среднем║Худший случай ║ ╠═══════════╬═════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(1) ║ O(n) ║ ║ Insert ║ O(1) ║ O(n) ║ ║ Delete ║ O(1) ║ O(n) ║ ╚═══════════╩═════════╩═══════════════╝
Задания с freeCodeCamp:
Дерево — это структура данных, состоящая из узлов. Она имеет следующие характеристики:
- Каждое дерево имеет корневой узел (вверху).
- Корневой узел имеет ноль или более дочерних узлов.
- Каждый дочерний узел имеет ноль или более дочерних узлов и т. д.
Двоичное дерево поиска имеет + две характеристики:
- Каждый узел имеет до двух детей(потомков).
- Для каждого узла его левые потомки меньше текущего узла, что меньше, чем у правых потомков.
Двоичные деревья поиска позволяют быстро находить, добавлять и удалять элементы. Способ их настройки означает, что в среднем каждое сравнение позволяет операциям пропускать половину дерева, так что каждый поиск, вставка или удаление занимает время, пропорциональное логарифму количества элементов, хранящихся в дереве.
Реализация на JavaScript
Временная сложность двоичного поиска ╔═══════════╦══════════╦══════════════╗ ║ Алгоритм ║В среднем ║Худший случай ║ ╠═══════════╬══════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Delete ║ O(log n) ║ O(n) ║ ╚═══════════╩══════════╩══════════════╝
Задания с freeCodeCamp:
Бор, луч или дерево префикса — это своего рода дерево поиска. Оно хранит данные в шагах, каждый из которых является его узлом. Префиксное дерево из-за быстрого поиска и функции автоматического дописания часто используют для хранения слов.
Каждый узел в префиксном дереве содержит одну букву слова. Вы следуете ветвям дерева, чтобы записать слово, по одной букве за раз. Шаги начинают расходиться, когда порядок букв отличается от других слов в дереве или, когда заканчивается слово. Каждый узел содержит букву (данные) и логическое значение, указывающее, является ли узел последним узлом в слове.
Реализация на JavaScript
Задания с freeCodeCamp:
Двоичная куча — это очередное дерево, в каждом узле которого не более двух детей. Кроме того, это полное дерево. Это означает, что все уровни полностью заполнены до последнего уровня, а последний уровень заполняется слева направо.
Двоичная куча может быть либо минимальной, либо максимальной. В максимальной -ключи родительских узлов всегда больше или равны тем, что у детей. В минимальной -ключи родительских узлов меньше или равны ключам дочерних элементов.
Реализация на JavaScript
Временная сложность двоичной кучи ╔═══════════╦══════════╦═══════════════╗ ║ Алгоритм ║В среднем ║ Худший случай ║ ╠═══════════╬══════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(log n) ║ ║ Delete ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═══════════╩══════════╩═══════════════╝
Задания с freeCodeCamp:
Графы представляют собой совокупности узлов (также называемых вершинами) и связей (называемых ребрами) между ними. Графы также известны как сети.
Одним из примеров графов является социальная сеть. Узлы — это люди, а ребра — дружба.
Существует два основных типа графов: ориентированные и неориентированные. Второй тип — это графы без какого-либо направления на ребрах между узлами. Ориентированные графы, напротив, представляют собой графы с направлением на них.
Два частых способа представления графа — это список смежности и матрица смежности.
Список смежности может быть представлен как список, где левая сторона является узлом, а правая — списком всех других узлов, с которыми он соединен.
Матрица смежности представляет собой таблицу чисел, где каждая строка или столбец представляет собой другой узел на графе. На пересечении строки и столбца есть число, которое указывает на отношение. Нули означают, что нет ребер или отношений. Единицы означают, что есть отношения. Числа выше единицы могут использоваться для отображения разных весов.
Алгоритмы обхода — это алгоритмы для перемещения или посещения узлов в графе. Основными типами алгоритмов обхода являются поиск в ширину и поиск в глубину. Одно из применений заключается в определении того, насколько близко узлы расположены по отношению к корневому узлу. Посмотрите, как реализовать поиск по ширине в JavaScript в приведенном ниже видео.
Реализация на JavaScript
Временная сложность списка смежности (граф) ╔═══════════════╦════════════╗ ║ Алгоритм ║ Время ║ ╠═══════════════╬════════════╣ ║ Storage ║ O(|V|+|E|) ║ ║ Add Vertex ║ O(1) ║ ║ Add Edge ║ O(1) ║ ║ Remove Vertex ║ O(|V|+|E|) ║ ║ Remove Edge ║ O(|E|) ║ ║ Query ║ O(|V|) ║ ╚═══════════════╩════════════╝
Задания с freeCodeCamp:
Если хотите узнать больше:
Книга Grokking Algorithms — лучшая книга на эту тему, если вы новичок в структурах данных / алгоритмах и не обладаете базой компьютерных наук. Автор использует простые объяснения и юмор, рисованные иллюстрации (он является ведущим разработчиком в Etsy), чтобы объяснить некоторые структуры данных, представленные в этой статье.
Наиболее популярные структуры данных. Основы Javascript
Роман Липский
26 февраля 2018
Текст рассчитан на людей, которые понимают, что такое цикл, массив и прочие базовые вещи любого распространенного языка программирования.
Итак, что же такое структуры данных?
Структура данных — это определенный формат хранения, который упрощает обработку данных.
Если у нас есть какой-то набор данных, то для упрощения обработки этой информации ее можно структурировать так, чтобы такие операции как поиск, изменение, добавление или удаление проходили как можно эффективнее по времени и затратам памяти. Мы будем рассматривать основные типы структур данных и более подробно изучать их наиболее распространенные вариации.
Итак, рассмотрим самую базовую из структур данных — список.
Список (list) — набор однотипных (не всегда) данных, следующих друг за другом по цепочке. Для начала рассмотрим одно- и двунаправленные списки.
Каждый элемент списка состоит из данных, указателя на следующий элемент и, если это двунаправленный список, указателя на предыдущий элемент.
В случае начала списка ссылка на элемент, предшествующий первому, = указывается как нулевая (null). С последним элементом всё наоборот — указатель на следующий элемент указывается как null.
Таким образом, независимо от того, сколько элементов в списке, их всегда можно по очереди обойти.
Если последнему элементу в качестве указателя на следующий элемент присвоить указатель первого элемента, или первому — на последний (в зависимости от того, какое направление вы выбрали), или оба варианта сразу (для двустороннего списка), такой тип списка называется кольцо (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) и т. д. Если существуют рёбра, которые связывают одну и ту же вершину, то они называются петлями.
Графы бывают ориентированными и неориентированными. В ориентированных графах у рёбер есть направление.
Для хранения графа можно использовать список для хранения данных, привязанных к вершинам графа и двумерный массив для хранения связей между ними. Есть два вида таких массивов: таблица смежности и таблица инцидентности.
Таблица смежности представляет из себя матрицу NxN, где N — количество вершин в графе. Таблица заполняется с учётом того, ориентированный граф или нет.
В неориентированном графе на пересечении i-ого столбца и j-ой строки ставится 1, если существует ребро, и 0 — если его нет. Для ориентированного графа ставится 1, если ребро направлено от i-ой вершины к j-ой, и -1 – если наоборот.
Таблица инцидентности представляет из себя матрицу NxM, где N — количество вершин, а M — количество рёбер. Заполняется таблица так же, как и таблица смежности (условие направленности сохраняется), но с учётом того, принадлежит j-ое ребро i-ому или нет.
Такие способы представления слишком избыточны для неплотных графов (то есть таких, где связей между вершинами мало). Более оптимизированным по затратам памяти является список смежности.
Список смежности является «списком списков», где в списке для каждой вершины создаётся список вершин, с которыми смежна исходная вершина. Соответственно, длиной такого списка является сумма количества вершин и ребер.
Ещё более оптимизированным является список ребер, где для каждого элемента, который соответствует ребру в графе, указывается, какие вершины ребро соединяет. Данный список зависит только от количества ребер в графе.
Граф называется связным, если в нём нет вершин, которые не соединены ни с какой другой.
Маршрут — это список рёбер, которые соединяют 2 различные вершины. Маршрут называется циклом, если начальная вершина совпадает с конечной.
Эйлеров цикл — это цикл, в котором каждое ребро используется ровно один раз.
Гамильтонов цикл — это цикл, который проходит через каждую вершину ровно один раз (кроме последней, которая является начальной вершиной).
Если граф связный и ацикличный (то есть отсутствуют циклы), то он называется деревом.
Дерево — один из распространённых типов графов. С помощью такой структуры можно отобразить, например, категории каталога в интернет-магазине. Представляется дерево в виде «списка списков»: изначально в список помещается одна вершина, называемая корнем, в которой содержится список её потомков, в каждом из которого может содержаться список из потомков, и т. д. Если у вершины нет потомков, то она называется листом.
Одна из интересных вариаций дерева — бинарное дерево поиска.
Для его создания должны соблюдаться 3 условия:
- Оба поддерева должны быть бинарными деревьями
- Все ключи левого поддерева должны быть меньше ключа корня
- Все ключи правого поддерева должны быть больше либо равны ключу корня
Допустим, нам нужно найти элемент с ключом 4. Начиная от корня, обходим вершины и проверяем на то, меньше, больше либо равно текущее значение значению ключа. В данном примере для поиска 4 мы пройдём по вершинам 8 → 3 → 6 → 4.
Таким образом, сегодня мы рассмотрели 2 базовые и самые популярные структуры данных – списки и деревья. Также в качестве бонуса мы заглянули в основы теории графов чтобы лучше понять общие принципы их использования.
Списки могут использоваться при линейном хранении данных, в то время как применение деревьев в структурировании данных варьируется от проекта к проекту.
Конечно же, это не все, что нужно знать о структурах данных, но описать всё за раз не представляется возможным. Поэтому продолжайте изучать эту тему и стремиться к совершенству!
Классические алгоритмы и структуры данных на JavaScript / Habr
Привет Всем! Я недавно запустил на GitHub проект JavaScript Algorithms and Data Structures, который содержит примеры классических алгоритмов и структур данных написанных на JavaScript с объяснениями, примерами и ссылками для дальнейшего изучения (в частности на соответствующие YouTube видео).Основная задача проекта — помочь программистам в изучении и применении алгоритмов и сделать это на JavaScript-е.
Для того, чтобы сделать процесс изучения более понятным я постарался добавить графические иллюстрации для каждого алгоритма и структуры данных, чтобы быстрее визуально понять о чем идет речь и как тот или иной алгоритм функционирует.
Так же в корневом README вы найдете справочную информацию, которая может пригодиться при изучении. Например:
- Графики Big O нотации (чтобы визуально быстро уловить разницу между
O(n!)иO(n^2)) - Список с конкретными значениями Big O (чтобы понимать насколько большое или маленькое значение у 10! (а оно у него аж 3628800))
- Сложность выполнения базовых операций для структур данных (чтобы понять у каких структур быстрое чтение, а у каких поиск или удаление)
- Сравнительная таблица сложности алгоритмов сортировки (чтобы понять какой способ сортировки выбрать и в каком случае, стабильная ли сортировка или нет)
Весь код на 100% покрыт unit-тестами. Это сделано не только для того, чтобы сохранять код в работоспособном состоянии, но так же и для того, чтобы проиллюстрировать методы и случаи употребления данного конкретного алгоритма или структуры данных (что делать, например, если граф направленный в одном из алгоритмов).
Репозиторий так же содержит песочницу. Это небольшой шаблон функции и пустого теста для нее, который должен помочь программисту сразу же приступить к экспериментам с алгоритмами, вместо того, чтобы создавать заново шаблонный код.
На данный момент в репозитории реализованы следующие структуры данных:
- Linked List
- Queue
- Stack
- Hash Table
- Heap
- Priority Queue
- Trie
- Tree (Binary Search Tree, AVL Tree)
- Graph (both directed and undirected)
- Disjoint Set
Дополнительно так же реализованы более 50 популярных алгоритмов. Среди которых есть алгоритмы сортировки, поиска, алгоритмы связанные с графами, деревьями, множествами, строками и математическими выкладками. Алгоритмы разделены на следующие группы:
- Brute Force Algorithms (перебор всех возможных комбинаций и выбор правильного решения)
- Greedy Algorithms (выбор оптимального решения на каждом текущем шаге)
- Divide and Conquer Algorithms (разделение проблемы на меньшие части и решение этих частей проблемы по-отдельности)
- Dynamic Programming Algorithms (построение решения на основании вычисленных ранее на предыдущих шагах данных)
- Backtracking Algorithms (перебор всех комбинаций (как и в Brute Force) с постоянной проверкой того, удовлетворяет ли текущее решение установленным ограничениям или нет, иначе — возврат на шаг назад)
Репозиторий JavaScript Algorithms and Data Structures находится в активной разработке. Это значит, что там будут появляться новые имплементации алгоритмов и структур данных. Тем не менее, надеюсь уже сейчас этот репозиторий может быть вам полезен. Легкого кодинга!
Структурирование данных с помощью JavaScript: Что такое структура данных?
Я всегда считал, что «структура данных» — это термин, придуманный специально, чтобы сбить нас с толку. В конце концов, мне удалось выяснить, что такое структура данных, просто переставив местами слова в термине «структура данных» — с «data structure» на «structure of data«. В таком контексте акцент внимания смещается с данных (вещи) на структуру (организацию). Другими словами, мы акцентируем внимание не на вещах, а на процессе организации вещей.
Давайте представим, что вещи, о которых мы говорим — это книги. Какое выражение имеет больше смысла: книги со структурой или организация книг? По-моему, последнее. Акцент поставлен на организацию, а не на книги.
Книги, подобно данным, могут быть организованы по-разному. Давайте представим, что у нас есть 20 книг. Как мы их структурируем?
Если мы хотим быстро найти книгу, то нам нужен какой-то указатель. Например, можно расставить книги на полке в алфавитном порядке. Благодаря этому мы сможем быстро находить нужный том.
Если мы хотим прочитать все книги в определенном порядке, например, первой прочитать книгу, которая первая появилась в нашей коллекции, и так далее до последней книги, то нужно разместить книги в соответствии с этим. Кроме этого мы установим определенное ограничение, чтобы мы могли перечитывать книги только в такой последовательности.
Если нам не хватает места, чтобы хранить все книги в одной комнате, то можно разместить их по всему дому. После этого создать список с двумя столбцами: первый столбец будет содержать название книги, а второй – ее местоположение.
Теперь стало ясно, что существует много способов сортировки книг. Но также существует много различных типов структур данных. Структура данных, которую мы используем в веб-разработке, зависит от конкретных условий.
Мы должны понять, что можно использовать и создавать эти структуры данных без каких-либо узкоспециализированных навыков программирования. Все что нам нужно — это понимание JavaScript, его простейших типов данных (например, логических выражений) и ссылочных типов (например, объектов).
Вначале это трудно представить, но не волнуйтесь. Раньше я представлял себе набор, который тоже является типом структуры данных, как просто набор. Но набор это не вещь, а название, присвоенное конкретному способу организации данных. Что не менее важно, набор создается с использованием объектов.
Эта серия статей о структурировании данных с помощью JavaScript должна показать вам, что структуры данных используются, чтобы сделать нашу жизнь проще.
Поскольку структур данных слишком много, чтобы их можно было полностью описать в этой серии статей, мы рассмотрим лишь некоторые из них, но самые распространенные:
- Стек и Очередь;
- Односвязные и двусвязные списки;
- Дерево.
Когда мы закончим рассмотрение данной серии статей, я надеюсь, вы не только узнаете, как реализовать распространенные структуры данных, но и поймете, что они используются вокруг вас. Тогда вы по-другому начнете относиться к данным и к их организации.
10 типов структур данных, которые нужно знать + видео и упражнения
Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.
Структуры данных играют важную роль в процессе разработки ПО, а еще по ним часто задают вопросы на собеседованиях для разработчиков. Хорошая новость в том, что по сути они представляют собой всего лишь специальные форматы для организации и хранения данных.
В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.
Обратите внимание, что некоторые структуры данных включают временную сложность в нотации «большого О». Это относится не ко всем из них, так как иногда временная сложность зависит от реализации. Если вы хотите узнать больше о нотации «большого О», посмотрите это видео от Briana Marie.
В статье я привожу примеры реализации этих структур данных на JavaScript: они также пригодятся, если вы используете низкоуровневый язык вроде С. В многие высокоуровневые языки, включая JavaScript, уже встроены реализации большинства структур данных, о которых пойдет речь. Тем не менее, такие знания станут серьезным преимуществом при поиске работы и пригодятся при написании высокопроизводительного кода.
Связные списки
Связный список — одна из базовых структур данных. Ее часто сравнивают с массивом, так как многие другие структуры можно реализовать с помощью либо массива, либо связного списка. У этих двух типов есть преимущества и недостатки.
Так устроен связный список
Связный список состоит из группы узлов, которые вместе образуют последовательность. Каждый узел содержит две вещи: фактические данные, которые в нем хранятся (это могут быть данные любого типа) и указатель (или ссылку) на следующий узел в последовательности. Также существуют двусвязные списки: в них у каждого узла есть указатель и на следующий, и на предыдущий элемент в списке.
Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.
Пример реализации на JavaScript
Временная сложность связного списка
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Упражнения от freeCodeCamp
Стеки
Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы только в её начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека, сперва придется убрать лежащие сверху.
Стек организован по принципу LIFO (Last In First Out, «последним пришёл — первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.
Так устроен стек
В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).
Пример реализации на JavaScript
Временная сложность стека
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Упражнения от freeCodeCamp
Очереди
Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.
Так устроена очередь
Очередь устроена по принципу FIFO (First In First Out, «первый пришёл — первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.
Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue) и удалять первый элемент (dequeue).
Пример реализации на JavaScript
Временная сложность очереди
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(1) ║
║ Delete ║ O(1) ║ O(1) ║
╚═══════════╩═════════════════╩═══════════════╝
Упражнения от freeCodeCamp
Множества
Так выглядит множество
Множество хранит значения данных без определенного порядка, не повторяя их. Оно позволяет не только добавлять и удалять элементы: есть ещё несколько важных функций, которые можно применять к двум множествам сразу.
- Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
- Пересечение анализирует два множества и создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
- Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
- Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.
Пример реализации на JavaScript
Упражнения от freeCodeCamp
Map
Map — это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:
- добавлять пары в коллекцию;
- удалять пары из коллекции;
- изменять существующей пары;
- искать значение, связанное с определенным ключом.
Так устроена структура map
Пример реализации на JavaScript
Упражнения от freeCodeCamp
Хэш-таблицы
Так работают хэш-таблица и хэш-функция
Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.
Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в том, чтобы таких случаев было как можно меньше.
Таким образом, когда вы вводите пару ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.
Пример реализации на JavaScript
Временная сложность хэш-таблицы
╔═══════════╦═════════════════╦═══════════════╗
║ Алгоритм ║Среднее значение ║ Худший случай ║
╠═══════════╬═════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(1) ║ O(n) ║
║ Insert ║ O(1) ║ O(n) ║
║ Delete ║ O(1) ║ O(n) ║
╚═══════════╩═════════════════╩═══════════════╝
Упражнения от freeCodeCamp
Двоичное дерево поиска
Двоичное дерево поиска
Дерево — это структура данных, состоящая из узлов. Ей присущи следующие свойства:
- Каждое дерево имеет корневой узел (вверху).
- Корневой узел имеет ноль или более дочерних узлов.
- Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.
У двоичного дерева поиска есть два дополнительных свойства:
- Каждый узел имеет до двух дочерних узлов (потомков).
- Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.
Двоичные деревья поиска позволяют быстро находить, добавлять и удалять элементы. Они устроены так, что время каждой операции пропорционально логарифму общего числа элементов в дереве.
Пример реализации на JavaScript
Временная сложность двоичного дерева поиска
╔═══════════╦═════════════════╦══════════════╗
║ Алгоритм ║Среднее значение ║Худший случай ║
╠═══════════╬═════════════════╬══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(log n) ║ O(n) ║
║ Insert ║ O(log n) ║ O(n) ║
║ Delete ║ O(log n) ║ O(n) ║
╚═══════════╩═════════════════╩══════════════╝
Упражнения от freeCodeCamp
Префиксное дерево
Префиксное (нагруженное) дерево — это разновидность дерева поиска. Оно хранит данные в метках, каждая из которых представляет собой узел на дереве. Такие структуры часто используют, чтобы хранить слова и выполнять быстрый поиск по ним — например, для функции автозаполнения.
Так устроено префиксное дерево
Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.
Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.
Пример реализации на JavaScript
Упражнения от freeCodeCamp
Двоичная куча
Двоичная куча — ещё одна древовидная структура данных. В ней у каждого узла не более двух потомков. Также она является совершенным деревом: это значит, что в ней полностью заняты данными все уровни, а последний заполнен слева направо.
Так устроены минимальная и максимальная кучи
Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.
Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.
Пример реализации на JavaScript
Временная сложность двоичной кучи
╔═══════════╦══════════════════╦═══════════════╗
║ Алгоритм ║ Среднее значение ║ Худший случай ║
╠═══════════╬══════════════════╬═══════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(n) ║ O(n) ║
║ Insert ║ O(1) ║ O(log n) ║
║ Delete ║ O(log n) ║ O(log n) ║
║ Peek ║ O(1) ║ O(1) ║
╚═══════════╩══════════════════╩═══════════════╝
Упражнения от freeCodeCamp
Граф
Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.
По такому принципу устроены социальные сети: узлы — это люди, а рёбра — их отношения.
Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.
Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.
Граф в виде матрицы смежности
Список смежности можно представить как перечень элементов, где слева находится один узел, а справа — все остальные узлы, с которыми он соединяется.
Матрица смежности — это сетка с числами, где каждый ряд или колонка соответствуют отдельному узлу в графе. На пересечении ряда и колонки находится число, которое указывает на наличие связи. Нули означают, что она отсутствует; единицы — что связь есть. Чтобы обозначить вес каждой связи, используют числа больше единицы.
Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.
Пример реализации на JavaScript
Временная сложность списка смежности (графа)
╔═══════════════╦════════════╗
║ Алгоритм ║ Время ║
╠═══════════════╬════════════╣
║ Storage ║ O(|V|+|E|) ║
║ Add Vertex ║ O(1) ║
║ Add Edge ║ O(1) ║
║ Remove Vertex ║ O(|V|+|E|) ║
║ Remove Edge ║ O(|E|) ║
║ Query ║ O(|V|) ║
╚═══════════════╩════════════╝
Упражнения от freeCodeCamp
Узнать больше
Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.
От редакции Нетологии
Нетология проводит набор на курсы по Big Data:
1. Программа «Big Data: основы работы с большими массивами данных»
Для кого: инженеры, программисты, аналитики, маркетологи — все, кто только начинает вникать в технологию Big Data.
- введение в историю и основы технологии;
- способы сбора больших данных;
- типы данных;
- основные и продвинутые методы анализа больших данных;
- основы программирования, архитектуры хранения и обработки для работы с большими массивами данных.
Формат занятий: онлайн.
Подробности по ссылке → http://netolo.gy/dJd
2. Программа «Data Scientist»
Для кого: специалисты, работающие или собирающиеся работать с Big Data, а также те, кто планирует построить карьеру в области Data Science. Для обучения необходимо владеть как минимум одним из языков программирования (желательно Python) и помнить программу по математике старших классов (а лучше вуза).
Темы курса:
- экспресс-обучение основным инструментам, Hadoop, кластерные вычисления;
- деревья решений, метод k-ближайших соседей, логистическая регрессия, кластеризация;
- уменьшение размерности данных, методы декомпозиции, спрямляющие пространства;
- введение в рекомендательные системы;
- распознавание изображений, машинное зрение, нейросети;
- обработка текста, дистрибутивная семантика, чатботы;
- временные ряды, модели ARMA/ARIMA, сложные модели прогнозирования.
Формат занятий: офлайн, г. Москва, центр Digital October. Преподают специалисты из Yandex Data Factory, Ростелеком, «Сбербанк-Технологии», Microsoft, OWOX, Clever DATA, МТС.
Подробности по ссылке.
Алгоритмы и структуры данных в Javascript 2019 | OPENSSOURCE
Курс: «Алгоритмы и структуры данных в Javascript 2019». Материал продается на Udemy. Автор — профессионал. Информация свежая, будет полезно для программистов. Материал предоставлен на английском языке + субтитры. Материал прислал анонимный пользователь без комментариев.
Материал может быть удален по запросу правообладателя!
Описание курса:
Для кого этот курс:
- Тот, кто хочет изучить алгоритмы сортировки;
- Тот, кто хочет изучать структуры данных;
- Любой, кто хочет реализовать алгоритмы и структуры данных в Javascript;
- Тот, кто хочет улучшить свои навыки решения проблем;
Этот курс разработан, чтобы помочь вам понять алгоритмы сортировки и структуры данных. По моему опыту большинство людей сосредотачивается на языке программирования, но люди часто забывают об алгоритмах. Алгоритмы определенно более важны, чем язык программирования, вы можете выучить язык программирования примерно за неделю, но способность решать проблемы гораздо сложнее выучить. Но выгоды того стоят.
Когда вы берете интервью, в основном они заботятся о ваших способностях решения проблем, алгоритмах и структурах данных. Чтобы получить работу своей мечты, вам нужно знать, как решить любую проблему, которая у них есть. В этом курсе вы узнаете, как это сделать. Кроме того, я считаю, что ни у кого нет времени на длинные и скучные лекции, поэтому в этом классе я постараюсь объяснить важные вещи быстро и увлекательно, чтобы не утомлять вас до смерти.
Мы начнем с сортировки алгоритмов. Сначала идет разъяснительная лекция, в которой вы узнаете идею алгоритма, затем идет лекция по реализации, где мы реализуем алгоритм в Javascript.
Затем я покажу вам, как работает Рекурсия, еще раз пытаюсь объяснить, что означает рекурсия, затем мы реализуем некоторые алгоритмы рекурсии и используем отладчик, чтобы увидеть, как компьютер оценивает рекурсивные функции.
Затем мы переходим к рекурсивным алгоритмам сортировки. Эти алгоритмы наиболее часто используются. С каждым алгоритмом я объясняю идею, затем мы реализуем алгоритм.
Как только вы изучите алгоритмы сортировки, мы перейдем к сложности времени. Я объясню, что такое сложность времени и зачем она нам нужна, а также покажу, как сравнивать алгоритмы сортировки, чтобы мы могли увидеть, какой из них «лучший».
В этом разделе вы также найдете статью с множеством проблем, где вы можете обучить своим навыкам решения проблем.
После этого мы рассмотрим структуры данных, и я выберу, на мой взгляд, лучшие структуры данных для вас, чтобы выучить важные понятия. Мы начнем с древовидных структур данных. Вы узнаете, как это работает, а также как их реализовать.
Затем мы рассмотрим связанные списки, стеки, попытки и хэш-таблицы. Еще раз мы реализуем все это в Javascript. Я верю, что изучение и понимание этих концепций поможет вам более эффективно решать проблемы.
Если Вы не видите ссылку для скачивания материала — отключите блокиратор рекламы и добавьте наш сайт в список исключений. Если Вы против рекламы на нашем сайте — покупайте контент напрямую у авторов.
Ссылка на скачивание этого материала доступна только зарегистрированным пользователям сайта. Регистрация на сайте бесплатная и не займет много времени. Если у Вас уже есть аккаунт — Вы можете авторизоваться.
Материал предоставлен исключительно для ознакомления!
Опубликовано: Анонимно
Доступ к огромной базе инфопродуктов (более 200.000 материалов), доступ к закрытому Torrent-трекеру с ЭКСКЛЮЗИВНОЙ информацией, доступ к ресурсу с зарубежными материалами и многое другое! Осваивайте новые и трендовые профессии вместе с OPENSSOURCE! НАЖМИТЕ ДЛЯ ПОЛУЧЕНИЯ ПОДРОБНОСТЕЙ[Udemy] Алгоритмы и структуры данных в Javascript (2019) | Складчина
Алгоритмы и структуры данных в Javascript (2019)Основные алгоритмы и структуры данных в Javascript.
Язык: Английский + субтитры
Автор: Luke
Лекций: 43
Продолжительность: 5 часов
Этот курс разработан, чтобы помочь вам понять алгоритмы сортировки и структуры данных. По моему опыту большинство людей сосредотачивается на языке программирования, но люди часто забывают об алгоритмах.
Алгоритмы определенно более важны, чем язык программирования, вы можете выучить язык программирования примерно за неделю, но способность решать проблемы гораздо сложнее выучить. Но выгоды того стоят.
Когда вы берете интервью, в основном они заботятся о ваших способностях решения проблем, алгоритмах и структурах данных.
Чтобы получить работу своей мечты, вам нужно знать, как решить любую проблему, которая у них есть. В этом курсе вы узнаете, как это сделать.
Кроме того, я считаю, что ни у кого нет времени на длинные и скучные лекции, поэтому в этом классе я постараюсь объяснить важные вещи быстро и увлекательно, чтобы не утомлять вас до смерти.
Мы начнем с сортировки алгоритмов:
— Выбор сортировки
— пузырьковая сортировка
Сначала идет разъяснительная лекция, в которой вы узнаете идею алгоритма, затем идет лекция по реализации, где мы реализуем алгоритм в Javascript.
Затем я покажу вам, как работает Рекурсия, еще раз пытаюсь объяснить, что означает рекурсия, затем мы реализуем некоторые алгоритмы рекурсии и используем отладчик, чтобы увидеть, как компьютер оценивает рекурсивные функции.
Затем мы переходим к рекурсивным алгоритмам сортировки
— Сортировка слиянием
— Быстрая сортировка
Эти алгоритмы наиболее часто используются. С каждым алгоритмом я объясняю идею, затем мы реализуем алгоритм.
Как только вы изучите алгоритмы сортировки, мы перейдем к сложности времени:
— Что такое сложность времени
— Big O обозначение
Я объясню, что такое сложность времени и зачем она нам нужна, а также покажу, как сравнивать алгоритмы сортировки, чтобы мы могли увидеть, какой из них «лучший».
В этом разделе вы также найдете статью с множеством проблем, где вы можете обучить своим навыкам решения проблем.
После этого мы рассмотрим структуры данных, и я выберу, на мой взгляд, лучшие структуры данных для вас, чтобы выучить важные понятия.
Мы начнем с древовидных структур данных:
— Двоичное дерево поиска
— AVL дерево
Вы узнаете, как это работает, а также как их реализовать.
Затем мы рассмотрим связанные списки, стеки, попытки и хэш-таблицы. Еще раз мы реализуем все это в Javascript.
Я верю, что изучение и понимание этих концепций поможет вам более эффективно решать проблемы.
Для кого этот курс:
- Тот, кто хочет изучить алгоритмы сортировки
- Тот, кто хочет изучать структуры данных
- Любой, кто хочет реализовать алгоритмы и структуры данных в Javascript
- Тот, кто хочет улучшить свои навыки решения проблем
Скрытый контент.