对《CTCI》中Java双向链表last属性实现的疑问

问题描述 #

我正在学习《CTCI》一书，无法理解作者实现的双向链表（DLL）中的last属性。无论如何初始化该双向链表，调用该属性时始终返回null。

我理解last属性不是类变量（无static关键字），因此每个Node对象都有自己的last元素。我原本期望双向链表能始终持有指向整个链表最后一个Node的指针，这种理解是否有误？

另外，我考虑在该实现中加入head属性，并在setPrevious方法中更新它——当head调用setPrevious时更新head。这种思路是否不合理？为何作者没有实现该逻辑？

书中代码及测试 #

实现代码 #

public class LinkedListNode {
    public LinkedListNode next;
    public LinkedListNode prev;
    public LinkedListNode last;
    public int data;
    public LinkedListNode(int d, LinkedListNode n, LinkedListNode p) {
        data = d;
        setNext(n);
        setPrevious(p);
    }
    
    public LinkedListNode(int d) {
        data = d;
    }   
    
    public LinkedListNode() { }

    public void setNext(LinkedListNode n) {
        next = n;
        if (this == last) {
            last = n;
        }
        if (n != null && n.prev != this) {
            n.setPrevious(this);
        }
    }
    
    public void setPrevious(LinkedListNode p) {
        prev = p;
        if (p != null && p.next != this) {
            p.setNext(this);
        }
    }   
    
    public String printForward() {
        if (next != null) {
            return data + "->" + next.printForward();
        } else {
            return ((Integer) data).toString();
        }
    }
    
    public LinkedListNode clone() {
        LinkedListNode next2 = null;
        if (next != null) {
            next2 = next.clone();
        }
        LinkedListNode head2 = new LinkedListNode(data, next2, null);
        return head2;
    }
    public static void main(String[] args) {
        LinkedListNode ll = new LinkedListNode(1);
        ll.setNext(new LinkedListNode(2));

        System.out.println(ll.last);
        System.out.println(ll.next.last);

        LinkedListNode firstNode = new LinkedListNode(1);
        LinkedListNode thirdNode = new LinkedListNode(3);

        LinkedListNode ll2 = new LinkedListNode(1, thirdNode, firstNode);
        System.out.println(firstNode.last);
        System.out.println(ll2.last);
        System.out.println(thirdNode.last);
        
    }
}

测试输出 #

> null
> null
> null
> null
> null

问题解答 #

1. last属性始终为null的原因
   代码中setNext方法里更新last的条件是this == last，但所有节点初始化时last默认是null，这个条件永远不会成立，导致last属性从未被赋值，自然一直返回null。作者的设计意图可能是让每个节点维护指向链表尾部的指针，但代码逻辑存在疏漏，没有完成初始化和后续的正确更新。

2. 关于last属性的理解
   你期望双向链表整体持有尾指针是完全正确的，这是常规双向链表的标准设计（通常会有一个独立的LinkedList类，包含head和tail两个全局指针）。但CTCI的这个实现把链表功能整合进了单个Node类，试图让每个节点自己维护尾引用，但代码未完善，导致last属性完全失效。

3. 加入head属性的思路合理性
   这个思路是可行的，但更合理的做法是用独立的链表类来管理head和tail指针，而不是让每个节点存储全局引用——这样能避免冗余数据，逻辑也更清晰。作者未实现该逻辑，可能是为了简化示例，或是代码本身存在疏漏。CTCI中的部分代码仅为演示特定概念，并非工业级的完整实现。

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