单向循环链表：原理与核心操作实现
概述
单向循环链表是链式存储结构的特殊形式，其尾节点的指针域不再指向NULL，而是回绕到头节点，形成逻辑上的环形结构。这种设计消除了传统单链表的方向性限制，使得从任意节点出发均可访问整个链表。
存储结构对比分析
1. 内存分配策略
顺序存储结构需要预先申请连续内存空间，容量固定；而单向循环链表采用动态节点分配，各节点物理位置离散，通过指针建立逻辑关联，容量可弹性扩展。
2. 时间复杂度表现
- 查找操作：顺序存储支持O(1)随机访问；单向循环链表需顺序遍历，平均时间复杂度为O(n)
- 增删操作：顺序存储需移动大量元素，平均O(n)；单向循环链表在定位后仅需修改指针，操作本身为O(1)
3. 空间利用率
顺序存储存在预分配浪费或溢出风险；单向循环链表按需分配，空间利用率理论上可达100%，但需额外存储指针域。
核心特性
- 环形遍历能力：无需空指针判断，通过检测指针是否回到起始位置即可控制遍历终止
- 全节点可达性：从任一节点出发均可访问所有其他节点，解决了单链表逆向访问困难的问题
- 结构轻量化：无需增加额外字段，仅调整指针指向即可实现循环特性
实现详解
节点定义
typedef int ResultCode;
typedef int DataType;
typedef struct CircularNode {
DataType value;
struct CircularNode *next;
} CircularNode;
typedef CircularNode* CircularList;初始化与构建
采用尾插法构建循环链表时，需特别注意维护尾节点与头节点的闭环关系。
ResultCode BuildList(CircularList *head) {
DataType inputValue;
CircularList newNode = NULL;
CircularList tailPtr = NULL;
printf("请输入节点值(-1结束):");
while (scanf("%d", &inputValue) == 1) {
if (inputValue == -1) break;
newNode = (CircularList)malloc(sizeof(CircularNode));
if (!newNode) return -1;
newNode->value = inputValue;
if (*head == NULL) {
newNode->next = newNode;
tailPtr = newNode;
*head = newNode;
} else {
newNode->next = *head;
tailPtr->next = newNode;
tailPtr = newNode;
}
}
return 0;
}遍历输出
三种典型的遍历实现方式：
void DisplayList(CircularList head) {
if (!head) {
printf("链表为空\n");
return;
}
CircularList current = head;
// 方案一：do-while结构
do {
printf("%d -> ", current->value);
current = current->next;
} while (current != head);
// 方案二：while结构（预读式）
// while (current->next != head) {
// printf("%d -> ", current->value);
// current = current->next;
// }
// printf("%d", current->value);
// 方案三：for循环
// for (; current->next != head; current = current->next) {
// printf("%d -> ", current->value);
// }
// printf("%d", current->value);
printf("(回到头节点)\n");
}节点插入
插入操作需区分头位置与其他位置。在头部插入时，必须同步更新尾节点的next指针以维持循环性。
ResultCode InsertNode(CircularList *head, int position, DataType newData) {
if (position < 1) return -1;
CircularList newNode = (CircularList)malloc(sizeof(CircularNode));
if (!newNode) return -1;
newNode->value = newData;
if (position == 1) {
// 插入到头部
CircularList tailNode = *head;
if (tailNode) {
while (tailNode->next != *head) {
tailNode = tailNode->next;
}
}
newNode->next = *head;
if (*head) {
tailNode->next = newNode;
} else {
newNode->next = newNode;
}
*head = newNode;
} else {
// 插入到中间或尾部
CircularList prevNode = *head;
for (int i = 1; i < position - 1 && prevNode->next != *head; i++) {
prevNode = prevNode->next;
}
newNode->next = prevNode->next;
prevNode->next = newNode;
}
return 0;
}节点删除
删除操作同样需特殊处理头节点，确保删除后尾节点仍能正确指向新的头节点。
ResultCode RemoveNode(CircularList *head, int position) {
if (!*head) return -1;
CircularList targetNode, prevNode;
if (position == 1) {
// 删除头节点
targetNode = *head;
prevNode = *head;
while (prevNode->next != *head) {
prevNode = prevNode->next;
}
if (prevNode == *head) {
// 仅有一个节点
free(*head);
*head = NULL;
return 0;
}
prevNode->next = (*head)->next;
*head = (*head)->next;
free(targetNode);
} else {
// 删除其他位置
prevNode = *head;
for (int i = 1; i < position - 1 && prevNode->next != *head; i++) {
prevNode = prevNode->next;
}
if (prevNode->next == *head) return -1; // 位置超出范围
targetNode = prevNode->next;
prevNode->next = targetNode->next;
free(targetNode);
}
return 0;
}查询操作
基于位置的查询：
DataType GetElementByPos(CircularList head, int position) {
if (!head || position < 1) return 0;
CircularList current = head;
for (int i = 1; i < position && current->next != head; i++) {
current = current->next;
}
return current->value;
}基于值的查找（假设值唯一）：
int GetPositionByValue(CircularList head, DataType targetValue) {
if (!head) return -1;
CircularList current = head;
int position = 1;
while (current->value != targetValue && current->next != head) {
current = current->next;
position++;
}
return (current->value == targetValue) ? position : -1;
}