Что такое односвязный список?

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

https://medium.com/@garhewalsatyam996/what-is-a-singly-linked-list-98d4cea516c1

Как создать односвязный список?

Чтобы создать односвязный список в JavaScript, нам необходимо иметь базовое представление о классах и объектах в JavaScript.

Узел состоит из значения и указателя для следующего узла.

В приведенном выше коде мы создали класс Node, который принимает одно значение параметра . При создании объекта класса Node мы получим взамен объект со значением и next в качестве ключа. Этот объект будет хранить текущее значение и указатель на следующий узел.

Односвязный список содержит голову, конец и длину списка. Голова — это начало списка, в котором есть указатель на следующий узел. Хвост — это конец списка, нулевой указатель которого является следующим узлом.

Передача значений в односвязный список

В приведенном выше коде мы создали класс с именем Односвязный список. В конструкторе мы создали 3 переменные head, tail и length, где начальное значение head и tail равно null, а длина списка равна 0.

Чтобы поместить значение в список, мы создали функцию push. Внутри этой функции мы создали переменную newNode и с помощью ключевого слова new делаем объект класса Node. Переменная newNode будет хранить в своей памяти объект, ключами которого являются value и next. В функции push мы задали условие if-else, чтобы проверить, нет ли значения внутри головы, затем присвоить узел голове, и хвост будет равен голове, в противном случае, если значения уже присутствует внутри списка, то текущий хвост будет указывать на новый узел, а новый узел будет новым хвостом.

Извлечение значений из односвязного списка

Функция pop в приведенном выше коде помогает нам извлечь последний узел из односвязного списка. Функция pop сначала проверяет наличие головы, если головы нет, что означает, что внутри списка нет узла, то возвращает значение undefined. Затем мы создали 2 переменные current и temp, обе из которых имеют начальное значение как текущая головка. Теперь мы перебираем текущий элемент и назначаем следующий узел до тех пор, пока в следующем узле не будет нулевого значения. Мы переназначаем хвост, равный значению temp, затем уменьшаем длину на 1 и возвращаем текущий элемент.

Функция сдвига в односвязном списке

Функция сдвига в JavaScript предназначена для удаления первого элемента из списка.

Отменить сдвиг в односвязном списке

Функция Unshift в JavaScript помогает нам добавить элемент в начало списка.

Получить значение узла из индекса

Индекс, который будет передан внутри метода get, будет индексом элемента, который будет возвращен из функции. Всегда помните, что индекс списка также начинается с 0, как массив.

Изменение значения узла в зависимости от его положения в связанном списке.

Функция set в приведенном выше коде поможет нам установить новое значение узла, которое было передано в функцию set. Внутренняя функция set использует функцию get для получения узла в этой конкретной позиции, а затем изменяет значение этого узла и возвращает значение true или false.

Вставка нового узла в определенную позицию

Вставка нового узла с помощью функции вставки внутри связанного списка требует двух параметров: один — это значение, которое мы хотим вставить, а другой — индекс, который будет определять положение узла. Функция вставки внутренне использует три функции: push, unshift и get. Функция push используется, когда нам нужно что-то поместить в конец списка, если заданный индекс равен длине списка, функция unshift используется, чтобы поместить узел в начало списка, и используется функция get. чтобы получить узел.

Удаление узла из связанного списка в заданной позиции

Удаление узла из определенной позиции в связанном списке внутренне использует функцию всплывающего окна и сдвига на основе индекса, который мы передаем в качестве параметра функции удаления.

Это все для односвязного списка👏🏼. Мы обсудим двусвязный список в следующем посте.

Если вам понравился 👍 мой блог, то вы можете угостить меня кофе ☕️ @ https://www.buymeacoffee.com/satyamgarhewal

Небольшая поддержка также будет оценена.