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

Основы

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

Проблема

Поскольку значения не индексируются; трудно найти индивидуальное значение. Вы должны пройти по списку, следуя узлам указателя, пока они не достигнут пункта назначения или списка. Если вам нужен легкий доступ к отдельным узлам, вы потеряете экономию времени.

Пример использования

Ваш список покупок, из которого вы планируете добавлять и удалять товары

Ключевые функции

Поиск головы и хвоста — позволяет найти начало и конец связанного списка.

Добавление в хвост — добавляет узел в конец вашего списка.

Удалить голову — удаляет первый элемент из связанного списка.

Содержит — проверьте, содержит ли ваш связанный список определенное значение.

Дополнительные примеры

http://www.thatjsdude.com/interview/linkedList.html

Различия двусвязных списков

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

Древовидные структуры данных

Основы

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

Высота узла — это то, на сколько узлов он удален от корневого узла. Высота дерева — это максимальное расстояние от корневого узла до конечного узла.

Использует

Возможное использование деревьев может быть отображением вашего генеалогического древа или иерархии организации.

Основные функции

children — массив, содержащий поддеревья

addChild — принимает значение и добавляет его как дочерний узел существующего узла.

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

Двоичное дерево поиска

Использовать

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

Типы обхода

Предварительный заказ — начните с корня и продвигайтесь вниз по дереву слева направо.

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

Post-Order — начните с нижней части каждой цепочки узлов, затем двигайтесь в обратном направлении.

Графики

Основы

В структуре данных графа узлы называются вершинами и каким-то образом связаны между собой. Ребра (пары) образуются при соединении двух узлов. Градусы — это количество ребер, которые имеет узел. Связный граф означает, что между каждой парой вершин существует путь. Если каждая вершина напрямую связана с каждой другой вершиной, то граф называется полным.

Типы

Ненаправленный — ребра неупорядочены, потому что вы можете перемещаться между вершинами.

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

Использование

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

Ключевые функции

Общие функции узла — Добавить, Удалить, Содержит

forEachNode — сделать что-то с каждым узлом

Edge Function — Add, Remove, Has Edge (проверяет, соединены ли два узла)

Установить

Основы

Наборы содержат уникальные неупорядоченные значения. В своей простейшей форме Set представляет собой массив. Вы можете часто видеть, что это представлено в виде кругов, то есть диаграммы Венна. Лучше всего использовать объекты, а не массивы, чтобы выполнять сложные операции с наименьшим временем.

Использование

Случайный выбор одежды из гардероба (при условии, что вы не Марк Цукерберг).

Ключевые функции

Общие — Добавить и удалить

Пересечение — значения, которые разделяют два набора

Отличие — ценности, которые они не разделяют

Union — предполагает наличие пересечения и возвращает все уникальные значения.

Таблица хеширования

Основы

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

Использование

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

Ключевые функции

Вставить — добавляет кортеж в хеш-таблицу.

Удалить — удаляет кортеж из хеш-таблицы.

Retrieve — извлекает кортеж по заданному ключу.

Источники

Все

  • Взломайте материалы реактора

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

Деревья

Графики

Наборы