链表实现队列和栈时为何队列尾元素、栈最早插入元素指向null

两者的指针指向设计，本质是为了匹配对应数据结构的操作特性，保证入队/出队、入栈/出栈的时间复杂度都是O(1)，同时作为遍历终止的判断标记。

1. 队列队尾元素next指向null的原因 #

队列是先进先出（FIFO）结构，默认采用头删尾插的实现逻辑：

• 所有元素的遍历方向是从队头到队尾，当遍历到节点的next为null时，就判定已经到达队尾，终止遍历
• 入队操作只需要修改当前队尾节点的next指针指向新节点，再将新节点的next设为null、更新队尾指针即可，全程O(1)时间复杂度

如果调整为队头指向null，相当于反向存储队列元素，此时出队操作需要从队头遍历到倒数第二个节点才能删除队尾元素，时间复杂度退化为O(n)，完全失去链表实现队列的效率优势。

2. 栈底（最早插入）元素next指向null的原因 #

栈是后进先出（LIFO）结构，默认采用栈顶插入/删除的实现逻辑：

• 所有元素的遍历方向是从栈顶到栈底，当遍历到节点的next为null时，就判定已经到达栈底，终止遍历
• 入栈操作只需要将新节点的next指针指向旧栈顶，再更新栈顶指针即可；出栈操作直接将栈顶指针指向栈顶的next即可，全程O(1)时间复杂度

如果调整为栈顶元素next指向null，相当于反向存储栈元素，此时入栈操作需要从栈顶遍历到栈底才能插入新元素，时间复杂度退化为O(n)，不符合栈的效率要求。

Java实现参考代码片段 #

队列核心操作 #

class Queue<E> {
    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E val) { this.val = val; }
    }
    private Node<E> front; // 队头
    private Node<E> rear; // 队尾

    public void enqueue(E val) {
        Node<E> newNode = new Node<>(val);
        if (front == null) {
            front = newNode;
            rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
        rear.next = null; // 新队尾next显式设为null
    }

    public E dequeue() {
        if (front == null) throw new RuntimeException("队列为空");
        E val = front.val;
        front = front.next;
        if (front == null) rear = null;
        return val;
    }
}

栈核心操作 #

class Stack<E> {
    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E val) { this.val = val; }
    }
    private Node<E> top; // 栈顶

    public void push(E val) {
        Node<E> newNode = new Node<>(val);
        newNode.next = top;
        top = newNode;
        // 第一个元素入栈时，top.next默认就是null，即栈底指向null
    }

    public E pop() {
        if (top == null) throw new RuntimeException("栈为空");
        E val = top.val;
        top = top.next;
        return val;
    }
}

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