Python数据结构之循环链表详解

1. 循环链表概述

在计算机科学中，循环链表是一种链式数据结构，其中的尾元素指向头部元素，形成一个环形结构。循环链表可以解决带头节点的单链表在链表尾部插入和删除结点时时间复杂度为O(n)的问题，使得操作的时间复杂度为O(1)。

2. 循环链表的实现

2.1 循环链表的结点

类似于单链表，循环链表也是由结点构成的，结点中至少要存储下一个结点的地址（指针）。另外，由于循环链表的特性，还需要存储指向前一个结点的指针。

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

2.2 循环链表的常见操作

2.2.1 创建空的循环链表

class CircularLinkedList:
    def __init__(self):
        node = Node(None)
        node.next = node
        node.prev = node
        self.head = node
        self.count = 0

2.2.2 在循环链表头部插入结点

class CircularLinkedList:
    ...
    def add_first(self, val):
        node = Node(val)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.count += 1

2.2.3 在循环链表尾部插入结点

class CircularLinkedList:
    ...
    def add_last(self, val):
        node = Node(val)
        node.next = self.head
        node.prev = self.head.prev
        self.head.prev.next = node
        self.head.prev = node
        self.count += 1

2.2.4 删除指定值的结点

class CircularLinkedList:
    ...
    def remove(self, val):
        node = self.head.next
        while node != self.head:
            if node.val == val:
                node.prev.next = node.next
                node.next.prev = node.prev
                self.count -= 1
                return
            node = node.next

3. 循环链表示例

3.1 Josephus问题

Josephus问题是一个经典的问题，它的大致思想是：一群人手牵手围成一个圈，从某个人开始报数，然后数到特定的数字的人出列，然后从下一个人开始重新报数，循环执行直到剩下一人为止。

通过使用循环链表可以轻易地解决这个问题。

def josephus(n, m):
    # 创建循环链表，并往里面添加n个人（以数字1~n表示）
    cir_list = CircularLinkedList()
    for i in range(1, n+1):
        cir_list.add_last(i)
    # 开始游戏，直到只剩下最后一个人
    node = cir_list.head.next
    while cir_list.count > 1:
        for i in range(m-1):
            node = node.next
        node.prev.next = node.next
        node.next.prev = node.prev
        cir_list.count -= 1
        node = node.next
    return node.val

3.2 构建浏览器的"前进"和"后退"功能

浏览器的"前进"和"后退"功能可以使用双向链表或者循环链表来实现。其中，以循环链表为例：

class Browser:
    def __init__(self):
        self.forward_list = CircularLinkedList()
        self.backward_list = CircularLinkedList()
    def forward(self):
        node = self.forward_list.head.next
        if node != self.forward_list.head:
            self.forward_list.remove(node.val)
            self.backward_list.add_last(node.val)
            return node.val
        else:
            return None
    def backward(self):
        node = self.backward_list.head.next
        if node != self.backward_list.head:
            self.backward_list.remove(node.val)
            self.forward_list.add_last(node.val)
            return node.val
        else:
            return None

4. 总结

循环链表是一种非常实用的数据结构，常见的应用场景包括约瑟夫问题、浏览器的"前进"和"后退"功能等。在实现循环链表过程中，需要着重考虑指向前一个结点的指针和循环特性。