Java数据结构与算法学习之循环链表

本文将详细介绍Java数据结构中的一种链表类型——循环链表，并讲解如何使用Java实现循环链表。同时，本文也提供了两个示例，方便读者更好地理解和运用循环链表。

什么是循环链表

循环链表是一种链表，它与单向链表和双向链表不同之处在于它的最后一个结点指向第一个结点。这就形成了一个循环链，因此称之为循环链表。

如何实现循环链表

在Java中，我们可以通过定义一个结点类来实现循环链表。具体的代码如下：

public class Node {
    public int data; // 数据域
    public Node next; // 指针域（指向下一个结点）

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

同时，我们也需要创建一个链表类，用于管理整个循环链表。链表类的定义如下：

public class CircularLinkedList {
    public Node head; // 头结点

    public CircularLinkedList() {
        this.head = null;
    }

    // 插入新的结点
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node current = head;
            while (current.next != head) {
                current = current.next;
            }
            current.next = newNode;
            newNode.next = head;
        }
    }

    // 删除指定数据的结点
    public void delete(int data) {
        if (head == null) {
            System.out.println("链表为空！");
            return;
        } else if (head.data == data) {
            head = head.next;
        } else {
            Node current = head;
            while (current.next != head) {
                if (current.next.data == data) {
                    current.next = current.next.next;
                    return;
                }
                current = current.next;
            }
            System.out.println("未找到指定数据的结点！");
        }
    }

    // 输出整个链表
    public void print() {
        if (head == null) {
            System.out.println("链表为空！");
        } else {
            Node current = head;
            do {
                System.out.print(current.data + " ");
                current = current.next;
            } while (current != head);
            System.out.println();
        }
    }
}

在这个链表类中，提供了三个方法：insert()、delete()和print()。分别用于插入新的结点、删除指定数据的结点和输出整个链表。

如何运用循环链表

循环链表可以用于很多场合，例如模拟环形动物队列、文件系统的循环链表等等。下面提供两个示例：

1.环形动物队列

在一个动物园中有10只猴子，现在要求按照顺序排名，从1到10。其中如果第一只猴子数到5，那么就离开队列，依次类推，直到只剩下最后一只猴子。那么我们可以利用循环链表来模拟这个过程。

public static void monkeyQueue() {
    CircularLinkedList list = new CircularLinkedList();
    for (int i = 1; i <= 10; i++) {
        list.insert(i);
    }
    Node current = list.head;
    int count = 0;
    while (current.next != current) {
        count++;
        if (count == 5) {
            list.delete(current.next.data);
            count = 0;
        } else {
            current = current.next;
        }
    }
    System.out.println("最后剩下的猴子编号为：" + current.data);
}

2.文件系统循环链表

在文件系统中，文件和目录之间的关系就是树形结构。而在这个结构中，文件夹内的内容列表就可以使用循环链表来实现。

public class FileNode {
    public String name;
    public boolean isFile;
    public FileNode nextFile;

    public FileNode(String name, boolean isFile) {
        this.name = name;
        this.isFile = isFile;
        this.nextFile = null;
    }
}

public class FolderNode {
    public String name;
    public FileNode firstFile;
    public FolderNode nextFolder;

    public FolderNode(String name) {
        this.name = name;
        this.firstFile = null;
        this.nextFolder = null;
    }

    public void addFile(String name, boolean isFile) {
        FileNode file = new FileNode(name, isFile);
        if (firstFile == null) {
            firstFile = file;
            file.nextFile = firstFile;
        } else {
            FileNode current = firstFile;
            while (current.nextFile != firstFile) {
                current = current.nextFile;
            }
            current.nextFile = file;
            file.nextFile = firstFile;
        }
    }

    public void print() {
        System.out.println(name + ": ");
        if (firstFile != null) {
            FileNode current = firstFile;
            do {
                System.out.println("- " + current.name);
                current = current.nextFile;
            } while (current != firstFile);
        }
        if (nextFolder != null) {
            nextFolder.print();
        }
    }
}

public class FileSystem {
    private FolderNode root;

    public FileSystem() {
        this.root = new FolderNode("Root");
    }

    public void addFolder(String path) {
        String[] dirs = path.split("/");
        FolderNode current = root;
        for (String dir : dirs) {
            if (dir.equals("")) {
                continue;
            }
            boolean isFound = false;
            if (current.nextFolder != null) {
                FolderNode temp = current.nextFolder;
                do {
                    if (temp.name.equals(dir)) {
                        current = temp;
                        isFound = true;
                        break;
                    }
                    temp = temp.nextFolder;
                } while (temp != current.nextFolder);
            }
            if (!isFound) {
                FolderNode folder = new FolderNode(dir);
                if (current.nextFolder == null) {
                    current.nextFolder = folder;
                    folder.nextFolder = folder;
                } else {
                    FolderNode temp = current.nextFolder;
                    while (temp.nextFolder != current.nextFolder) {
                        temp = temp.nextFolder;
                    }
                    temp.nextFolder = folder;
                    folder.nextFolder = current.nextFolder;
                }
                current = folder;
            }
        }
    }

    public void print() {
        root.print();
    }
}

在这个文件系统中，可以添加文件夹和文件，同时也支持输出整个文件系统的内容列表。

总结

循环链表是Java数据结构中的一种链表类型，它集合了单向链表和双向链表的优点。通过定义结点类和链表类，我们可以方便地创建和管理循环链表。同时，循环链表也可以被运用到很多实际问题中，例如环形动物队列和文件系统的内容列表。