链表的append函数如何在覆盖尾部的同时更新嵌套节点？

Question

我很困惑 append() 如何能够更新链表中的嵌套节点，尽管覆盖了 this.tail。

this.tail.next 如何更新 this.tail 和 this.tail.next 引用的任何内容，在第一种情况下，this.head，等等？特别是当 this.tail 被立即覆盖为 newNode 时。不应该完全覆盖 this.head 吗？尽管整个 this.tail 都设置为 newNode，但 next 密钥如何“保存”？

另外，我知道 this.tail.next 之前引用了节点 - 但是如果我们所做的只是设置 this.tail.next 而不是它的引用 next 键如何更新参考资料？

为了说明这一点 - 我设置了一个变量 potatoes 和另一个变量 fish，引用 potatoes。尽管更新了 potatoes，但很明显 fish 也没有更新，即使它只是对 potatoes.

的引用

let potatoes = 5
let fish = potatoes
potatoes = 2
console.log(fish)

class LinkedList {
  constructor(value) {
    this.head = {
      value,
      next: null
    }
    this.tail = this.head
    this.length = 1
  }
  append(value) {
    const newNode = {
      value,
      next: null
    }
    this.tail.next = newNode
    this.tail = newNode
    this.length++
    return this
  }
 }
 
const linkedList = new LinkedList(5)
linkedList.append(2)
linkedList.append(8)

console.log(linkedList)

Answer 1

这就是为什么它将 tail.next 和 tail 都更改为附加节点的原因。

// This is setting the new Node to be the next Node to the tail Node.
this.tail.next = newNode

// Now it's setting the new node as the tail.
this.tail = newNode

回答引用问题，在JavaScript中只能引用数组和对象，所以在你的pototoe例子中，它没有被引用，而是在给另一个变量赋值。

// Numbers, Strings and booleans, can't be referenced.
let potatoes = 5
let fish = potatoes
potatoes = 2
console.log("Number:", fish)

let orange = "5"
let raspberry = orange
orange = "2"
console.log("String:", raspberry)

let pineapple = false
let watermelon = pineapple
pineapple = true
console.log("Boolean:", watermelon)

// Arrays and Objects can.
let pear = [5]
let apple = pear
pear[0] = 2
console.log("Array:", apple[0])

let banana = {
  value: 5
}
let grape = banana
banana.value = 2
console.log("Object:", grape.value)

Answer 2

How can this.tail.next update both this.tail and whatever this.tail.next is referencing, in the first case, this.head, and so forth?

this.head 通过 next 属性链对 this.tail 进行了（深度）引用。因此，当您改变 this.tail.next 时，可以从任何其他具有 next 链并最终在 this.tail.

处结束的节点“看到”此更改

Especially when this.tail is overwritten to newNode right afterwards. Shouldn't that overwrite this.head entirely?

不，将赋值给this.tail不会影响this.tail在赋值之前引用的对象。更改该对象的唯一方法是更改其属性之一的值。

How is the next key "saved" despite the entire this.tail being set to newNode?

如上所述，this.tail 引用的对象没有被这个赋值改变。赋值只是“切换”this.tail 到（引用）一个不同的对象。

Separately, I understand that this.tail.next is referencing the node before - but how does the reference's next key get updated if all we are doing is setting this.tail.next, and not its reference?

当我们执行 this.tail.next = newNode 时，我们是设置对 newNode 所指内容的引用。那一刻，链表已经长了一个节点。当我们跟进 this.tail = newNode 时，我们确保 this.tail 引用列表中的 last 节点，这是我们要恢复的不变量。

可视化您在脚本中呈现的示例可能会有所帮助。

当const linkedList = new LinkedList(5)执行时，我们将this.head设置为一个新的节点，我们得到这个状态：

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │
│           │    │ next: null│
└───────────┘    └───────────┘

左边的框是链表实例，右边的框是（第一个）节点实例。

构造函数继续 this.tail = this.head。这只是将对新对象的引用复制到新的 tail 属性:

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │
│ tail: ───────> │ next: null│
└───────────┘    └───────────┘

此处length属性管理我略过，与问题无关

然后执行linkedList.append(2)。首先 newNode 获得一个新节点的引用，该节点目前与列表没有任何关系：

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │
│ tail: ───────> │ next: null│    │ next: null│
└───────────┘    └───────────┘    └───────────┘
                                    ↑
                                   newNode

...并且此引用也分配给 this.tail.next：

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │
│ tail: ───────> │ next: ───────> │ next: null│
└───────────┘    └───────────┘    └───────────┘
                                    ↑
                                   newNode

所以this.tail.next = newNode的效果是通过中间的水平箭头反映出来的。请注意，确实 newNode 和 this.tail.next（如果您跟随箭头）指的是同一个节点。

现在我们执行this.tail = newNode。这是它的（简单）效果：

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │
│ tail: ──────┐  │ next: ───────> │ next: null│
└───────────┘ │  └───────────┘ ┌> └───────────┘
              └────────────────┘    ↑
                                   newNode

请注意，这样的赋值会改变链表实例，但不会改变任何节点实例。 append 方法结束，newNode 变量超出范围，不再相关。

让我们继续linkedList.append(8)。 newNode 变量再次获取对新节点的引用：

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │    │ value: 8  │
│ tail: ──────┐  │ next: ───────> │ next: null│    │ next: null│
└───────────┘ │  └───────────┘ ┌> └───────────┘    └───────────┘
              └────────────────┘                     ↑
                                                    newNode

...我们再次用 this.tail.next = newNode:

改变 tail 所指的节点

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │    │ value: 8  │
│ tail: ──────┐  │ next: ───────> │ next: ───────> │ next: null│
└───────────┘ │  └───────────┘ ┌> └───────────┘    └───────────┘
              └────────────────┘                     ↑
                                                    newNode

...唯一剩下的就是让 tail 引用 last 节点（不变量） this.tail.next = newNode:

 linkedList (this)
  ↓
┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
│ head: ───────> │ value: 5  │    │ value: 2  │    │ value: 8  │
│ tail: ──────┐  │ next: ───────> │ next: ───────> │ next: null│
└───────────┘ │  └───────────┘    └───────────┘ ┌> └───────────┘
              └─────────────────────────────────┘    ↑
                                                    newNode

希望这能说明问题。

链表的append函数如何在覆盖尾部的同时更新嵌套节点？

How does the append function of a linked list update a nested node while overwriting the tail?

javascript

linked-list