Java 数据结构与算法系列精讲之环形链表

概述

在本文中，我们将探讨环形链表的相关概念，以及如何使用Java语言实现环形链表的各种操作。我们将依次介绍以下几个部分：

• 环形链表的基本概念
• 环形链表的创建
• 环形链表的遍历
• 环形链表的插入、删除、查找等操作
• 环形链表的示例程序

环形链表的基本概念

链表是一种基本的数据结构，是由一组节点组成的序列，每个节点包含数据和指向下一节点的指针。链表的最后一个节点指向空地址NULL，可以用于表示链表的结束。但在环形链表中，最后一个节点不再指向 NULL，而是指向链表的第一个节点，形成了一个环形。

环形链表的创建

我们可以使用Java语言定义一个环形链表的节点Node，用class实现，包含数据值和指向下一节点的指针，如下所示：

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

然后我们可以定义一个环形链表的类CircularLinkedList，用来存储整个链表的头节点和尾节点，实现各种操作。具体实现如下：

class CircularLinkedList {
    Node head;
    Node tail;
    public CircularLinkedList() {
        head = null;
        tail = null;
    }
}

接下来，我们就可以通过往链表中添加节点的方式来实现链表的创建。在添加节点时，我们需要判断链表是不是空链表，然后逐个遍历找到尾节点，并把新节点添加到尾节点后面构成环形。具体代码实现如下：

public void add(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        tail = newNode;
        newNode.next = head;
    } else {
        tail.next = newNode;
        tail = newNode;
        tail.next = head;
    }
}

环形链表的遍历

遍历链表是常见的操作之一，我们需要从头节点开始，依次访问每个节点，直到尾节点为止。在遍历环形链表时，我们需要担心的是陷入死循环，因此我们可以设置一个循环标志来判断是否到达尾节点位置。代码实现如下：

public void traversal() {
    if (head == null) {
        System.out.println("Empty list...");
        return;
    }
    Node current = head;
    boolean flag = false;
    while (!flag) {
        System.out.print(current.data + " ");
        if (current == tail) {
            flag = true;
        }
        current = current.next;
    }
    System.out.println();
}

环形链表的插入、删除、查找等操作

环形链表的插入、删除、查找等操作与普通链表没有太大区别，具体实现如下：

在指定位置插入节点

public void insert(int index, int data) {
    if (index <= 0) {
        add(data);
    } else if (index > size()) {
        System.out.println("Insert failed, out of range...");
        return;
    } else {
        Node newNode = new Node(data);
        Node current = head;
        int count = 0;
        while (count < index - 1) {
            current = current.next;
            count++;
        }
        newNode.next = current.next;
        current.next = newNode;
    }
}

删除指定节点

public void remove(int index) {
    if (head == null) {
        System.out.println("Empty list...");
        return;
    }
    if (index <= 0) {
        head = head.next;
        tail.next = head;
    } else if (index >= size()) {
        System.out.println("Remove failed, out of range...");
        return;
    } else {
        Node current = head;
        int count = 0;
        while (count < index - 1) {
            current = current.next;
            count++;
        }
        current.next = current.next.next;
        if (index == size() - 1) {
            tail = current;
        }
    }
}

按照数据值查找节点

public Node search(int data) {
    if (head == null) {
        System.out.println("Empty list...");
        return null;
    }
    Node current = head;
    boolean flag = false;
    while (current != null) {
        if (current.data == data) {
            flag = true;
            break;
        }
        current = current.next;
        if (current == tail.next) {
            break;
        }
    }
    if (flag) {
        return current;
    } else {
        System.out.println("Node not found...");
        return null;
    }
}

环形链表的示例程序

我们可以使用环形链表来解决环状报数问题。问题描述：n个人围成一圈，从第一个人开始从1报数，报数到第m个人，然后出圈；接着从出圈的下一个人开始继续从1报数，报数到第m个人，再次出圈；重复进行直到所有人出圈为止。具体代码实现如下：

public static void counting(int n, int m) {
    CircularLinkedList list = new CircularLinkedList();
    for (int i = 1; i <= n; i++) {
        list.add(i);
    }
    Node current = list.head;
    while (current.next != current) {
        for (int i = 1; i < m; i++) {
            current = current.next;
        }
        System.out.print(current.data + " ");
        current = current.next;
        list.remove(current, current.data);
    }
    System.out.println("\nThe last one is: " + current.data);
}

以上就是环形链表的完整攻略，通过本文的阅读，您应该已经对环形链表的概念、创建、遍历和各种操作有了一定的了解。希望本文对您有所帮助。