【数据结构】单循环链表

易ლ拉罐

1367人浏览 · 2025-07-17 23:22:43

易ლ拉罐 · 2025-07-17 23:22:43 发布

一、单循环链表的基本概念与结构

单循环链表是一种特殊的链表结构，其最后一个节点的指针不再指向 NULL，而是指向头节点（或第一个节点），形成一个闭合环。与普通单链表相比，循环链表允许从任意节点出发遍历整个链表，无需额外处理尾节点。

1、单循环链表的有效节点的结构设计

单循环链表的节点结构与普通单链表相同，包含两部分：数据域：存储节点的实际数据；指针域：存储指向下一个节点的地址。

typedef int Elem_Type;

//单链表有效节点的结构体设计
typedef struct CNode {
	Elem_Type data;//数据域，存储有效数据
	struct CNode* next;//指针域，存储下一个有效节点的地址
}CNode, * PCNode;

关键区别：

普通单链表的尾节点指针域为 NULL。
单循环链表的尾节点指针域指向头节点（或首节点）。
单链表辅助节点的结构体设计，借用有效节点

二、单循环链表的各功能函数的声明

// 可实现的操作
void Init_CList(CNode* plist);// 初始化
bool Insert_head(CNode* plist, Elem_Type val);//头插
bool Insert_tail(CNode* plist, Elem_Type val);//尾插
bool Insert_pos(CNode* plist, Elem_Type val, int pos);//按位置插入
bool Del_head(CNode* plist);//头删
bool Del_tail(CNode* plist);//尾删
bool Del_pos(CNode* plist, int pos);//按位置删除；默认pos=0,则为头删
bool Del_val(CNode* plist, Elem_Type val);//按值删除；只删除val出现的第一次的位置
bool Del_ALL_val(CNode* plist, Elem_Type val);//按值删除；删除val出现的所有位置
CNode* Search(CNode* plist, Elem_Type val);// 查找,查找第一次出现的
void Clear(CNode* plist);// 清空
void Destroy1(CNode* plist);// 销毁1,需要辅助节点参与
void Destroy2(CNode* plist);// 销毁2，不需要
bool Is_Empty(CNode* plist);// 判空
int Get_Length(CNode* plist);//获取有效值长度
void Show(CNode* plist);//打印

三、单循环链表的基本操作

1、初始化

图解：

代码实现：

// 初始化
void Init_CList(CNode* plist) {
	assert(plist != NULL);
	//数据域不做处理，指针域指向自身
	plist->next = plist;
}

2、插入操作

头插

图解：

代码实现：

bool Insert_head(CNode* plist, Elem_Type val) {
	assert(plist != NULL);
	if (plist == NULL) {
		return false;
	}
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));//购买新节点
	if (pnewnode == NULL) {
		exit(1);
	}
	pnewnode->data = val;
	//找到合适位置插入,头插比较特殊，在头节点后
	pnewnode->next = plist->next;
	plist->next = pnewnode;
	return true;
}

尾插

图解：

代码实现：

bool Insert_tail(CNode* plist, Elem_Type val) {
	assert(plist != NULL);
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));//购买新结点
	if (pnewnode == NULL) exit(1);
	pnewnode->data = val;
	CNode* p = plist;
	//尾插需要将临时指针p，停在当前尾节点处
	while (plist->next!=plist) {
		p = p->next;
	}
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

按位置插入

图解：

代码实现：

//按位置插入,默认pos=0,代表头插
bool Insert_pos(CNode* plist, Elem_Type val, int pos) {
	assert(plist != NULL);
	CNode* pnewnode = (CNode*)malloc(sizeof(CNode));//购买新结点
	if (pnewnode == NULL) exit(1);
	pnewnode->data = val;
	//找到合适的待插位置，pos=ji,p走pos步
	CNode* p = plist;
	for (int i = 0; i < pos; i++){
		p = p->next;
	}
	pnewnode->next = p->next;
	p->next = pnewnode;
	return true;
}

3、删除操作
头删

图解：

代码实现：

//头删
bool Del_head(CNode* plist) {
	assert(plist != NULL);
	if (plist == NULL) return false;
	//对单循环链表判空
	if (Is_Empty(plist)) return false;
	//需要一个临时指针q指向待删节点,由于是头删，因此q为第一个有效值节点
	CNode* q = plist->next;
	//需要一个临时指针p指向待删节点的前驱,由于是头删，因此p用辅助结点plist代替
	//跨越指向，释放
	plist->next = q->next;
	free(q);
	q = NULL;
	return true;
}

尾删

图解：

代码实现：

//尾删
bool Del_tail(CNode* plist) {
	assert(plist != NULL);
	if (plist == NULL) return false;
	//对单循环链表判空
	if (Is_Empty(plist)) return false;
	//需要一个临时指针q指向待删节点,由于是尾删，因此q为最后一个有效值节点
	CNode* q = plist;
	for (; q->next != plist; q = q->next);
	//需要一个临时指针p指向待删节点的前驱
	CNode* p = plist;
	for (; p->next != q; p = p->next);
	//跨越指向，释放
	p->next = q->next;
	free(q);
	q = NULL;
	return true;
}

按位置删除；默认pos=0,则为头删

图解：

代码实现：

//按位置删除；默认pos=0,则为头删
bool Del_pos(CNode* plist, int pos) {
	assert(plist != NULL);
	if (plist == NULL) return false;
	assert(pos >= 0 && pos < Get_Length(plist));
	//对单循环链表判空
	if (Is_Empty(plist)) return false;
	//需要一个临时指针q指向待删节点
	//需要一个临时指针p指向待删节点的前驱
	CNode* p = plist;
	for (int i = 0; i < pos;i++)
		p = p->next;
	CNode* q = p->next;
	//跨越指向，释放
	p->next = q->next;
	free(q);
	q = NULL;
	return true;
}

按值删除；只删除val出现的第一次的位置

代码实现：

//按值删除；只删除val出现的第一次的位置
bool Del_val(CNode* plist, Elem_Type val) {
	assert(plist != NULL);
	if (plist == NULL) return false;
	//对单循环链表判空
	if (Is_Empty(plist)) return false;
	//需要一个临时指针q指向待删节点,通过search找到val第一次出现的位置
	CNode* q =Search(plist, val); 
	if (NULL == q)return false;
	//需要一个临时指针p指向待删节点的前驱
	CNode* p = plist;
	for (; p->next != q; p = p->next);
	//跨越指向，释放
	p->next = q->next;
	free(q);
	q = NULL;
	return true;
}

按值删除；删除val出现的所有位置

图解：

代码实现：

//按值删除；删除val出现的所有位置
bool Del_ALL_val(CNode* plist, Elem_Type val) {
	assert(plist != NULL);
	if (plist == NULL) return false;
	//对单循环链表判空
	if (Is_Empty(plist)) return false;
	CNode* p = plist->next;
	CNode* q = plist;
	while (p->next != plist) {
		q = p->next;
		if (q->data == val) {
			p->next = q->next;
			free(p);
			q = NULL;
		}
		else {
			p = q;
		}
	}
	return true;
}

4、查找,查找第一次出现的

代码实现：

// 查找,查找第一次出现的
CNode* Search(CNode* plist, Elem_Type val) {
	for (CNode* p = plist->next; p != plist; p = p->next) {
		if (p->data == val) {
			return p;
		}
	}
	return NULL;
}

5、清空

代码实现：

// 清空
void Clear(CNode* plist) {
	Destroy1(plist);
}

6、销毁

销毁1,需要辅助节点参与

代码实现：

// 销毁1,需要辅助节点参与,无限头删
void Destroy1(CNode* plist) {
	while (plist->next!=plist) {
		CNode* p = plist->next;
		plist->next = p->next;
		free(p);
		p = NULL;
	}
}

销毁2，不需要

图解：

代码实现：

// 销毁2，不需要,利用临时指针pq，去销毁所有有效节点，辅助结点不参与
void Destroy2(CNode* plist) {
	//assert
	CNode* p = plist->next;//申请指针p,使其保存辅助结点的指针域
	CNode* q=NULL;//申请指针q，先不给q赋值
	//反复通过pq，去销毁后续节点
	//节点全部销毁完毕，最后处理辅助结点的指针域
	while (p != plist) {
		q = p->next;
		free(p);
		p = q;
	}
}

7、判空

代码实现：

// 判空
bool Is_Empty(CNode* plist) {
	return plist->next != plist;
}

8、获取有效值长度

代码实现：

//获取有效值长度
int Get_Length(CNode* plist) {
	int length = 0;
	for (CNode* p = plist->next; p != plist; p = p->next)length++;
	return length;
}

9、打印

图解：

代码实现：

void Show(CNode* plist) {
	//assert
	for (CNode*p  = plist->next; p != plist; p = p->next) {
		printf("%d ", p->data);
	}
	printf("\n");
}

四、单循环链表的应用场景

约瑟夫问题（Josephus Problem）
轮询任务调度
环形缓冲区实现

五、单循环链表的优缺点

优点：空间利用率高，适合环形数据需求
缺点：操作复杂度较高，需注意循环终止条件

六、常见问题与解决方案

1、循环单链表避免死循环与内存泄漏的方法

设置明确的终止条件

在遍历循环单链表时，必须通过判断当前节点是否回到头节点（或预设的终止节点）来终止循环。例如：

Node* current = head;
do {
    // 处理节点逻辑
    current = current->next;
} while (current != head);  // 终止条件

引入遍历计数器

对于可能存在环外环的异常情况，可设置最大遍历次数（如链表长度），防止无限循环：

int max_steps = list_length;
while (current != NULL && max_steps-- > 0) {
    // 处理节点
    current = current->next;
}

严格管理内存释放

释放循环单链表时，需先断开循环再释放节点，避免无法回收：

if (head != NULL) {
    Node* current = head->next;
    head->next = NULL;  // 断开循环
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
}

2、边界条件处理

空链表情形

所有操作前需检查头指针是否为NULL：

if (head == NULL) {
    return;  // 或返回错误码
}

单节点链表情形

处理单节点时需确保next指针不引发无限循环：

if (head->next == head) {
    // 单节点特殊处理
    free(head);
    head = NULL;
    return;
}

插入/删除操作的边界处理

插入节点到空链表：新节点的next应指向自身。
删除最后一个节点：将头指针置为NULL。

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能