Java中通过root节点实现LinkedStack类无size属性的size()方法

实现思路 #

• 核心逻辑为遍历链式节点计数：栈的所有节点通过Node类的next指针从root节点开始串联，只需要从root出发依次遍历所有节点，每访问一个节点计数器加1，直到遇到null终止遍历，返回最终计数即可。
• 其余方法无需调整：你现有的push、pop、peek、isEmpty、toString方法均未依赖size属性，直接删除类中private int size;属性声明即可。

size()方法实现代码 #

public int size() {
    int count = 0;
    Node current = root;
    // 遍历所有节点计数，逻辑和现有toString方法的遍历规则完全一致
    while (current != null) {
        count++;
        current = current.getNext();
    }
    return count;
}

补充说明 #

• 性能表现：该实现时间复杂度为O(n)（n为栈内元素数量），相比原维护size变量的O(1)实现有一定性能损耗，优势是完全避免了push/pop操作时忘记更新size导致的计数不一致问题，更适合栈元素数量不大、size()方法调用频率不高的场景。
• 兼容性：返回结果和原有size()方法完全一致，不会影响上层调用逻辑。

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