Java实现单向循环链表

准备节点类，节点类中只有一个int类型的数据域和一个指针：

/**
 * 单链表节点
 */
public class Node
{
    private int data;//数据域
    private Node next;//指向下一个节点

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    //构造函数
    public Node(int data, Node next){
        this.data = data;
        this.next = next;
    }
    public Node(int data){
        this(data,null);
    }
    public Node(){
        this(0,null);
    }

}

 具体实现：

  1 /**
  2  * Java实现单向循环链表
  3  * Author：hangwei
  4  * 2022/11
  5  */
  6 public class LinkedList {
  7     public Node getHead() {
  8         return head;
  9     }
 10 
 11     private Node head;
 12 
 13     public Node getTail() {
 14         return tail;
 15     }
 16 
 17     private Node tail;
 18     private int size;
 19 
 20     public LinkedList(){
 21         tail = head = null;
 22         size = 0;
 23     }
 24 
 25     /**
 26      * 在单向循环链表的任意位置之后新增一个节点
 27      * @param position 新增的位置，即新增节点的上一个节点
 28      * @param target 新增节点
 29      */
 30     public void addNode(Node position,Node target){
 31         if(target == null)
 32             return;
 33         if (size == 0) {
 34             target.setNext(target);
 35             tail = head = target;
 36         } else if (position == null) {//position为空就在链表尾部添加新节点
 37             tail.setNext(target);//尾节点的下一个节点是新节点
 38             target.setNext(head);//新节点的下一个节点是头节点
 39             //标记新的尾节点
 40             tail = target;
 41         } else {
 42             target.setNext(position.getNext());//原来position节点的下一个节点变成target的下一个节点
 43             position.setNext(target);
 44             if(size == 1 || position == tail)//标记新的尾节点
 45                 tail = target;
 46         }
 47         size++;
 48     }
 49 
 50     //备用：在链表的头部增加节点（新增节点始终是头节点）
 51     public void addHead(Node hd){
 52         if(hd == null)
 53             return;
 54         if(size == 0){
 55             hd.setNext(hd);//下一个节点即是自己
 56             tail = head = hd;
 57         }
 58         else {
 59             hd.setNext(head);//新节点的下一个节点是头
 60             tail.setNext(hd);//尾节点的下一个节点是新节点
 61             //标记新的头节点；
 62             head = hd;
 63         }
 64         size++;
 65     }
 66 
 67     //备用：在链表的尾部增加节点(新增节点始终是尾节点）
 68     public void addTail(Node tl){
 69         if(tl == null)
 70             return;
 71         if(size == 0){
 72             tl.setNext(tl);
 73             head = tail = tl;
 74         }
 75         else{
 76             tail.setNext(tl);//尾节点的下一个节点是新节点
 77             tl.setNext(head);//新节点的下一个节点是头节点
 78             //标记新的尾节点
 79             tail = tl;
 80         }
 81         size++;
 82     }
 83 
 84     /**
 85      * 删除链表中的任意节点
 86      * @param target 即将被删除的节点
 87      */
 88     public void deleteNode(Node target){
 89         if(size == 0 || target == null){
 90             System.out.println("null linked list ,can not delete.");
 91             return;
 92         }
 93         else if(size == 1){
 94             head = tail = null;
 95         }
 96         else {
 97             if(target == head){//如果目标是头节点
 98                 tail.setNext(head.getNext());
 99                 head = head.getNext();
100             }
101             else {
102                 //计算目标节点的上一个节点
103                 Node n = new Node();//n表示target节点的上一个节点
104                 n = head;
105                 while (n.getNext() != tail) {//可以看到这里：当想要求解单向链表中的某个非头/尾节点时始终涉及到遍历
106                     if (n.getNext() == target)
107                         break;
108                     n = n.getNext();
109                 }
110                 n.setNext(target.getNext());
111                 if(target == tail)//如果目标是尾节点
112                     tail = n;//标记新的尾节点
113             }
114         }
115         size--;
116     }
117 
118     //打印链表
119     public void print(){
120         Node node = new Node();
121         node = head;
122         while (node.getNext() != head && node.getNext() != null){//遍历
123             System.out.print(node.getData());
124             System.out.print("->");
125             node = node.getNext();
126         }
127         System.out.print(node.getData());//补充打印循环体的最后一个节点
128         System.out.print("->");
129         //最后打印出头节点
130         System.out.print(head.getData());
131         System.out.println();
132     }
133 }

测试类：

public class Test {
    public static void main(String[] args) {
        LinkedList ll = new LinkedList();
        ll.addNode(null,new Node(0));
        ll.print();
        ll.addNode(null,new Node(1));
        ll.addNode(null,new Node(2));
        ll.addNode(null,new Node(3));
        ll.print();
        ll.addNode(ll.getHead().getNext(),new Node(4));
        ll.print();
        ll.deleteNode(ll.getHead().getNext().getNext());
        ll.print();
        ll.deleteNode(ll.getHead());
        ll.print();
        ll.deleteNode(ll.getTail());
        ll.print();
    }
}

输出结果：

*重点：链表在查找节点时涉及的遍历问题（时间复杂度O(n))