#javascript #data-structures #linked-list #singly-linked-list
#javascript #структуры данных #связанный список #односвязный список
Вопрос:
Я пытаюсь понять, как push()
работает метод с использованием tails в JS. вот код:
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(val) {
const newNode = new Node(val)
if (this.head===null) { // happens only once
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode; // this.a.next = b node???
this.tail = newNode;
}
this.length
}
в частности, я не понимаю else
часть внутри push()
метода. Как каждому next
из a head
присваивается новый узел, если мы скажем this.tail.next = newNode
? Где связь между head и tail и как, говоря this.tail.next = newNode
, мы получаем доступ к head
свойству списка? Когда я запускаю этот код, он работает совершенно правильно, и это меня смущает.
const myList = new SinglyLinkedList();
myList.push("111");
myList.push("222");
myList.push("333");
console.log(myList);
Вывод:
SinglyLinkedList {
length: 3,
head: Node { val: '111', next: Node { val: '222', next: [Node] } },
tail: Node { val: '333', next: null } }
Ответ №1:
Как каждому
next
из ahead
присваивается новый узел, если мы говорим this.tail.next = newNode? Где связь между head и tail и как, сказав this.tail.next = newNode, мы получаем доступ к свойству head списка?
Давайте вернемся к пустому списку. При первом добавлении узла мы попадаем в if
блок, где оба head
и tail
будут ссылаться на один и тот же новый узел. Это означает, что с этого момента все, что вы изменяете, tail
будет изменяться head
, поскольку они ссылаются на один и тот же объект.
Теперь push
выполняется второй, и мы попадаем в else
блок. Там мы присваиваем новый узел next
свойству tail
. Но поскольку это тот же объект, на который head
ссылается, мы фактически устанавливаем head.next
здесь! Это происходит только со вторым push
, потому что сразу после этого назначения tail
присваивается новая ссылка ( next
), поэтому с этого момента head
и tail
ссылаются на разные узлы.
Графически:
После push('111')
:
head
↓
111
↑
tail
Когда push('222')
, после this.tail.next = newNode;
:
head
↓
111 → 222
↑
tail
…и после this.tail = newNode;
того, как во время того же нажатия:
head
↓
111 → 222
↑
tail
Когда push('333')
, после this.tail.next = newNode;
:
head
↓
111 → 222 → 333
↑
tail
…и после this.tail = newNode;
того, как во время того же нажатия:
head
↓
111 → 222 → 333
↑
tail
Ответ №2:
Хорошо, я попробую объяснить, почему это так.
- Когда вы нажимаете в первый раз, оба
head
иtail
относятся к одному и тому же узлу. - Затем, когда вы нажимаете второй раз,
this.tail.next = newNode
добавляет новый узел к обоимhead
иtail
следующему свойству. - Затем
this.tail = newNode
обновляет узелtail
s, который оставляетhead
следующий таким же, как хвост.
Если вы хотите проверить шаг 2 выше, прокомментируйте this.tail = newNode
и нажмите дважды. Вы увидите, что оба head
и tail
следующее свойство одинаковы.