每日算法 — 使用java实现环形链表：循环结构与双向循环链表

算法概述

环形链表（Circular Linked List）是一种首尾相连的链式数据结构，最后一个节点的next指针指向头节点而非null。这种结构天然适合处理循环队列、轮转调度、圆桌问题等场景。本文用Java实现单向环形链表与双向循环链表，涵盖插入、删除、遍历、约瑟夫问题求解等核心操作，并对比两种结构的时空效率差异。

核心原理

单向环形链表中，尾节点的next指向头节点，形成单向循环。双向循环链表中，头节点的prev指向尾节点，尾节点的next指向头节点，支持双向遍历。核心挑战在于维护循环结构的一致性，尤其是在边界操作（插入到空表、删除唯一节点）时避免断链。

完整Java实现

/**
 * 单向环形链表节点
 */
class CircularNode {
    int data;
    CircularNode next;
    CircularNode(int data) { this.data = data; }
}

/**
 * 双向循环链表节点
 */
class DlCircularNode {
    int data;
    DlCircularNode prev, next;
    DlCircularNode(int data) { this.data = data; }
}

/**
 * 单向环形链表实现
 */
class SinglyCircularList {
    CircularNode tail; // 指向尾节点，可O(1)访问首尾
    int size;

    public void append(int data) {
        CircularNode node = new CircularNode(data);
        if (tail == null) {
            node.next = node; // 自环
            tail = node;
        } else {
            node.next = tail.next; // 新节点指向头
            tail.next = node;      // 原尾指向新节点
            tail = node;
        }
        size++;
    }

    public void prepend(int data) {
        CircularNode node = new CircularNode(data);
        if (tail == null) {
            node.next = node;
            tail = node;
        } else {
            node.next = tail.next;
            tail.next = node;
        }
        size++;
    }

    public boolean remove(int data) {
        if (tail == null) return false;
        CircularNode curr = tail.next, prev = tail;
        do {
            if (curr.data == data) {
                if (curr == tail && curr.next == tail) {
                    tail = null; // 唯一节点
                } else {
                    prev.next = curr.next;
                    if (curr == tail) tail = prev;
                }
                size--;
                return true;
            }
            prev = curr;
            curr = curr.next;
        } while (curr != tail.next);
        return false;
    }

    public void print() {
        if (tail == null) return;
        CircularNode curr = tail.next;
        do {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        } while (curr != tail.next);
        System.out.println("(head)");
    }

    /**
     * 约瑟夫问题求解：每数到k的人出列，求最后幸存者
     * 使用环形链表模拟，时间O(n*k)，空间O(n)
     */
    public int josephus(int k) {
        if (tail == null || k <= 0) return -1;
        CircularNode curr = tail.next;
        while (size > 1) {
            // 前进k-1步（curr本身算第1个）
            for (int i = 1; i < k - 1; i++) {
                curr = curr.next;
            }
            // 删除curr.next
            CircularNode toRemove = curr.next;
            curr.next = toRemove.next;
            if (toRemove == tail) tail = curr;
            size--;
            curr = curr.next;
        }
        return curr.data;
    }
}

/**
 * 双向循环链表实现
 */
class DoublyCircularList {
    DlCircularNode head; // 哨兵节点
    int size;

    public DoublyCircularList() {
        head = new DlCircularNode(-1);
        head.prev = head.next = head;
    }

    public void append(int data) {
        DlCircularNode node = new DlCircularNode(data);
        node.prev = head.prev;
        node.next = head;
        head.prev.next = node;
        head.prev = node;
        size++;
    }

    public void insertAfter(DlCircularNode target, int data) {
        DlCircularNode node = new DlCircularNode(data);
        node.next = target.next;
        node.prev = target;
        target.next.prev = node;
        target.next = node;
        size++;
    }

    public void remove(DlCircularNode node) {
        if (size == 0 || node == head) return;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    public void printForward() {
        DlCircularNode curr = head.next;
        while (curr != head) {
            System.out.print(curr.data + " <-> ");
            curr = curr.next;
        }
        System.out.println("(head)");
    }

    public void printBackward() {
        DlCircularNode curr = head.prev;
        while (curr != head) {
            System.out.print(curr.data + " <-> ");
            curr = curr.prev;
        }
        System.out.println("(head)");
    }
}

public class CircularLinkedList {
    public static void main(String[] args) {
        // 单向环形链表测试
        SinglyCircularList scl = new SinglyCircularList();
        for (int i = 1; i <= 7; i++) scl.append(i);
        System.out.print("单向环形链表: ");
        scl.print();
        System.out.println("约瑟夫问题(k=3): 幸存者 = " + scl.josephus(3));

        // 双向循环链表测试
        DoublyCircularList dcl = new DoublyCircularList();
        for (int i = 1; i <= 5; i++) dcl.append(i);
        System.out.print("双向循环链表(正向): ");
        dcl.printForward();
        System.out.print("双向循环链表(反向): ");
        dcl.printBackward();
    }
}

复杂度分析

*单向环形链表删除已知节点需先找到其前驱

应用场景

• 操作系统进程调度：轮转调度（Round-Robin）使用时间片轮转的循环队列
• 音乐播放器循环播放：播放列表的上一首/下一首在循环链表中天然支持
• 约瑟夫问题：经典的数学淘汰问题，环形链表是最直观的模拟结构
• 多人游戏轮流机制：环形链表维护玩家顺序，支持顺时针/逆时针轮转
• 缓冲区循环复用：如内核中的环形缓冲区（ring buffer）管理