Односвязные списки... круговые связанные списки... двусвязные списки... и так далее.
Если вы читаете эту статью прямо сейчас, вполне вероятно, что вы так же интересуетесь связными списками, как и я. Итак, давайте разберем это шаг за шагом, чтобы лучше понять их. Для начала, давайте начнем с основного вопроса. Что такое связанный список?
Быстрый поиск может дать вам ответ, подобный этому:
«…упорядоченный набор элементов данных, каждый из которых содержит ссылку на своего преемника (а иногда и на предшественника)». - Оксфордский словарь
Или, если вам повезет, вы можете наткнуться на непонятное определение Википедии:
В «информатике связный список — это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти».
…Что? Порядок... не определяется их физическим размещением в памяти? Что ж, это звучит очень интригующе. Давайте погрузимся глубже.
Итак, у нас есть «набор элементов данных», который для нашего сегодняшнего сравнения может быть массивом или связанным списком. Чтобы избежать избыточности примеров кода в Интернете, моя сегодняшняя цель — помочь вам понять связанные списки — предоставить минимальное количество примеров кода. Вы можете найти ссылки и полные примеры кода внизу этой статьи.
Существуют преимущества и недостатки использования массива или связанного списка для доступа к нашим элементам данных. Сначала посмотрим на массив:
МАССИВ ЗА И ПРОТИВ
Преимущества:
- иметь O(1) произвольный доступ (нам не нужно проходить последовательность, чтобы найти элемент данных)
- может использовать бинарный и линейный поиск
- требуется меньше памяти
- лучшая локализация кеша (значительное увеличение производительности)
- поддерживает совместное использование структуры
Недостатки:
- фиксированное количество элементов данных
- размер указывается при объявлении (не может уменьшаться или увеличиваться)
- вставка и удаление элемента обходится дорого (требуется сдвиг всех элементов данных в массиве)
- использование памяти неэффективно
- смежные (каждый элемент должен находиться рядом с предыдущим элементом в памяти). Поэтому, когда в массив добавляются новые элементы, весь массив удаляется из памяти, а новый элемент с дополнительным элементом будет находиться в другом месте в памяти.
СВЯЗАННЫЙ СПИСОК ЗА И ПРОТИВ
Преимущества:
- переменное количество элементов данных
- размер может увеличиваться и уменьшаться во время объявления
- проще, быстрее и эффективнее добавлять и удалять элементы
- эффективное использование памяти
- непримитивный
- несмежные (следующий узел может храниться везде, где он доступен). При создании новых узлов
Недостатки:
- последовательный доступ (медленнее для доступа к более глубоким вложенным элементам данных)
- только линейный поиск
- требуется больше памяти
- произвольный доступ не разрешен (O(n))
Отлично. Похоже, у каждого из них есть свои преимущества и недостатки. Можно даже сказать, что каждое преимущество и недостаток тесно связаны друг с другом.
В массивах мы снижаем использование памяти для более быстрого доступа к элементам данных, что повышает производительность за счет лучшей локализации кэша. Связанные списки идут на компромисс, требуя больше памяти для эффективного добавления и удаления элементов, что затем делает память использование более эффективным.
Имея эту информацию, мы можем начать представлять, где может быть полезно использовать тот или иной метод.
Лучше всего использовать массивы, когда вам нужен индексированный или произвольный доступ к элементам (особенно если они вам нужны часто), вы знаете максимальный размер вашей структуры данных или когда память беспокоит. Вот несколько реальных примеров:
- Некоторые шифрования используют двумерные массивы символов.
- Двумерные массивы также используются при обработке изображений.
- Рендеринг нескольких элементов в компоненты.
связанный список удобен, когда вставки и удаления необходимо постоянно обновлять (данные изменчивы), когда список может уменьшаться или увеличиваться, или когда список необходимо перемешивать. Реальные приложения для связанных списков включают:
- Средства просмотра изображений, веб-браузеры, музыкальные проигрыватели или любое другое место, где может потребоваться предыдущая и следующая функция.
- Реализация стеков, очередей и графов.
- Ведение справочников имен.
- Арифметические операции или манипулирование полиномами.
Вау, это много полезного! Если вы похожи на меня, вы хотите докопаться до сути и глубже понять, как это работает в коде. Давайте разберем несколько примеров кода, ссылки на которые приведены ниже:
Это наш отдельный узел, передаваемые в него данные — это отдельный элемент данных, которому мы назначим «указатель» в зависимости от его положения в списке.
function Node(data) {
this.data = data;
this.next = null;
};
Источник: https://medium.com/@deniswells59/singly-linked-lists-with-javascript-81859a5a5095
Это базовый связанный список с функцией добавления для добавления новых узлов. Давайте пройдемся по каждой строке здесь.
function LinkedList() {
// head will be the top of the list
// we'll define it as null for now
this.head = null;
this.length = 0;
// add function starts here
this.add = function(data) {
// here we create a new Node class with the data item passed in.
const nodeToAdd = new Node(data),
/* if the head is null, the nodeToAdd variable
becomes the head of the list. */
nodeToCheck = this.head;
if(!nodeToCheck) {
this.head = nodeToAdd;
/* the length of the list increases with each addition,
this is how the list grows in size. */
this.length++;
return nodeToAdd;
}
// loop until we find the end
while(nodeToCheck.next) {
nodeToCheck = nodeToCheck.next;
}
// once we're at the end of the list
nodeToCheck.next = nodeToAdd;
this.length++;
return nodeToAdd;
}
}
Источник: https://medium.com/@deniswells59/singly-linked-lists-with-javascript-81859a5a5095
Этот пример должен дать нам хорошее представление о том, что происходит внутри связанного списка. У нас есть узлы, содержащие два конструктора: данные, к которым мы можем захотеть получить доступ, и указатель на следующий узел, если вместо этого мы хотим получить к нему доступ. Именно указатели позволяют связным спискам не требовать размещения каждого узла в памяти рядом с другим.
Существует ряд различных методов, которые мы можем создать для улучшения нашего связанного списка, в том числе: удаление элемента, вставка/удаление из индекса и получение элемента из индекса. Веб-сайт geeksforgeeks предоставляет отличное пошаговое руководство по реализации связанных списков, основанных на классах. Для продолжения функционального связанного списка, приведенного выше, вы можете ознакомиться со статьей Дениса Уэллса о нем здесь.
Если вы хотите начать работать со связанными списками и хотите начать работать над ними прямо сейчас, я поддерживаю это мнение. Но подождите!! Есть еще одна вещь, которую вам нужно знать, прежде чем идти. Существуют различные типы связанных списков! Давайте закончим эту учебную экспедицию вишенкой на торте, узнав об этом:
ТИПЫ СВЯЗАННЫХ СПИСКОВ
Односвязные списки: навигация по элементам данных осуществляется только вперед и останавливается в конце списка.
Двусвязные списки: можно перемещаться по элементам данных назад и вперед. В этом случае в нашем классе или функции Node будет третий конструктор (скорее всего this.prev).
Круговые связанные списки: круговые списки позволяют нам двигаться от хвоста к голове или от головы к хвосту. Это можно использовать с односвязными или двусвязными списками.
Многосвязные списки.узлы содержат несколько указателей на другие узлы в одном наборе данных. Это позволяет использовать более эффективные алгоритмы при обходе разных точек данных в одном и том же наборе данных.
Это было настоящее путешествие! Надеюсь, вы узнали столько же, сколько и я, изучая связанные списки, и это вдохновит вас на дальнейшее изучение. Существуют и другие типы структур данных, которые не менее интересны, включая древовидные структуры данных, структуры данных стека, структуры данных очереди и т. д. Оставайтесь с нами, чтобы узнать больше!
КЛАСС — ССЫЛОЧНЫЙ СПИСОК:
ФУНКЦИОНАЛЬНЫЙ СВЯЗАННЫЙ СПИСОК:
Ссылки:
