数据结构-单向循环链表

文章目录

• 简介
• Java 实现

单向循环链表，是在单向链表的基础上增加了循环这一个特性，单向循环链表可以使用两个结点，头结点和尾结点，但是如果只是用一个结点的话方便与两个单向循环链表的拼接

下方代码实现中实现了两个单向循环链表的拼接

逻辑思路

// 结点
class Node {
    int data;
    Node next = null;
}
// 单向循环链表
public class SinglyLinkedCircularList {
    // 头结点
    private Node head;
    
    // 初始化
    public SinglyLinkedCircularList() {
        head = new Node();
        head.next = head;
    }
    
    // 头插法创建单向循环链表（倒序）
    public void createFromHead(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node();
            node.data = arr[i];
            node.next = head.next;
            head.next = node;
        }
    }
    
    // 尾插法创建单向循环链表（正序）
    public void createFromTail(int[] arr) {
        Node h = head;
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node();
            node.data = arr[i];
            node.next = h.next;
            h.next = node;
            h = node;
        }
    }
    
    // 新增
    public void add(Node n) {
        Node h;
        for (h = head; h.next != head; h = h.next);
        n.next = h.next;
        h.next = n;
    }
    
    // 查找
    public void search(int num) {
        int k = 0;
        for (Node h = head; h.next != head; k++,h = h.next);
        if (num < 1 || num > k)
            throw new Exception("数字超过范围！");
        Node h = head;
        for (int i = 1; i <= num; i++,h = h.next);
        return h.data;
    }
    
    // 插入
    public void insert(int num, Node n) throws Exception {
        int k = 0;
        for (Node h = head; h.next != head; k++,h = h.next);
        if (num < 1 || num > k)
            throw new Exception("数字超过范围！");
        Node h = head;
        for (int i = 1; i < num; i++,h = h.next);
        n.next = h.next;
        h.next = n;
    }
    
    // 删除
    public int delete(int num) throws Exception {
        int k = 0;
        for (Node h = head; h.next != head; k++,h = h.next);
        if (num < 1 || num > k)
            throw new Exception("数字超过范围！");
        Node h = head;
        for (int i = 1; i < num; i++,h = h.next);
        int e = (h.next).data;
        h.next = (h.next).next;
        return e;
    }
    
    // 得到单向循环链表中结点个数
    public int getCapability() {
        int count = 0;
        for (Node h = head; h.next != head; count++,h = h.next);
        return count;
    }
    
    // 得到单链表头结点
    public Node getHead() {
        return head;
    }
    
    // 将新单向循环链表拼接到尾部
    public void spliceSinglyLinkedCircularList(SinglyLinkedCircularList slcl) {
        Node h;
        for (h = head; h.next != head; h = h.next);
        Node h2;
        for (h2 = slcl.getHead(); h2.next != slcl.getHead(); h2 = h2.next);
        h2.next = h.next;
        h.next = slcl.getHead();
    }
}