Связный список — это линейная структура данных, в которой элементы не хранятся в смежных ячейках памяти.
Вв компьютерных науках связный список – это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий.
Он используется для реализации других структур данных, таких как стеки, деревья, очереди и графики. Другие приложения связанного списка:
- Отменить функциональность
- Кэш браузера
- Полиномиальное сложение
- Очереди заданий с приоритетом
Множество
Массив использует непрерывные ячейки памяти, как показано на изображении выше. то есть a содержит адрес памяти 0x02, b содержит следующий адрес памяти 0x03, и так далее.
Если элемент нужно добавить в конец массива, это можно сделать в Big O(1).
Когда элемент необходимо добавить в любом месте, кроме последнего, все последующие элементы должны быть смещены после заданного индекса, и эту операцию можно выполнить за Big O(n), проблема с непрерывными появляется место памяти.
Есть несколько встроенных функций и операций, которые предлагает JS, и к ним прилагается временная сложность, как показано на изображении ниже.
Связанный список
Связанный список многих типов, но это 3 списка, которые используются в основном:
- Односвязный список
- Двусвязный список
- Круговой связанный список
Односвязный список
Каждая запись связанного списка часто называется элементом или узлом.
то есть a, b, c и d являются узлами.
Поле каждого узла, которое содержит адрес следующего узла, обычно называется следующая ссылка или следующий указатель. Остальные поля известны как поля «данные», «информация», «значение», «груз» или «полезная нагрузка».
то есть a содержит адрес b(0x10), b содержит адрес c(0x16) и a содержит адрес d(0x20). a next — это b, b — это next c, c — это next d, а d — это null, поэтому список заканчивается здесь.
head списка — это его первый узел. Хвост списка может относиться либо к остальной части списка после головы, либо к последнему узлу в списке.
то есть a - это голова, а bcd или d могут быть хвостом.
Односвязный список: Создание
Было создано четыре узла a, b, c и d. Next в a относится к b, next в b относится к c, а next в c относится к d.
Таким образом, был создан связанный список a --› b --› c --› d.
Односвязный список: обход
Мы начинаем наш обход с предоставленного головного узла, а текущий узел изначально ссылается на головной. Затем мы проверяем, что следующий узел не является нулевым, поскольку следующий нулевой узел соответствует хвостовому узлу, и вставляем значение в список.
поэтому список будет возвращен в виде массива.
