Java循环链表实现中如何将尾节点正确链接到头节点

问题核心原因 #

1. 代码仅实现了头节点的previous指针指向尾节点的逻辑，始终没有设置尾节点的next指针指向头节点，导致循环链路断裂
2. 遍历展示方法的终止条件不符合循环链表的特性，循环链表中不存在next为null的节点，原有逻辑要么提前终止，要么在修复循环后出现无限遍历
3. 头部插入新节点时，没有同步更新旧尾节点的next指针指向新的头节点

具体修改方案 #

1. 修正FindTail()方法 #

找到尾节点后增加尾节点next指向头节点的逻辑，修复循环链路：

private void FindTail(){
    Node current_node = this.head;
    // 处理链表只有一个节点的情况
    if(current_node.GetNextNode() == null || current_node.GetNextNode() == current_node){
        this.tail = current_node;
        this.head.SetPreviousNode(this.tail);
        this.tail.SetNextNode(this.head);
        return;
    }
    // 遍历找尾
    while(current_node.GetNextNode() != this.head){
        current_node = current_node.GetNextNode();
    }
    this.head.SetPreviousNode(current_node);
    this.SetTail(current_node);
    // 新增：尾节点next指向头节点
    this.tail.SetNextNode(this.head);
}

2. 修正InsertAtFront()方法 #

头部插入非空链表时，同步更新旧尾节点的next指针指向新头节点：

public void InsertAtFront(int data){
    Node new_node = new Node(data);
    if( new_node != null){
        if(this.head != null){
            this.head.SetPreviousNode(new_node);
            new_node.SetNextNode(this.head);
            new_node.SetPreviousNode(this.tail);
            // 新增：旧尾节点的next指向新的头节点
            this.tail.SetNextNode(new_node);
        }else{
            // 第一个节点自闭合
            new_node.SetNextNode(new_node);
            new_node.SetPreviousNode(new_node);
        }
        this.head = new_node;
        this.FindTail();
    }
    else{
        System.out.print("Sorry, the list is full!");
    }
}

3. 修正DisplayList()方法 #

适配循环链表的遍历逻辑，绕回头节点时终止：

public void DisplayList(){
    Node current_node = this.head;
    if(current_node == null){
        System.out.println("链表为空");
        return;
    }
    do{
        current_node.NodeDetails();
        current_node = current_node.GetNextNode();
    }while(current_node != this.head);
    // 输出闭环标识
    System.out.println("[回到头节点ID：" + this.head.GetId() +"]");
}

运行结果 #

修改后执行测试代码，输出为：
[Data: __ID = 0__ |{Previous: 4}, {Next: 4}] -> [Data: __ID = 4__ |{Previous: 0}, {Next: 0}] -> [回到头节点ID：0]
符合预期，ID为4的尾节点next指针正确指向头节点0。

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