資料結構-單向循環連結清單

文章目錄

• 簡介
• 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();
    }
}