JavaScript 中带尾巴的 LinkedList push() 方法

Question

我试图了解 push() 方法如何在 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++
    }

具体来说，我不理解 push() 方法中的 else 部分。如果我们说 this.tail.next = newNode，head 的每个 next 如何分配一个新节点？ 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 } }

Answer 1

How does each next of a head gets assigned a new node if we say this.tail.next = newNode? Where is the relation between head and tail and how by saying this.tail.next = newNode we get access to the head property of the list?

让我们回到空列表。第一次添加节点时，我们进入 if 块，其中 head 和 tail 都将引用 相同的 新节点。这意味着从那一刻起，无论你在 tail 中发生什么变化，都会发生变化 head，因为它们指的是同一个对象。

现在执行第二个 push，我们进入 else 块。在那里我们将新节点分配给 tail 的 next 属性。但由于这是 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

Answer 2

好的，我会尝试解释为什么会这样。

第一次push时，head和tail指的是同一个节点
然后当您第二次推送时，this.tail.next = newNode 将新节点添加到 head 和 tail 的下一个属性.
然后 this.tail = newNode 更新 tail 的节点，使 head 的下一个节点与尾部相同。

如果要检查上面的第2步，请注释掉this.tail = newNode并推送两次。您会看到 head 和 tail 的下一个属性是相同的。

JavaScript 中带尾巴的 LinkedList push() 方法

LinkedList push() method in JavaScript with a tail

javascript

linked-list

data-structures

singly-linked-list