推送法在SinglyLinkedList中头节点的工作原理

Question

每当给尾巴分配一个新的节点时，我都不知道头是如何变化的。我是不是错过了一些关于课堂如何工作的重要内容？请给我详细解释一下。

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

class SinglyLinkedList {
    constructor(){
        this.head = null
        this.tail = null
        this.length = 0
    }
    push(val){
        let newNode = new Node(val)
        if(!this.head){
            this.head = newNode 
            this.tail = this.head
        }else{
            this.tail.next = newNode // <-- this line
            this.tail = newNode
        }
        this.length++
        return this
    }
}
 let list = new SinglyLinkedList()
 slist.push(1)
 slist.push(2)
 slist.push(3)

 console.log(JSON.stringify(list))
//output {"head":{"val":1,"next":{"val":2,"next":
// {"val":3,"next":null}}},"tail":{"val":3,"next":null},"length":3}

头不是只得到第一个节点对象吗？

Answer 1

这可能有助于想象这一点。

当let list = new SinglyLinkedList()执行时，我们可以这样描绘状态：

slist
  │
  ▼
┌────────────┐
│ head: null │
│ tail: null │
│ length: 0  │
└────────────┘           

现在，让我们看看当slist.push(1)被调用时会发生什么。在执行该方法时，this将是slist。第一个newNode被创建为new Node(val)

this
slist             newNode
  │                 │
  ▼                 ▼
┌────────────┐    ┌────────────┐
│ head: null │    │ val:  1    │
│ tail: null │    │ next: null │
│ length: 0  │    └────────────┘
└────────────┘

正如this.head是null一样，!this.head是一个真实的表达式，因此执行if块。this.head = newNode的结果是：

this
slist             newNode
  │                 │
  ▼                 ▼
┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │
│ tail: null │    │ next: null │
│ length: 0  │    └────────────┘
└────────────┘

在this.tail = this.head执行之后，我们得到以下内容：

this
slist             newNode
  │                 │
  ▼                 ▼
┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │
│ tail: ────────► │ next: null │
│ length: 0  │    └────────────┘
└────────────┘

最后，length属性增加。return this被执行，但调用方不使用该返回值。打电话的人看到这个：

slist (returned)
  │
  ▼
┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │
│ tail: ────────► │ next: null │
│ length: 1  │    └────────────┘
└────────────┘

在push的下一个调用中，我们再次得到一个newNode

this
slist                               newNode
  │                                   │
  ▼                                   ▼
┌────────────┐    ┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │    │ val:  2    │
│ tail: ────────► │ next: null │    │ next: null │
│ length: 1  │    └────────────┘    └────────────┘
└────────────┘

这次head不是null，所以我们进入了else块。在这里，我们执行this.tail.next = newNode，这就是您询问的内容。this引用列表对象(图中的第一个框)，this.tail引用节点对象(图中的第二个框)，this.tail.next是当前为null的属性，但通过赋值获得新的引用。在next属性引用的赋值之后，newNode

this
slist                               newNode
  │                                   │
  ▼                                   ▼
┌────────────┐    ┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │    │ val:  2    │
│ tail: ────────► │ next: ────────► │ next: null │
│ length: 1  │    └────────────┘    └────────────┘
└────────────┘

最后执行this.tail = newNode和this.length++：

this
slist                               newNode
  │                                   │
  ▼                                   ▼
┌────────────┐    ┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │    │ val:  2    │
│ tail: ───────┐  │ next: ────────► │ next: null │
│ length: 2  │ │  └────────────┘    └────────────┘
└────────────┘ │                      ▲
               └──────────────────────┘

对slist.push(3)的调用重复此过程，调用方将得到以下结果：

slist
  │
  ▼
┌────────────┐    ┌────────────┐    ┌────────────┐    ┌────────────┐
│ head: ────────► │ val:  1    │    │ val:  2    │    │ val:  3    │
│ tail: ───────┐  │ next: ────────► │ next: ────────► │ next: null │
│ length: 2  │ │  └────────────┘    └────────────┘    └────────────┘
└────────────┘ │                                         ▲
               └─────────────────────────────────────────┘

Answer 2

当列表为空并添加第一项时，情况就是如此。- if(!this.head)