单链表shift方法疑问：调用后tail未置空的原因解析

先看我实现的单链表代码：

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.tail = newNode;
        }
        this.length++;
        return this;
    }
    shift() {
        if (!this.head) return undefined;
        let first = this.head
        this.head = first.next
        this.length--;

        return this
    }
}

let list = new SinglyLinkedList()
list.push("1")
list.push("2")
list.shift()

第一次调用shift()后，链表状态符合预期：

{
    "head": {
        "val": "2",
        "next": null
    },
    "tail": {
        "val": "2",
        "next": null
    },
    "length": 1
}

但再次调用shift()后，出现了不符合预期的结果：

{
    "head": null,
    "tail": {
        "val": "2",
        "next": null
    },
    "length": 0
}

我原本以为此时tail会变成null，但实际它还指向原来的节点。后来在shift方法里添加了「当length为0时将tail置为null」的逻辑，就得到了head和tail均为null的正确结果。下面说下背后的原因和解决逻辑的原理：

问题原因 #

原来的shift方法只处理了head的更新和length的递减，完全没考虑tail的边界情况：

• 当链表只剩最后一个节点时，调用shift会把head设为first.next（也就是null），同时length减为0，但此时tail的引用没有被修改，仍然指向之前的最后一个节点。
• 只有push方法里会主动设置tail的值，shift方法没做对应的收尾处理，导致空链表的tail状态不一致。

解决逻辑的原理 #

单链表的空状态定义是head和tail都为null，length为0。所以在shift方法里，当length递减后变为0时，必须同步把tail设为null，这样才能保证链表状态的一致性。修改后的shift方法应该是这样：

shift() {
    if (!this.head) return undefined;
    let first = this.head
    this.head = first.next
    this.length--;
    // 新增判断，当链表为空时同步置空tail
    if (this.length === 0) {
        this.tail = null;
    }
    return this
}

这样当最后一个节点被移除后，tail会被正确置为null，链表的状态就完全符合空链表的定义了。

内容的提问来源于stack exchange，提问作者jhchoi