this.tail.next 如何将节点添加到 this.head？

Question

最近在看单链表的教程，导师的单链表实现让我对push方法很迷惑，搞不懂是怎么回事。

这里是：

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(val) {
    let node = new Node(val);
    if (!this.head) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

let list = new SinglyLinkedList();
list.push('hello');
list.push('goodbye');
}

在这段代码中，我真的很难理解 this.tail.next 如何向 this.head[= 插入一个新节点21=]。对于第一次插入，很明显 head 和 tail 都指向同一个对象，即第一个节点。但是在第一次推送之后，this.tail 被分配了一个新对象并且与 this.head 不同，但是 this.tail.next 仍然将新节点添加到 [=24= 的最后一个下一个属性 ] 这是怎么回事？

Answer 1

But after the first push, this.tail is assigned a new object and is not same with this.head

这是不正确的。第一次插入后，this.head和this.tail指向同一个对象：

if (!this.head) {
  this.head = node;
  this.tail = this.head;
}

对于任何后续插入，this.tail 指向先前插入的节点。 this.tail.next 在 之前更新 新节点被分配给 this.tail:

this.tail.next = node;
this.tail = node;

这意味着当第二次插入发生时，this.tail和this.head仍然指向同一个对象。 this.tail.next = node 被执行，因此也更新了 this.head.next。只有在之后，分配 this.tail 更新为指向新节点。

Answer 2

可视化 push 方法如何完成工作可能会有所帮助。

当用let list = new SinglyLinkedList()构造（空）链表时，出现这种情况（长度属性我省略了，因为它与问题无关）：

 list (this)
  ↓
┌────────────┐
│ head: null │
│ tail: null │
└────────────┘

然后主代码调用list.push('hello')。这从创建节点实例开始，局部变量 node 引用它：

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: null │    │ val: "hello" │
│ tail: null │    │ next: null   │
└────────────┘    └──────────────┘

因为 this.head 是 null，所以 if 块被执行。第一个 this.head = node 导致此状态：

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: ────────> │ val: "hello" │
│ tail: null │    │ next: null   │
└────────────┘    └──────────────┘

然后将该引用复制到 this.tail:

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: ────────> │ val: "hello" │
│ tail: ────────> │ next: null   │
└────────────┘    └──────────────┘

长度更新后，push('hello') 调用完成其工作，node 变量被释放。然后执行list.push('goodbye')。我们再次从创建一个节点开始：

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ────────> │ next: null   │    │ next: null     │
└────────────┘    └──────────────┘    └────────────────┘

现在 this.head 不是 null 所以我们进入 else 块。 this.tail.next = node 被执行，所以我们得到（只需跟随从 this 到 tail 到 next 的箭头，其中 null 被替换为对 node):

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ────────> │ next: ──────────> │ next: null     │
└────────────┘    └──────────────┘    └────────────────┘

然后 this.tail = node 被执行。这会将现有引用替换为另一个引用，恢复 list.tail 始终引用最后一个节点的不变量：

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ───────┐  │ next: ──────────> │ next: null     │
└────────────┘ │  └──────────────┘┌─> └────────────────┘ 
               └──────────────────┘

同样，node 变量的生命周期在执行结束时结束，因此我们只剩下 list 和上面描述的依赖结构。

this.tail.next 如何将节点添加到 this.head？

how does this.tail.next adds node to this.head?

javascript

data-structures