4.3 Java实现循环链表（完整代码及详细注释）

一.循环链表

什么是循环链表？顾名思义，就是收尾相连的链表，也就是说在这个链表里，任何节点都可能是头节点，也可以是尾节点。
为了简单理解，这里只演示单向循环链表。

1.单向循环链表

循环链表和单向链表基本没差别，无非就是将尾节点的next设置为头节点即可（注意这个点就理解了），也就是说单向循环链表的定义和单向链表的定义基本一致，只是多了一个标志，用于结束循环。

二.循环链表的实现

1.节点定义

package Exa04.CycleList;

import lombok.Data;

@Data
public class CycleListNode {

    //存储数据的变量
    private int data;
    //它存储了下一个节点对象引用
    private CycleListNode next;
    //节点名称
    private String nodeName;
    //是否头节点标识
    private boolean isHead = false;
    
    public CycleListNode(int data,String nodeName){
        this.data=data;
        if(nodeName==null){
            nodeName=""+data;
        }
        this.nodeName=nodeName;
    }
}

2.操作方法定义

package Exa04.CycleList;

import Exa04.OneNextList.ListNode;

public class CycleListAble {

    /**
     * 以输入节点为头，计算出链表长度
     * @param headNode 任意节点
     * @return 链表长度
     */
    static int ListLength(CycleListNode headNode){
        int length=0;
        CycleListNode currentNode=headNode;
        if(currentNode==null) return length;

        while (!currentNode.isHead()){
            headNode.setHead(true);
            currentNode=currentNode.getNext();
            length++;
        }
        headNode.setHead(false);
        return length;
    }

    /**
     * 遍历打印链表内容
     * @param headNode 链表头节点
     */
    static void Check(CycleListNode headNode){
        CycleListNode check=headNode;
        int size=ListLength(headNode);
        if(check==null){
            System.out.print("null");
            return;
        }
        for(int i=0;i<size+1;i++){
            System.out.print(check.getNodeName()+"->");
            check=check.getNext();
        }
    }

    /**
     * 此方法用于获得最后一个节点
     * @param headNode 头节点
     * @return 循环链表的最后一个节点
     */
    static CycleListNode getLastNode(CycleListNode headNode){
        CycleListNode currentNode=headNode;
        CycleListNode previousNode=headNode;
        if(currentNode==null) return null;
        while (!currentNode.isHead()){
            headNode.setHead(true);
            previousNode=currentNode;
            currentNode=currentNode.getNext();
        }
        headNode.setHead(false);
        return previousNode;
    }

    /**
     * 主要思路是：先判断链表中存不存在position位置，若没有输出错误信息并返回头节点；
     *      若存在则进行插入操作：首先判断position是不是为1，因为这种情况不同于其他的。
     *      否则，先找到第position-1个节点和position个节点，将前一个节点的下一节点设为nodeToInsert
     *      将nodeToInsert的下一个节点设置为position节点，这样完成插入操作
     * @param headNode 链表头节点
     * @param nodeToInsert 要插入的节点
     * @param position 指定插入的位置
     * @return 插入后的链表头节点
     */
    static CycleListNode Insert(CycleListNode headNode,CycleListNode nodeToInsert,int position) {
        if(headNode==null) {
            return nodeToInsert;
        }
        //获得输入链表的长度
        int size=ListLength(headNode);
        //判断链表内是否存在此位置
        if(position>size+1||position<1) {
            System.out.println("Position of node to insert is invalid.The valid inputs are 1 to"+(size+1));
            return headNode;
        }
        //在链表开头插入
        CycleListNode lastNode = getLastNode(headNode);
        if(position==1) {
            nodeToInsert.setNext(headNode);
            //让尾节点指向插入节点
            if(lastNode!=null)
                lastNode.setNext(nodeToInsert);
            return nodeToInsert;
            //在末尾插入
        }else if(position==size){
            //插入操作
            nodeToInsert.setNext(headNode);
            if(lastNode!=null)
                lastNode.setNext(nodeToInsert);
            //在中间插入
        }else{
            CycleListNode previousNode=headNode;
            int count=1;
            //找到那个位置的前一个节点
            while(count<position-1){
                //获得第position-1位置的节点
                previousNode=previousNode.getNext();
                count++;
            }
            //获得第position位置的节点
            CycleListNode currentNode = previousNode.getNext();
            //插入操作
            nodeToInsert.setNext(currentNode);
            previousNode.setNext(nodeToInsert);
        }
        return headNode;
    }

    /**
     * 方法和前面的插入方法有异曲同工之妙：
     *  主要思想是找到position的前一个节点和后一个节点，然后将他们连接
     * @param headNode 头节点
     * @param position 删除的位置
     * @return 删除后的链表头节点
     */
    static CycleListNode Delete(CycleListNode headNode,int position){
        if(headNode==null) return null;
        int size = ListLength(headNode);
        if(position>size||position<1) {
            System.out.println("Position of node to delete is invalid. The valid inputs are 1 to"+size);
            return headNode;
        }
        CycleListNode lastNode=getLastNode(headNode);
        //删除表头
        if(position==1){
            assert lastNode != null;
            lastNode.setNext(headNode.getNext());
            return headNode.getNext();
            //删除中间或结尾节点
        }else{
            CycleListNode previousNode=headNode;
            int count =1;
            //获得目标节点的上一个节点
            while(count<position-1) {
                previousNode = previousNode.getNext();
                count++;
            }
            //要删除目标节点
            CycleListNode currentNode = previousNode.getNext();
            previousNode.setNext(currentNode.getNext());
        }
        return headNode;
    }
}

三.循环链表测试

1.首先编写循环链表自动生成方法

/**
 * 自动随机创建循环链表，用于测试
 * @param length 链表长度
 * @param min 链表最小值
 * @param max 链表最大值
 * @return 生成的循环链表
 */
public static CycleListNode generatorCycleList(int length,int min,int max){
    CycleListNode headNode = null;
    CycleListNode nextNode=null;
    for(int i=0;i<length;i++){
        int num=numberGenerator(min,max);
        if(headNode==null){
            headNode= new CycleListNode(num,null);
            nextNode=headNode;
        }else{
            CycleListNode node=new CycleListNode(num,null);
            nextNode.setNext(node);
            nextNode=node;
            if(i==length-1){
                node.setNext(headNode);
            }
        }
    }
    return headNode;
}

2.然后进行测试用例编写

package Exa04.CycleList;

import Exa04.Util.ITestDemo;
import Exa04.Util.ListGenerator;
import org.junit.Test;

public class TestDemo implements ITestDemo {
    @Override
    @Test
    public void LengthTest() {
        CycleListNode cycleListNode= ListGenerator.generatorCycleList(10,1,18);
        System.out.println("循环链表长度如下：");
        System.out.println(CycleListAble.ListLength(cycleListNode));
        CycleListAble.Check(cycleListNode);
    }

    @Override
    @Test
    public void InsertTest() {
        CycleListNode cycleListNode= ListGenerator.generatorCycleList(10,1,18);
        System.out.println("循环链表长度如下：");
        System.out.println(CycleListAble.ListLength(cycleListNode));
        CycleListAble.Check(cycleListNode);
        System.out.println();
        System.out.println("插入操作：");
        CycleListNode test1=new CycleListNode(23,null);
        cycleListNode=CycleListAble.Insert(cycleListNode,test1,1);
        CycleListAble.Check(cycleListNode);
        System.out.println();
    }

    @Override
    @Test
    public void DeleteTest() {
        CycleListNode cycleListNode= ListGenerator.generatorCycleList(10,1,18);
        System.out.println("循环链表长度如下：");
        System.out.println(CycleListAble.ListLength(cycleListNode));
        CycleListAble.Check(cycleListNode);
        System.out.println();
        System.out.println("删除操作：");
        cycleListNode=CycleListAble.Delete(cycleListNode,1);
        CycleListAble.Check(cycleListNode);
    }
}

最后，就可以进行各种场景的测试与进一步学习了！！

原文链接：https://blog.csdn.net/c1776167012/article/details/122331281