Java 中的循环链表实现 | Baeldung中文网

1. 简介

本文将手把手带你实现一个循环链表（Circular Linked List）——一种特殊的链表结构。我们不仅会讲解其核心特性，还会完成插入、查找、删除和遍历等常见操作的 Java 实现。

如果你在面试或实际开发中遇到过环形缓冲区、任务调度器这类需求，那循环链表就是背后的常用数据结构之一，值得好好掌握。

2. 什么是循环链表

循环链表是链表的一种变体，它的最后一个节点不再指向 null，而是指回头节点（head），形成一个闭环。

✅ 与普通单向链表相比，它有以下几个优势：

任意节点都可以作为起点进行遍历，没有真正的“头”或“尾”概念
整个链表可以从任何一个节点开始访问，灵活性更高
在实现队列（Queue）时特别方便，入队出队操作更高效
**从尾节点跳转到头节点的时间复杂度为 O(1)**，而普通链表需要从头重新遍历（O(n)）

⚠️ 注意：虽然结构上形成了环，但我们仍然维护 head 和 tail 指针来简化操作。

3. Java 实现

先定义一个内部类 Node，用于存储整数值和下一个节点的引用：

class Node {
    int value;
    Node nextNode;

    public Node(int value) {
        this.value = value;
    }
}

接着创建主类 CircularLinkedList，维护头尾指针：

public class CircularLinkedList {
    private Node head = null;
    private Node tail = null;

    // 后续方法将在这里实现
}

接下来我们逐个实现核心操作。

3.1 插入元素

插入新节点时需要处理两种情况：

✅ 链表为空：新节点既是 head 也是 tail
✅ 链表非空：将当前 tail 的 nextNode 指向新节点，然后更新 tail

关键点：每次插入后，tail.nextNode 都要指向 head，保持闭环。

public void addNode(int value) {
    Node newNode = new Node(value);

    if (head == null) {
        head = newNode;
    } else {
        tail.nextNode = newNode;
    }

    tail = newNode;
    tail.nextNode = head;
}

测试一下构造一个链表：

private CircularLinkedList createCircularLinkedList() {
    CircularLinkedList cll = new CircularLinkedList();

    cll.addNode(13);
    cll.addNode(7);
    cll.addNode(24);
    cll.addNode(1);
    cll.addNode(8);
    cll.addNode(37);
    cll.addNode(46);

    return cll;
}

最终结构如下图所示（假设 head=13, tail=46）：

[13] -> [7]  -> [24] -> [1] -> [8] -> [37] -> [46]
 ^                                         |
 |_________________________________________|

3.2 查找元素

查找逻辑很简单：从 head 出发，沿着 nextNode 一路往下走，直到再次回到 head。

⚠️ 由于是环形结构，必须用 do-while 循环确保至少走一圈，避免空指针。

public boolean containsNode(int searchValue) {
    Node currentNode = head;

    if (head == null) {
        return false;
    } else {
        do {
            if (currentNode.value == searchValue) {
                return true;
            }
            currentNode = currentNode.nextNode;
        } while (currentNode != head);
        return false;
    }
}

配套单元测试验证正确性：

@Test
public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(8));
    assertTrue(cll.containsNode(37));
}

@Test
public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() {
    CircularLinkedList cll = createCircularLinkedList();

    assertFalse(cll.containsNode(11));
}

3.3 删除元素

删除操作稍微复杂，需要考虑三种特殊情况：

情况	处理方式
❌ 链表为空	直接返回
✅ 删除唯一节点	`head = tail = null`
✅ 删除头节点	将 `head.nextNode` 设为新的 `head`
✅ 删除尾节点	更新 `tail` 为被删节点的前驱

实现时我们通过判断 currentNode.nextNode.value 是否等于目标值，来定位待删除节点及其前驱。

public void deleteNode(int valueToDelete) {
    Node currentNode = head;
    if (head == null) {
        return;
    }
    do {
        Node nextNode = currentNode.nextNode;
        if (nextNode.value == valueToDelete) {
            if (tail == head) {
                head = null;
                tail = null;
            } else {
                currentNode.nextNode = nextNode.nextNode;
                if (head == nextNode) {
                    head = head.nextNode;
                }
                if (tail == nextNode) {
                    tail = currentNode;
                }
            }
            break;
        }
        currentNode = nextNode;
    } while (currentNode != head);
}

测试覆盖各种删除顺序和边界情况：

@Test
public void givenACircularLinkedList_WhenDeletingInOrderHeadMiddleTail_ThenListDoesNotContainThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(13));
    cll.deleteNode(13);
    assertFalse(cll.containsNode(13));

    assertTrue(cll.containsNode(1));
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));

    assertTrue(cll.containsNode(46));
    cll.deleteNode(46);
    assertFalse(cll.containsNode(46));
}

@Test
public void givenACircularLinkedList_WhenDeletingInOrderTailMiddleHead_ThenListDoesNotContainThoseElements() {
    CircularLinkedList cll = createCircularLinkedList();

    assertTrue(cll.containsNode(46));
    cll.deleteNode(46);
    assertFalse(cll.containsNode(46));

    assertTrue(cll.containsNode(1));
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));

    assertTrue(cll.containsNode(13));
    cll.deleteNode(13);
    assertFalse(cll.containsNode(13));
}

@Test
public void givenACircularLinkedListWithOneNode_WhenDeletingElement_ThenListDoesNotContainTheElement() {
    CircularLinkedList cll = new CircularLinkedList();
    cll.addNode(1);
    cll.deleteNode(1);
    assertFalse(cll.containsNode(1));
}

3.4 遍历链表

遍历和查找类似，使用 do-while 循环从 head 开始，逐个打印节点值，直到回到起点。

public void traverseList() {
    Node currentNode = head;

    if (head != null) {
        do {
            System.out.print(currentNode.value + " ");
            currentNode = currentNode.nextNode;
        } while (currentNode != head);
        System.out.println(); // 换行
    }
}

调用 traverseList() 输出结果为：

13 7 24 1 8 37 46

4. 总结

本文完整实现了 Java 中的循环链表，涵盖了增删查改和遍历等核心操作。这种数据结构在以下场景中非常实用：

✅ 实现循环队列或环形缓冲区
✅ 多任务调度系统（如操作系统中的时间片轮转）
✅ 游戏开发中的角色轮转机制

虽然代码量不大，但指针操作容易踩坑，建议动手调试一遍加深理解。

示例代码已托管至 GitHub：https://github.com/baeldung/data-structures

Persistence

REST

Security