当前位置：首页 > news >正文

数据结构：循环链表详解（从原理到实战，新手必看）

news 2026/5/12 11:04:00

在链表家族中，除了最基础的单链表和双链表，还有一种结构非常特殊且实用的类型 ——循环链表。它将单链表的首尾相连，让整个链表形成一个闭环，解决了普通单链表 “走到末尾就结束” 的局限，在环形缓冲区、约瑟夫环、操作系统时间片轮转等场景中被大量使用。

本文将从概念、结构特点、核心操作、C 语言完整实现到应用场景，带你彻底掌握循环链表。

一、什么是循环链表？

循环链表（Circular Linked List）是单链表的一种变体：

普通单链表：尾节点的next指针指向NULL
循环链表：尾节点的next指针重新指向头节点，整个链表形成一个环

核心特点

链表无明显的头和尾，从任意节点出发都能遍历全表
可以不使用头结点，也可以带哨兵头结点（更常用）
遍历时终止条件不再是p == NULL，而是p == head
插入、删除逻辑与单链表类似，但边界判断更简洁

二、循环链表的结构体定义（C 语言）

我们使用带头结点的循环链表，方便统一处理空表和非空表逻辑。

#include <stdio.h> #include <stdlib.h> #include <assert.h> // 节点结构体 typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } Node; // 链表类型重定义（指向头结点） typedef Node* CList;

三、初始化循环链表

创建一个头结点，并让头结点自环，代表空链表。

// 初始化循环链表 void InitList(CList *head) { *head = (Node*)malloc(sizeof(Node)); assert(*head != NULL); // 自环，空循环链表 (*head)->next = *head; }

四、插入操作（尾插法）

尾插是循环链表最常用的插入方式，找到尾节点后插入新节点，并保持环结构。

// 尾插法插入元素 bool InsertTail(CList head, int val) { assert(head != NULL); Node *newNode = (Node*)malloc(sizeof(Node)); assert(newNode != NULL); newNode->data = val; newNode->next = head; // 新节点指向头结点 // 找尾节点 Node *p = head; while (p->next != head) { p = p->next; } p->next = newNode; return true; }

五、遍历循环链表

因为是环，不能用 p == NULL 结束，而是回到头结点就停止。

// 遍历打印循环链表 void ShowList(CList head) { assert(head != NULL); Node *p = head->next; while (p != head) { printf("%d ", p->data); p = p->next; } printf("\n"); }

六、删除指定值的节点

找到待删节点的前驱，修改指针，保持环不断裂。

// 删除第一个值为 val 的节点 bool DeleteVal(CList head, int val) { assert(head != NULL); Node *prev = head; Node *cur = head->next; while (cur != head) { if (cur->data == val) { prev->next = cur->next; free(cur); return true; } prev = cur; cur = cur->next; } // 没找到 return false; }

七、判断链表是否为空

bool IsEmpty(CList head) { return head->next == head; }

八、销毁循环链表

因为是环，要逐个节点释放，最后释放头结点。

void DestroyList(CList *head) { if (*head == NULL) return; Node *p = (*head)->next; Node *q = NULL; while (p != *head) { q = p->next; free(p); p = q; } free(*head); *head = NULL; }