| 上一篇 | 下一篇 |
|---|---|
| 单链表的两个核心缺点 |
目 录
- 单向循环链表（Circular Linked List）
- 1）什么是循环链表？
- 2）常用操作
- 2.1）初始化空循环链表
- 2.2）在末尾插入新节点
- 2.3）删除第一个值为 target 的节点
- 2.4）打印整个循环链表（避免死循环！）
- 3）完整示例程序
单向循环链表（Circular Linked List）
1）什么是循环链表？
循环链表是单链表的一种变形，其特点是：最后一个节点的next指针不再指向NULL，而是指向链表的第一个节点（或头节点），从而形成一个闭环结构（其余结构和操作方法和单链表很类似，只是为尾节点判断方式变了）。
主要特点：
- 无真正“尾部”：从任意节点出发，沿
next指针遍历，最终都会回到起点 - 空链表判断特殊：若使用带头节点的结构，空表满足
head->next == head - 适合循环场景：如约瑟夫问题、轮询调度、环形缓冲区等
2）常用操作
假设采用带哨兵头节点的单向循环链表（头节点不存有效数据，仅作起始标记），空表时
head->next = head。
2.1）初始化空循环链表
/** * @brief: initCircularList —— 创建并初始化一个带头节点的空循环链表 * @return: 指向头节点的指针；失败时返回 NULL * @note: 头节点 data 无意义，其 next 指向自身表示空表。 */ListNode*initCircularList(){ListNode*head=(ListNode*)malloc(sizeof(ListNode));if(head==NULL)returnNULL;// 没有空间，造成分配内存失败head->next=head;// 关键：空循环链表中，头节点指向自己returnhead;}2.2）在末尾插入新节点
/** * @brief: insertAtTail —— 在循环链表尾部插入新节点 * @param[in,out]: head - 链表头指针（不可为 NULL） * @param[in]: value - 要插入的数据 * @return: 成功返回 true，失败返回 false * @note: 尾部即头节点的前一个位置。时间复杂度 O(n)。 */boolinsertAtTail(ListNode*head,intvalue){if(head==NULL)returnfalse;// 创建新节点ListNode*newNode=(ListNode*)malloc(sizeof(ListNode));if(newNode==NULL)returnfalse;newNode->data=value;// 找到当前尾节点（即 head 的前驱）ListNode*tail=head;while(tail->next!=head){tail=tail->next;}// 插入新节点tail->next=newNode;newNode->next=head;// 新尾节点指向头，保持循环returntrue;}2.3）删除第一个值为 target 的节点
/** * @brief: deleteByValue —— 删除循环链表中第一个值等于 target 的节点 * @param[in,out]: head - 链表头指针（不可为 NULL） * @param[in]: target - 要删除的目标值 * @return: 成功删除返回 true，未找到返回 false * @note: 若删除后链表为空，则 head->next 仍指向 head。 */booldeleteByValue(ListNode*head,inttarget){if(head==NULL||head->next==head){returnfalse;// 空表}ListNode*prev=head;ListNode*current=head->next;// 遍历直到回到 headwhile(current!=head){if(current->data==target){prev->next=current->next;free(current);returntrue;}prev=current;current=current->next;}returnfalse;// 未找到}2.4）打印整个循环链表（避免死循环！）
/** * @brief: printCircularList —— 安全打印循环链表内容 * @param[in]: head - 链表头指针 * @return: 链表长度（不含头节点） * @note: 从 head->next 开始，遇到 head 停止，防止无限循环。 */intprintCircularList(ListNode*head){if(head==NULL||head->next==head){printf("循环链表为空。\n");return0;}printf("循环链表: ");ListNode*current=head->next;intcount=0;while(current!=head){printf("%d -> ",current->data);current=current->next;count++;}printf("(回到头)\n");returncount;}3）完整示例程序
#include<stdio.h>#include<stdlib.h>#include<stdbool.h>// 定义链表节点结构typedefstructListNode{intdata;structListNode*next;}ListNode;/** * @brief: initCircularList —— 创建并初始化一个带头节点的空循环链表 * @return: 指向头节点的指针；失败时返回 NULL * @note: 头节点 data 无意义，其 next 指向自身表示空表。 */ListNode*initCircularList(){ListNode*head=(ListNode*)malloc(sizeof(ListNode));if(head==NULL)returnNULL;head->next=head;// 关键：空循环链表中，头节点指向自己returnhead;}/** * @brief: insertAtTail —— 在循环链表尾部插入新节点 * @param[in,out]: head - 链表头指针（不可为 NULL） * @param[in]: value - 要插入的数据 * @return: 成功返回 true，失败返回 false * @note: 尾部即头节点的前一个位置。时间复杂度 O(n)。 */boolinsertAtTail(ListNode*head,intvalue){if(head==NULL)returnfalse;ListNode*newNode=(ListNode*)malloc(sizeof(ListNode));if(newNode==NULL)returnfalse;newNode->data=value;// 找到当前尾节点（即 head 的前驱）ListNode*tail=head;while(tail->next!=head){tail=tail->next;}// 插入新节点tail->next=newNode;newNode->next=head;// 新尾节点指向头，保持循环returntrue;}/** * @brief: deleteByValue —— 删除循环链表中第一个值等于 target 的节点 * @param[in,out]: head - 链表头指针（不可为 NULL） * @param[in]: target - 要删除的目标值 * @return: 成功删除返回 true，未找到返回 false * @note: 若删除后链表为空，则 head->next 仍指向 head。 */booldeleteByValue(ListNode*head,inttarget){if(head==NULL||head->next==head){returnfalse;// 空表}ListNode*prev=head;ListNode*current=head->next;// 遍历直到回到 headwhile(current!=head){if(current->data==target){prev->next=current->next;free(current);returntrue;}prev=current;current=current->next;}returnfalse;// 未找到}/** * @brief: printCircularList —— 安全打印循环链表内容 * @param[in]: head - 链表头指针 * @return: 链表长度（不含头节点） * @note: 从 head->next 开始，遇到 head 停止，防止无限循环。 */intprintCircularList(ListNode*head){if(head==NULL||head->next==head){printf("循环链表为空。\n");return0;}printf("循环链表: ");ListNode*current=head->next;intcount=0;while(current!=head){printf("%d -> ",current->data);current=current->next;count++;}printf("(回到头)\n");returncount;}/** * @brief: destroyCircularList —— 销毁整个循环链表并释放内存 * @param[in,out]: head - 链表头指针的地址 * @return: 无 * @note: 释放所有节点后将头指针置为 NULL。 */voiddestroyCircularList(ListNode**headRef){if(headRef==NULL||*headRef==NULL)return;ListNode*head=*headRef;if(head->next==head){// 空表，只释放头节点free(head);*headRef=NULL;return;}// 从第一个有效节点开始释放ListNode*current=head->next;while(current!=head){ListNode*next=current->next;free(current);current=next;}// 最后释放头节点free(head);*headRef=NULL;}// 主函数：完整示例intmain(){// 1. 初始化空循环链表ListNode*head=initCircularList();if(head==NULL){printf("初始化失败！\n");return-1;}printf("=== 初始化空链表 ===\n");printCircularList(head);// 2. 插入元素printf("\n=== 插入元素 10, 20, 30 ===\n");insertAtTail(head,10);insertAtTail(head,20);insertAtTail(head,30);intlen=printCircularList(head);printf("链表长度: %d\n",len);// 3. 删除中间元素printf("\n=== 删除元素 20 ===\n");if(deleteByValue(head,20)){printf("删除成功！\n");}else{printf("未找到要删除的元素。\n");}printCircularList(head);// 4. 删除不存在的元素printf("\n=== 尝试删除不存在的元素 99 ===\n");if(deleteByValue(head,99)){printf("删除成功！\n");}else{printf("未找到要删除的元素。\n");}printCircularList(head);// 5. 清理内存printf("\n=== 销毁链表 ===\n");destroyCircularList(&head);if(head==NULL){printf("链表已成功销毁。\n");}return0;}运行结果为
=== 初始化空链表 === 循环链表为空。 === 插入元素 10, 20, 30 === 循环链表: 10 -> 20 -> 30 -> (回到头) 链表长度: 3 === 删除元素 20 === 删除成功！ 循环链表: 10 -> 30 -> (回到头) === 尝试删除不存在的元素 99 === 未找到要删除的元素。 循环链表: 10 -> 30 -> (回到头) === 销毁链表 === 链表已成功销毁。提示：实际应用中，若频繁在尾部操作，可使用尾指针（rear）代替头指针，使尾部插入变为 O(1)。此时空表条件为
rear->next == rear。
