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

嵌入式 - 数据结构：循环链表和内核链表

news 2025/8/6 15:55:50

在数据结构的世界中，链表作为一种灵活的线性数据结构，衍生出了多种变体以适应不同的应用场景。本文将聚焦循环链表和内核链表，详细解析其结构特点、实现方式，并结合实际应用场景进行拓展分析，帮助读者深入理解这两种特殊链表的设计思想与实用价值。

一、循环链表：首尾相连的环形结构

循环链表是一种特殊的链表形式，其核心特征是链表的最后一个节点与第一个节点相连，形成一个闭合的环形结构。这种设计使其在需要循环访问数据的场景中表现出色。

1. 结构特点与核心优势

循环链表的最大特点是首尾相接：头结点的前驱指针（ppre）指向链表的最后一个节点，而最后一个节点的后继指针（pnext）则指向头结点（或第一个有效节点）。这种结构带来了诸多优势：

从任意节点出发都能遍历整个链表，无需像单向链表那样记录头节点位置；
适合表示环形数据，如时钟、循环队列等；
简化了链表的某些操作，如尾插法无需遍历找到最后一个节点（通过头结点的前驱即可直接定位）。

2. 节点定义与创建

循环链表的节点结构与双向链表类似，包含数据域和两个指针域（前驱 ppre 和后继 pnext）：

typedef int datatype;
typedef struct node {datatype data;       // 数据域struct node *ppre;   // 前驱指针struct node *pnext;  // 后继指针
} linknode;

创建空循环链表时，需让头节点的前驱和后继指针都指向自身，形成初始闭环：

linknode *create_empty_linklist(void) {linknode *ptmpnode = malloc(sizeof(linknode));if (NULL == ptmpnode) {perror("fail to malloc");return NULL;}ptmpnode->pnext = ptmpnode->ppre = ptmpnode;  // 首尾自环return ptmpnode;
}

3. 核心操作实现

（1）头插法与尾插法

头插法：在头节点之后插入新节点，需同时更新头节点的后继和原第一个节点的前驱指针：

int insert_head_linklist(linknode *phead, datatype tmpdata) {linknode *ptmpnode = malloc(sizeof(linknode));if (NULL == ptmpnode) {perror("fail to malloc");return -1;}ptmpnode->data = tmpdata;ptmpnode->pnext = phead->pnext;  // 新节点后继指向头节点原后继ptmpnode->ppre = phead;          // 新节点前驱指向头节点ptmpnode->pnext->ppre = ptmpnode; // 原第一个节点前驱指向新节点phead->pnext = ptmpnode;         // 头节点后继指向新节点return 0;
}

尾插法：在链表末尾插入新节点，利用头节点的前驱指针直接定位最后一个节点：

int insert_tail_linklist(linknode *phead, datatype tmpdata) {linknode *ptmpnode = malloc(sizeof(linknode));if (NULL == ptmpnode) {perror("fail to malloc");return -1;}ptmpnode->data = tmpdata;ptmpnode->pnext = phead;          // 新节点后继指向头节点（形成环）ptmpnode->ppre = phead->ppre;     // 新节点前驱指向原最后一个节点phead->ppre->pnext = ptmpnode;    // 原最后一个节点后继指向新节点phead->ppre = ptmpnode;           // 头节点前驱指向新节点（更新尾节点）return 0;
}

（2）遍历与查找

循环链表的遍历终止条件为 “指针不等于头节点”（而非 NULL），确保遍历整个环后终止：

int show_linklist(linknode *phead) {linknode *ptmpnode = phead->pnext;while (ptmpnode != phead) {  // 遍历至头节点时终止printf("%d ", ptmpnode->data);ptmpnode = ptmpnode->pnext;}printf("\n");return 0;
}

查找操作与遍历逻辑类似，只需在遍历过程中判断节点数据是否匹配。

（3）删除与销毁

删除节点时需同时更新前驱节点的后继和后继节点的前驱，维持环的完整性；销毁链表时需逐个释放节点，最后释放头节点：

int delete_linklist(linknode *phead, datatype tmpdata) {linknode *ptmpnode = phead->pnext;while (ptmpnode != phead) {if (ptmpnode->data == tmpdata) {ptmpnode->ppre->pnext = ptmpnode->pnext;  // 前驱节点跳过当前节点ptmpnode->pnext->ppre = ptmpnode->ppre;  // 后继节点回指前驱节点free(ptmpnode);}ptmpnode = ptmpnode->pnext;}return 0;
}

4. 应用场景拓展

循环链表在实际开发中应用广泛：

约瑟夫问题：解决环形队列中 “报数淘汰” 问题，利用循环链表的环形结构可高效模拟淘汰过程；
资源调度：如操作系统中时间片轮转调度算法，通过循环链表管理进程队列，实现公平调度；
多媒体播放列表：支持列表循环播放，首尾无缝切换。

二、内核链表：Linux 内核中的通用链表

内核链表是 Linux 内核为实现通用数据结构管理而设计的特殊链表，其核心思想是 “数据中包含链表节点”，而非传统链表的 “节点包含数据”，这种设计使其能适配任意数据类型。

1. 设计理念与优势

传统链表的节点与数据强耦合（如struct node { int data; ... }），而内核链表将链表节点嵌入数据结构中，实现了链表操作与数据类型的解耦：

通用性：同一套链表操作函数可管理任意类型的数据，无需为每种数据类型重复实现链表逻辑；
灵活性：数据结构可同时属于多个链表（通过嵌入多个节点），适合复杂关系管理；
高效性：链表操作仅涉及节点指针修改，与数据本身无关，性能开销小。

2. 结构定义与核心宏

Linux 内核中通过struct list_head定义链表节点，仅包含前驱和后继指针：

struct list_head {struct list_head *next;  // 后继指针struct list_head *prev;  // 前驱指针
};

为实现通用操作，内核链表提供了一系列宏定义，核心包括：

初始化：INIT_LIST_HEAD(head) 初始化头节点，使其首尾自环；
插入：list_add(new, head)（头插）、list_add_tail(new, head)（尾插）；
删除：list_del(old) 从链表中移除节点；
遍历：list_for_each_entry(pos, head, member) 遍历数据元素，其中member为数据结构中struct list_head成员的名称；
数据定位：list_entry(ptr, type, member) 通过节点指针ptr找到数据结构的首地址（核心宏，通过指针运算实现）。

3. 核心操作解析

（1）数据结构定义与初始化

使用内核链表时，需在自定义数据结构中嵌入struct list_head：

// 示例：定义一个包含内核链表节点的进程结构
typedef struct {int pid;             // 进程IDchar name[32];       // 进程名struct list_head list;  // 内核链表节点
} process;// 初始化链表头
struct list_head process_list;
INIT_LIST_HEAD(&process_list);

（2）插入数据

插入数据时，先初始化数据结构中的list节点，再通过list_add或list_add_tail插入链表：

process *p = malloc(sizeof(process));
p->pid = 100;
strcpy(p->name, "test");
INIT_LIST_HEAD(&p->list);  // 初始化节点
list_add_tail(&p->list, &process_list);  // 尾插至链表

（3）遍历与访问数据

通过list_for_each_entry宏遍历数据，自动关联节点与数据：

process *pos;
// 遍历所有进程数据
list_for_each_entry(pos, &process_list, list) {printf("pid: %d, name: %s\n", pos->pid, pos->name);
}

（4）删除数据

删除时先通过节点找到数据，释放前从链表中移除节点：

// 假设pos为待删除的process指针
list_del(&pos->list);  // 从链表中移除节点
free(pos);             // 释放数据

4. 内核链表的实战价值

内核链表在 Linux 内核中无处不在，例如：

进程管理：通过链表维护进程队列（如就绪队列、等待队列）；
文件系统：管理目录项、inode 等结构的关系；
设备驱动：维护设备链表，实现设备的动态注册与注销。

其设计思想也被广泛应用于用户态程序，尤其是需要管理多种数据类型或动态扩展的数据结构场景。

三、循环链表与内核链表的对比与总结

特性	循环链表	内核链表
结构特点	首尾相接的环形结构	数据中嵌入节点，通用化设计
核心优势	适合循环访问，简化首尾操作	解耦数据与链表，支持多类型
典型应用	约瑟夫问题、环形队列	内核数据管理、通用容器
实现复杂度	中等（需维护环形指针关系）	较高（依赖宏定义与指针运算）