В этой статье мы реализуем связанный список с помощью функций javascript. Итак, что такое связанный список? Это линейная структура данных, в которой данные не хранятся в непрерывных ячейках памяти, а элементы связаны с помощью поля ссылки.
Как видите, элементы связаны друг с другом с помощью стрелок, обозначающих ссылку. Элементы связанного списка называются узлами, поэтому мы также можем сказать, что все узлы связаны указателями и именно так узлы организованы в последовательность. Первый узел называется головкой. Если связанный список пуст, то значение заголовка равно NULL. Последний узел связанного списка имеет NULL в качестве ссылки, что означает отсутствие следующего узла. Односвязный список состоит из двух частей:
- Данные (значение узла)
- Далее (ссылка на следующий узел)
Преимущества
- Вы можете динамически вставлять данные в связанный список без предварительного объявления размера и выделения памяти.
- Операции вставки и удаления в связанном списке намного проще, чем с массивом, поскольку в отличие от массива нам не нужно перемещать все элементы за вставленные или удаленные элементы.
Недостатки
- Дополнительное пространство памяти необходимо для хранения ссылки на следующий узел.
- Произвольный доступ к элементам не допускается. Мы должны обращаться к элементам последовательно, начиная с первого узла. Таким образом, мы не можем эффективно выполнять двоичный поиск по связанным спискам с его реализацией по умолчанию.
Реализация связного списка с использованием функций Javascript -
В этом разделе мы реализуем следующие функции при разработке односвязного списка в javascript.
get(index)
: получить значение узла по данному индексу в связанном списке.addAtHead(value)
: добавьте узел с значением в качестве данных перед первым узлом связанного списка.addAtTail(value)
: добавить узел со значением значение в конец связанного списка.addAtIndex(index, value)
: добавить узел со значением value по данному индексу связанного списка.deleteAtIndex(index)
: удалить узел по данному индексу в связанном списке.
Начнем с функции MyLinkedList. Эта функция содержит другую функцию getNewNode, которая создает новый узел, используя значение из аргументов, и возвращает вновь созданный узел с ссылкой, инициализированный как NULL. Мы хотим сохранить в памяти первую запись (заголовок) и размер списка.
var MyLinkedList = function() { this.getNewNode = value => { return { value, next: null }; }; this.head = null; this.length = 0; };
get (индекс)
Этот метод возвращает -1, если index недействителен. Если index действителен, мы будем просматривать связанный список, начиная с заголовка. Для этого мы будем использовать цикл while, который продолжается до тех пор, пока не будет достигнут индекс, и вернет значение узла.
MyLinkedList.prototype.get = function(index) { let head = this.head; let i = 0; if (index < 0 || index >= this.length) { return -1; } while (head.next) { if (i === index) { break; } head = head.next; i++; } return head.value; };
addAtHead (значение)
Этот метод создает новый узел и с переданным значением value добавляет его в первую позицию связанного списка.
- Инициализируйте новый узел с помощью значения.
- Если голова отсутствует (когда связанный список пуст), мы назначаем узел на голову.
- Если заголовок присутствует, присвойте исходный головной узел следующему (ссылке) нового узла.
- Назначьте новый узел заголовку.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtHead = function(value) { const newNode = this.getNewNode(value); if (this.head) { newNode.next = this.head; } this.head = newNode; this.length++; };
Этот метод четко объясняет, насколько простой и менее затратной является операция вставки связанного списка, поскольку, в отличие от массива, нам не нужно перемещать все элементы за вставленный элемент.
addAtTail (значение)
Этот метод создает новый узел с переданным значением и добавляет его в связанный список.
- Проверим, есть ли голова. Если нет, мы можем напрямую вызвать addAtHead (value) или инициализировать новый узел и назначить его заголовку.
- Если заголовок существует, мы будем перемещаться по списку, начиная с начала (заголовок), пока next не станет NULL (т.е. пока мы не дойдем до последнего узла связанного списка. следующая ссылка NULL). Когда мы дойдем до последнего узла, мы инициализируем новый узел с переданным значением и присвоим его следующему исходному последнему узлу.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtTail = function(value) { if (!this.head) { const newNode = this.getNewNode(value); this.head = newNode; this.length++; return; } let head = this.head; while (head.next) { head = head.next; } const newNode = this.node(value); head.next = newNode; this.length++; };
addAtIndex (значение, индекс)
Этот метод создает новый узел с аргументом value и добавляет его к переданному индексу связанного списка.
- Инициализируйте новый узел с помощью значения.
- Если index недействителен, мы не выполняем вставку. Если index равен 0 или заголовок не существует (т.е. связанный список пуст), мы просто вызываем функцию addAtHead. Если index равен длине связанного списка, мы просто вызываем функцию addAtTail, поскольку узел будет добавлен в конец связанного списка.
- В остальных случаях мы будем перемещаться до index. В (индекс -1) мы сохраним предыдущий узел. В index мы получаем доступ к исходному или текущему элементу next (reference) и назначаем его в качестве ссылки на новый узел. Теперь мы добавляем новый узел к следующему (справочному) предыдущему узлу.
- Увеличьте длину на 1.
MyLinkedList.prototype.addAtIndex = function(index, value) { if (index < 0 || index > this.length) { return; } else if (index === 0 || !this.head) { this.addAtHead(value); return; } else if (index === this.length) { this.addAtTail(value); return; } let head = this.head; let i = 0; let prev = null; while (head.next || index === this.length - 1) { if (i === index - 1) { prev = head; } else if (i === index) { const newNode = this.getNewNode(value); newNode.next = head; prev.next = newNode; this.length++; break; } head = head.next; i++; } };
deleteAtIndex (индекс)
Эта функция удаляет узел по переданному индексу.
- Если index равен 0, мы получаем доступ к узлу с 1-го index и назначаем его заголовку.
- Если index равен длине связанного списка, мы проходим до индекса (length -1) и присваиваем NULL ссылке (length -1) указатель.
- В остальных случаях мы просматриваем связанный список до index. В index мы назначаем next (reference) текущего узла (index -1) узла next (ссылка)
- Уменьшите длину на 1.
MyLinkedList.prototype.deleteAtIndex = function(index) { let head = this.head; let i = 0; let prev = null; if (index === 0) { while (head.next) { if (i === index + 1) { this.head = head; this.length--; break; } head = head.next; i++; } } else if (index === this.length - 1) { while (head.next) { if (i === this.length - 2) { head.next = null; this.length--; break; } head = head.next; i++; } } else { while (head.next) { if (i === index - 1) { prev = head; } if (i === index) { prev.next = head.next; this.length--; break; } head = head.next; i++; } } };
Заключение
После создания собственного связанного списка в javascript вы должны лучше понять плюсы и минусы структуры данных связанного списка. В то время как операции вставки и удаления в связанном списке проще, доступ к случайным элементам - дорогостоящая операция.
Хотя мы можем использовать массивы для большинства наших операций, использование связанного списка может быть очень полезным при реализации других структур данных, таких как графы, стеки и очереди. Одним из реальных примеров, где связанный список может использоваться в реальном мире, является программа просмотра фотографий для связи между предыдущими и следующими фотографиями.
Вот и все!
Чтобы увидеть полный код нашей реализации, ознакомьтесь с этой сутью GitHub.
Я надеюсь, что вы нашли эту реализацию полезной для разработки одного из фундаментальных типов данных информатики, и если у вас есть какие-либо вопросы или отзывы, не стесняйтесь Оставить комментарий.