Метод LinkedList push() в JavaScript с хвостом

#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 из a head присваивается новый узел, если мы говорим 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
 ↓
111222
 ↑
tail
  

…и после this.tail = newNode; того, как во время того же нажатия:

 head
 ↓
111222
       ↑
     tail
  

Когда push('333') , после this.tail.next = newNode; :

 head
 ↓
111222333
       ↑
     tail
  

…и после this.tail = newNode; того, как во время того же нажатия:

 head
 ↓
111222333
             ↑
           tail
  

Ответ №2:

Хорошо, я попробую объяснить, почему это так.

  1. Когда вы нажимаете в первый раз, оба head и tail относятся к одному и тому же узлу.
  2. Затем, когда вы нажимаете второй раз, this.tail.next = newNode добавляет новый узел к обоим head и tail следующему свойству.
  3. Затем this.tail = newNode обновляет узел tail s, который оставляет head следующий таким же, как хвост.

Если вы хотите проверить шаг 2 выше, прокомментируйте this.tail = newNode и нажмите дважды. Вы увидите, что оба head и tail следующее свойство одинаковы.