如何基于单哨兵正确实现双向链表的首尾节点删除？

我基于泛型实现了双向链表适配类SLList，需要实现public T firstout()和public T lastout()方法分别删除首、尾节点。参考建议使用单哨兵节点辅助实现，但没能正确理解哨兵节点的指针逻辑，现有代码无法实现预期功能。

现有代码：

public class SLList<T> { // Add Generics here
    private class IntNode {
        private T data;
        private IntNode previous;
        private IntNode next;

        public IntNode(T data, IntNode previous, IntNode next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }

        public IntNode() { // Self-referencing node
            next = previous = this;
        }
    }

    IntNode sentinel; // One sentinel can serve both purposes
    private int length = 0;

    public SLList() {
        sentinel = new IntNode(); // Self referencing previous/next
    }

    public void addFirst(T data) {
        IntNode node = new IntNode(data, sentinel, sentinel.next);
        sentinel.next = node;
        node.next.previous = node;
    }

    public boolean isempty() {
        return length == 0;
    }

    public T firstout() {
        return sentinel.previous == null;
    }

    public T lastout() {
        return sentinel.next == null;
    }
}

错误点分析 #

• 哨兵指针逻辑理解错误：单哨兵节点的双向链表中，空链表时哨兵的next和previous都指向自身，而非null；首节点是sentinel.next，尾节点是sentinel.previous，你完全搞反了两者的指向关系。
• 方法返回值类型错误：firstout()和lastout()需要返回被删除节点的data（泛型T），但现有代码返回布尔值，类型完全不匹配。
• 链表长度未维护：addFirst()方法中没有更新length变量，导致isempty()的判断完全失效。
• 删除逻辑错误：删除节点不能直接把指针设为null，需要调整前后节点的引用关系，让被删除节点彻底脱离链表，同时还要处理空链表的边界情况。

修正后的代码实现 #

public class SLList<T> {
    private class IntNode {
        private T data;
        private IntNode previous;
        private IntNode next;

        public IntNode(T data, IntNode previous, IntNode next) {
            this.data = data;
            this.previous = previous;
            this.next = next;
        }

        public IntNode() { // 自引用哨兵节点
            next = previous = this;
        }
    }

    private IntNode sentinel;
    private int length = 0;

    public SLList() {
        sentinel = new IntNode();
    }

    public void addFirst(T data) {
        IntNode newNode = new IntNode(data, sentinel, sentinel.next);
        // 先调整原首节点的前驱引用，再更新哨兵的后继引用
        sentinel.next.previous = newNode;
        sentinel.next = newNode;
        length++;
    }

    // 可选：添加尾节点方法，方便测试链表功能
    public void addLast(T data) {
        IntNode newNode = new IntNode(data, sentinel.previous, sentinel);
        sentinel.previous.next = newNode;
        sentinel.previous = newNode;
        length++;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public T firstout() {
        // 空链表时返回null，也可根据需求抛出IllegalStateException
        if (isEmpty()) {
            return null;
        }
        IntNode firstNode = sentinel.next;
        // 调整哨兵与原首节点的下一个节点的引用关系
        sentinel.next = firstNode.next;
        firstNode.next.previous = sentinel;
        // 断开被删除节点的引用，帮助垃圾回收
        firstNode.next = null;
        firstNode.previous = null;
        length--;
        return firstNode.data;
    }

    public T lastout() {
        if (isEmpty()) {
            return null;
        }
        IntNode lastNode = sentinel.previous;
        // 调整哨兵与原尾节点的前一个节点的引用关系
        sentinel.previous = lastNode.previous;
        lastNode.previous.next = sentinel;
        // 断开被删除节点的引用
        lastNode.next = null;
        lastNode.previous = null;
        length--;
        return lastNode.data;
    }
}

关键修正说明 #

1. 维护链表长度：在添加节点的方法中更新length，确保isEmpty()的判断准确可靠。
2. 正确定位节点：明确首节点是sentinel.next、尾节点是sentinel.previous，删除时通过调整相邻节点的引用，让哨兵直接关联到下一个/上一个有效节点。
3. 边界情况处理：删除前先判断链表是否为空，避免触发空指针异常。
4. 清理无效引用：断开被删除节点的previous和next指向，帮助JVM进行垃圾回收。

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