Связный список — это последовательность структур данных, соединенных между собой ссылками.
Каждая ссылка содержит соединение с другой ссылкой. Связанный список является второй наиболее часто используемой структурой данных после массива. Ниже приведены важные термины для понимания концепции связанного списка.
- Ссылка — каждая ссылка связанного списка может хранить данные, называемые элементом.
- Далее — каждая ссылка связанного списка содержит ссылку на следующую ссылку под названием «Далее».
- Связанный список — связанный список содержит ссылку на первую ссылку под названием «Первая».
Типы связанного списка
Ниже приведены различные типы связанных списков.
- Простой связанный список — навигация по элементам осуществляется только вперед.
- Двойной связанный список — элементы могут перемещаться вперед и назад.
- Круговой связанный список — последний элемент содержит ссылку на первый элемент как на следующий, а первый элемент имеет ссылку на последний элемент как на предыдущий.
Почему связанный список?
Связанные списки часто используются из-за их эффективной вставки и удаления. С их помощью можно реализовать стеки, очереди и другие абстрактные типы данных. Связанные списки — это линейные структуры данных, которые содержат данные в отдельных объектах, называемых узлами. Эти узлы содержат как данные, так и ссылку на следующий узел в списке.
Представление связанного списка
Связанный список можно представить как цепочку узлов, где каждый узел указывает на следующий узел.
Согласно приведенной выше иллюстрации, следующие важные моменты следует учитывать.
- Связанный список содержит элемент ссылки, вызываемый первым.
- Каждая ссылка содержит поле (поля) данных и поле ссылки, называемое next.
- Каждая ссылка связана со своей следующей ссылкой с помощью своей следующей ссылки.
- Последняя ссылка содержит ссылку как нулевую, чтобы отметить конец списка.
Что такое односвязный список?
Односвязный список – это тип связанного списка, который является однонаправленным, то есть его можно перемещать только в одном направлении от начала до последнего узла (хвоста).
Каждый элемент связанного списка называется узлом. Один узел содержит данные и указатель на следующий узел, который помогает поддерживать структуру списка.
Первый узел называется head; он указывает на первый узел списка и помогает нам получить доступ ко всем остальным элементам списка. Последний узел, также иногда называемый хвостом, указывает на NULL, что помогает нам определить, когда заканчивается список.
Первый простой связанный список в JavaScript
Давайте создадим простой связанный список с двумя узлами.
Преимущества односвязного списка
- это облегчает доступ к узлу в прямом направлении.
- вставка и удаление узла более эффективны из-за отсутствия необходимости сдвигать список после операции.
- Требование будет меньше памяти по сравнению с двойным, круговым или дважды круговым связанным списком.
Резюме
В этой статье мы обсудили, что такое связанный список и как его можно реализовать в JavaScript. Мы также обсудили различные типы связанных списков. Если вы хотите продолжить свое путешествие, чтобы узнать больше, обязательно посетите следующие ссылки:
