微信登录

链表 - 循环链表 - 循环链表的结构与使用

链表 - 循环链表 - 循环链表的结构与使用

一、引言

在数据结构的世界里，链表是一种基础且重要的线性数据结构。而循环链表作为链表的一种特殊形式，有着独特的结构和广泛的应用场景。本文将深入探讨循环链表的结构特点、实现方式以及实际应用，帮助大家更好地理解和运用这一数据结构。

二、链表基础回顾

在正式介绍循环链表之前，我们先来简单回顾一下普通链表的基本概念。链表是由一系列节点组成的数据结构，每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，而指针域则指向下一个节点的地址。通过这种方式，节点之间形成了一种链式的连接关系。

普通链表的最后一个节点的指针域通常指向 NULL，表示链表的结束。例如，一个简单的整数链表可能如下所示：

  1. [1] -> [2] -> [3] -> NULL

三、循环链表的结构特点

循环链表与普通链表的主要区别在于，它的最后一个节点的指针域不是指向 NULL，而是指向链表的第一个节点，从而形成一个封闭的循环。根据链表是否为单链表或双链表，循环链表也可以分为单向循环链表和双向循环链表。

1. 单向循环链表

单向循环链表中，每个节点只有一个指针域，指向下一个节点。最后一个节点的指针域指向头节点。其结构示意图如下：

  1. [1] -> [2] -> [3]
  2.  ^             |
  3.  |_____________|

2. 双向循环链表

双向循环链表中，每个节点有两个指针域，一个指向前一个节点，另一个指向后一个节点。头节点的前一个指针指向尾节点，尾节点的后一个指针指向头节点。其结构示意图如下：

  1.   <-> [1] <-> [2] <-> [3] <->
  2.    ^                      |
  3.    |______________________|

四、循环链表的实现

1. 单向循环链表的实现（Python 示例）

  1. # 定义节点类
  2. class Node:
  3.     def __init__(self, data):
  4.         self.data = data
  5.         self.next = None
  7. # 定义单向循环链表类
  8. class CircularLinkedList:
  9.     def __init__(self):
  10.         self.head = None
  12.     # 在链表尾部插入新节点
  13.     def append(self, data):
  14.         new_node = Node(data)
  15.         if not self.head:
  16.             self.head = new_node
  17.             new_node.next = self.head
  18.         else:
  19.             current = self.head
  20.             while current.next!= self.head:
  21.                 current = current.next
  22.             current.next = new_node
  23.             new_node.next = self.head
  25.     # 遍历链表
  26.     def display(self):
  27.         if not self.head:
  28.             return
  29.         current = self.head
  30.         while True:
  31.             print(current.data, end=" ")
  32.             current = current.next
  33.             if current == self.head:
  34.                 break
  35.         print()
  37. # 使用示例
  38. cll = CircularLinkedList()
  39. cll.append(1)
  40. cll.append(2)
  41. cll.append(3)
  42. cll.display()  # 输出: 1 2 3

2. 双向循环链表的实现（Python 示例）

  1. # 定义双向节点类
  2. class DoubleNode:
  3.     def __init__(self, data):
  4.         self.data = data
  5.         self.prev = None
  6.         self.next = None
  8. # 定义双向循环链表类
  9. class DoublyCircularLinkedList:
  10.     def __init__(self):
  11.         self.head = None
  13.     # 在链表尾部插入新节点
  14.     def append(self, data):
  15.         new_node = DoubleNode(data)
  16.         if not self.head:
  17.             self.head = new_node
  18.             new_node.next = new_node
  19.             new_node.prev = new_node
  20.         else:
  21.             last = self.head.prev
  22.             last.next = new_node
  23.             new_node.prev = last
  24.             new_node.next = self.head
  25.             self.head.prev = new_node
  27.     # 遍历链表
  28.     def display(self):
  29.         if not self.head:
  30.             return
  31.         current = self.head
  32.         while True:
  33.             print(current.data, end=" ")
  34.             current = current.next
  35.             if current == self.head:
  36.                 break
  37.         print()
  39. # 使用示例
  40. dccl = DoublyCircularLinkedList()
  41. dccl.append(1)
  42. dccl.append(2)
  43. dccl.append(3)
  44. dccl.display()  # 输出: 1 2 3

五、循环链表的应用场景

1. 约瑟夫斯问题

约瑟夫斯问题是一个经典的问题，描述了 n 个人围成一圈，从某个人开始报数，报到 m 的人出列，然后从出列的下一个人重新开始报数，直到所有人都出列。使用循环链表可以很方便地解决这个问题。

  1. class Node:
  2.     def __init__(self, data):
  3.         self.data = data
  4.         self.next = None
  6. def josephus_problem(n, m):
  7.     # 创建循环链表
  8.     head = Node(1)
  9.     current = head
  10.     for i in range(2, n + 1):
  11.         new_node = Node(i)
  12.         current.next = new_node
  13.         current = new_node
  14.     current.next = head
  16.     # 开始报数
  17.     prev = current
  18.     current = head
  19.     while current.next!= current:
  20.         for i in range(m - 1):
  21.             prev = current
  22.             current = current.next
  23.         print(f"出列的人是: {current.data}")
  24.         prev.next = current.next
  25.         current = prev.next
  27.     print(f"最后剩下的人是: {current.data}")
  29. # 使用示例
  30. josephus_problem(5, 3)

2. 操作系统的进程调度

在操作系统中，进程调度算法有时会使用循环链表来管理多个进程。每个进程可以看作是链表中的一个节点，调度器按照循环链表的顺序依次选择进程执行，从而实现公平的进程调度。

六、总结

类型 结构特点 优点 缺点 应用场景
单向循环链表 每个节点只有一个指针域，最后一个节点指向头节点 实现简单，节省空间 只能单向遍历 约瑟夫斯问题等
双向循环链表 每个节点有两个指针域，头节点和尾节点相互指向 可以双向遍历，操作更灵活 占用更多空间，实现相对复杂 操作系统进程调度等

循环链表作为一种特殊的链表结构，在某些场景下具有独特的优势。通过本文的介绍，相信大家对循环链表的结构和使用有了更深入的了解。在实际应用中，可以根据具体的需求选择合适的链表类型，以提高程序的效率和性能。