数据结构与算法：循环链表和内核链表详解
一、循环链表（Circular Linked List）
1. 基本概念
循环链表是链表的变体，其中最后一个节点指向第一个节点（或头节点），形成一个环状结构。
text
单向循环链表： 头节点 → A → B → C → 头节点 双向循环链表： 头节点 ⇄ A ⇄ B ⇄ C ⇄ 头节点
2. 单向循环链表
2.1 结构定义
c
typedef int DataType;
typedef struct Node {
DataType data;
struct Node *next;
} Node_t;
2.2 创建空循环链表
c
Node_t *CreateEmptyCircularList(void)
{
Node_t *phead = (Node_t *)malloc(sizeof(Node_t));
if (phead == NULL) {
perror("malloc failed");
return NULL;
}
phead->next = phead; // 指向自己，形成环
return phead;
}
2.3 插入操作
c
// 头插法
int InsertHeadCircularList(Node_t *phead, DataType data)
{
Node_t *pnew = (Node_t *)malloc(sizeof(Node_t));
if (pnew == NULL) {
perror("malloc failed");
return -1;
}
pnew->data = data;
pnew->next = phead->next;
phead->next = pnew;
return 0;
}
// 尾插法
int InsertTailCircularList(Node_t *phead, DataType data)
{
Node_t *pnew = (Node_t *)malloc(sizeof(Node_t));
if (pnew == NULL) {
perror("malloc failed");
return -1;
}
pnew->data = data;
// 找到尾节点（指向头节点的节点）
Node_t *ptail = phead;
while (ptail->next != phead) {
ptail = ptail->next;
}
pnew->next = phead;
ptail->next = pnew;
return 0;
}
2.4 遍历操作
c
void ShowCircularList(Node_t *phead)
{
if (phead->next == phead) {
printf("Empty list
");
return;
}
Node_t *pcur = phead->next;
printf("List: ");
while (pcur != phead) {
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("(back to head)
");
}
3. 双向循环链表
3.1 结构定义
c
typedef struct DNode {
DataType data;
struct DNode *prev;
struct DNode *next;
} DNode_t;
3.2 创建空双向循环链表
c
DNode_t *CreateEmptyDoubleCircularList(void)
{
DNode_t *phead = (DNode_t *)malloc(sizeof(DNode_t));
if (phead == NULL) {
perror("malloc failed");
return NULL;
}
phead->prev = phead;
phead->next = phead;
return phead;
}
3.3 插入操作
c
// 通用插入函数（在指定节点后插入）
void InsertAfterNode(DNode_t *pnode, DataType data)
{
DNode_t *pnew = (DNode_t *)malloc(sizeof(DNode_t));
if (pnew == NULL) return;
pnew->data = data;
// 插入到pnode之后
pnew->next = pnode->next;
pnew->prev = pnode;
pnode->next->prev = pnew;
pnode->next = pnew;
}
// 头插法
int InsertHeadDoubleCircularList(DNode_t *phead, DataType data)
{
InsertAfterNode(phead, data);
return 0;
}
// 尾插法
int InsertTailDoubleCircularList(DNode_t *phead, DataType data)
{
InsertAfterNode(phead->prev, data);
return 0;
}
3.4 删除操作
c
// 删除指定节点
void DeleteNode(DNode_t *pnode)
{
if (pnode == NULL) return;
pnode->prev->next = pnode->next;
pnode->next->prev = pnode->prev;
free(pnode);
}
// 删除指定数据的节点
int DeleteDataDoubleCircularList(DNode_t *phead, DataType data)
{
DNode_t *pcur = phead->next;
while (pcur != phead) {
if (pcur->data == data) {
DeleteNode(pcur);
return 0;
}
pcur = pcur->next;
}
return -1; // 未找到
}
3.5 遍历操作
c
// 正向遍历
void ShowDoubleCircularListForward(DNode_t *phead)
{
if (phead->next == phead) {
printf("Empty list
");
return;
}
DNode_t *pcur = phead->next;
printf("Forward: ");
while (pcur != phead) {
printf("%d ", pcur->data);
pcur = pcur->next;
}
printf("
");
}
// 反向遍历
void ShowDoubleCircularListBackward(DNode_t *phead)
{
if (phead->prev == phead) {
printf("Empty list
");
return;
}
DNode_t *pcur = phead->prev;
printf("Backward: ");
while (pcur != phead) {
printf("%d ", pcur->data);
pcur = pcur->prev;
}
printf("
");
}
二、内核链表（Linux Kernel Linked List）
1. 内核链表的特点
内核链表是Linux内核中使用的一种通用双向循环链表，具有以下特点：
-
与数据分离：链表节点不包含数据，只有前后指针
-
高度通用：可用于任何数据结构
-
类型安全：通过宏实现类型检查
-
零指针优化：使用NULL指针优化判断
2. 内核链表的数据结构
c
// 链表节点结构（最小化）
struct list_head {
struct list_head *next;
struct list_head *prev;
};
3. 完整内核链表实现
3.1 头文件 kernel_list.h
c
#ifndef _KERNEL_LIST_H
#define _KERNEL_LIST_H
// 链表节点结构
struct list_head {
struct list_head *next;
struct list_head *prev;
};
// 初始化链表头
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
// 内部插入函数
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
// 头插法
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 尾插法
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
// 内部删除函数
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
// 删除节点
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *)0; // 用于调试
entry->prev = (void *)0;
}
// 判断链表是否为空
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
// 遍历宏
#define list_for_each(pos, head)
for (pos = (head)->next; pos != (head); pos = pos->next)
// 安全遍历宏（支持删除）
#define list_for_each_safe(pos, n, head)
for (pos = (head)->next, n = pos->next; pos != (head);
pos = n, n = pos->next)
// 获取宿主结构的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// 获取包含链表节点的结构体指针
#define container_of(ptr, type, member) ({
const typeof(((type *)0)->member) *__mptr = (ptr);
(type *)((char *)__mptr - offsetof(type, member)); })
// 获取链表节点所在的结构体
#define list_entry(ptr, type, member)
container_of(ptr, type, member)
// 遍历宿主结构
#define list_for_each_entry(pos, head, member)
for (pos = list_entry((head)->next, typeof(*pos), member);
&pos->member != (head);
pos = list_entry(pos->member.next, typeof(*pos), member))
// 安全遍历宿主结构
#define list_for_each_entry_safe(pos, n, head, member)
for (pos = list_entry((head)->next, typeof(*pos), member),
n = list_entry(pos->member.next, typeof(*pos), member);
&pos->member != (head);
pos = n, n = list_entry(n->member.next, typeof(*n), member))
#endif
3.2 使用示例
示例1：学生管理系统
c
#include#include #include #include "kernel_list.h" // 学生结构体 typedef struct student { int id; char name[32]; int score; struct list_head list; // 嵌入链表节点 } Student; // 创建学生 Student *create_student(int id, const char *name, int score) { Student *stu = (Student *)malloc(sizeof(Student)); if (stu == NULL) return NULL; stu->id = id; strncpy(stu->name, name, sizeof(stu->name) - 1); stu->score = score; INIT_LIST_HEAD(&stu->list); // 初始化链表节点 return stu; } // 打印学生列表 void print_students(struct list_head *head) { Student *pos; printf("=== 学生列表 === "); printf("ID 姓名 分数 "); printf("---------------- "); list_for_each_entry(pos, head, list) { printf("%d %s %d ", pos->id, pos->name, pos->score); } printf(" "); } // 按分数排序（插入排序） void sort_by_score(struct list_head *head) { struct list_head *i, *j, *temp; Student *stu_i, *stu_j; list_for_each(i, head) { j = i; while (j != head->next) { stu_i = list_entry(i, Student, list); stu_j = list_entry(j->prev, Student, list); if (stu_j->score > stu_i->score) { // 交换节点位置 list_del(i); __list_add(i, j->prev, j); break; } j = j->prev; } } } int main() { // 创建链表头 struct list_head student_list; INIT_LIST_HEAD(&student_list); // 添加学生 Student *stu1 = create_student(1001, "张三", 85); Student *stu2 = create_student(1002, "李四", 92); Student *stu3 = create_student(1003, "王五", 78); Student *stu4 = create_student(1004, "赵六", 95); // 尾插法添加 list_add_tail(&stu1->list, &student_list); list_add_tail(&stu2->list, &student_list); list_add_tail(&stu3->list, &student_list); list_add_tail(&stu4->list, &student_list); printf("原始列表: "); print_students(&student_list); // 按分数排序 sort_by_score(&student_list); printf("按分数排序后: "); print_students(&student_list); // 删除分数最低的学生 Student *last = list_entry(student_list.prev, Student, list); printf("删除学生: %s (分数: %d) ", last->name, last->score); list_del(&last->list); free(last); printf("删除后: "); print_students(&student_list); // 释放所有内存 Student *pos, *n; list_for_each_entry_safe(pos, n, &student_list, list) { list_del(&pos->list); free(pos); } return 0; }
示例2：进程调度队列
c
#include#include #include "kernel_list.h" // 进程控制块（PCB） typedef struct process { int pid; // 进程ID char name[16]; // 进程名 int priority; // 优先级 int state; // 状态：0-就绪，1-运行，2-阻塞 struct list_head ready_list; // 就绪队列节点 struct list_head all_list; // 所有进程链表节点 } Process; // 全局链表头 struct list_head ready_queue; // 就绪队列 struct list_head all_processes; // 所有进程链表 // 初始化系统 void init_system(void) { INIT_LIST_HEAD(&ready_queue); INIT_LIST_HEAD(&all_processes); } // 创建进程 Process *create_process(int pid, const char *name, int priority) { Process *proc = (Process *)malloc(sizeof(Process)); if (proc == NULL) return NULL; proc->pid = pid; snprintf(proc->name, sizeof(proc->name), "%s", name); proc->priority = priority; proc->state = 0; // 初始状态为就绪 INIT_LIST_HEAD(&proc->ready_list); INIT_LIST_HEAD(&proc->all_list); return proc; } // 添加进程到系统 void add_process(Process *proc) { // 添加到所有进程链表 list_add_tail(&proc->all_list, &all_processes); // 如果进程就绪，添加到就绪队列 if (proc->state == 0) { // 按优先级插入（优先级高的在前面） struct list_head *pos; Process *p; list_for_each(pos, &ready_queue) { p = list_entry(pos, Process, ready_list); if (p->priority < proc->priority) { break; } } __list_add(&proc->ready_list, pos->prev, pos); } } // 调度进程 Process *schedule_process(void) { if (list_empty(&ready_queue)) { return NULL; } // 从就绪队列头取出进程 Process *proc = list_entry(ready_queue.next, Process, ready_list); list_del(&proc->ready_list); proc->state = 1; // 设置为运行状态 return proc; } // 进程阻塞 void block_process(Process *proc) { if (proc->state == 1) { // 只有运行状态的进程可以阻塞 proc->state = 2; // 设置为阻塞状态 list_del(&proc->ready_list); } } // 进程唤醒 void wakeup_process(Process *proc) { if (proc->state == 2) { // 只有阻塞状态的进程可以唤醒 proc->state = 0; // 设置为就绪状态 add_process(proc); // 重新添加到就绪队列 } } // 打印队列状态 void print_queues(void) { Process *pos; printf("=== 就绪队列 === "); list_for_each_entry(pos, &ready_queue, ready_list) { printf("PID: %d, 名称: %s, 优先级: %d ", pos->pid, pos->name, pos->priority); } printf(" === 所有进程 === "); list_for_each_entry(pos, &all_processes, all_list) { const char *state_str; switch (pos->state) { case 0: state_str = "就绪"; break; case 1: state_str = "运行"; break; case 2: state_str = "阻塞"; break; default: state_str = "未知"; } printf("PID: %d, 名称: %s, 状态: %s ", pos->pid, pos->name, state_str); } printf(" "); } int main() { // 初始化系统 init_system(); // 创建进程 Process *p1 = create_process(1, "init", 10); Process *p2 = create_process(2, "bash", 5); Process *p3 = create_process(3, "vim", 8); Process *p4 = create_process(4, "gcc", 3); // 添加进程到系统 add_process(p1); add_process(p2); add_process(p3); add_process(p4); printf("初始状态: "); print_queues(); // 调度进程 Process *running = schedule_process(); if (running) { printf("调度进程: %s (PID: %d) ", running->name, running->pid); } printf("调度后: "); print_queues(); // 阻塞进程 if (running) { printf("阻塞进程: %s ", running->name); block_process(running); } printf("阻塞后: "); print_queues(); // 唤醒进程 if (running) { printf("唤醒进程: %s ", running->name); wakeup_process(running); } printf("唤醒后: "); print_queues(); // 清理资源 Process *pos, *n; list_for_each_entry_safe(pos, n, &all_processes, all_list) { list_del(&pos->all_list); if (pos->state == 0) { list_del(&pos->ready_list); } free(pos); } return 0; }
三、内核链表的优势
1. 代码复用性高
c
// 同样的链表操作可用于任何数据结构
struct student {
int id;
char name[32];
struct list_head list;
};
struct teacher {
int id;
char name[32];
char subject[32];
struct list_head list;
};
// 都可以使用同样的链表操作函数
2. 内存效率高
-
链表节点只包含两个指针（8或16字节）
-
数据与链表结构分离，无额外内存开销
3. 类型安全
-
通过
container_of宏确保类型正确 -
编译时类型检查
4. 性能优化
-
循环链表结构，访问效率高
-
内联函数减少函数调用开销
四、常见问题解答
Q1: 循环链表和普通链表有什么区别？
A: 主要区别在于尾节点的next指针：
-
普通链表：尾节点next指向NULL
-
循环链表：尾节点next指向头节点
Q2: 内核链表为什么设计成双向循环？
A:
-
双向：可以向前和向后遍历，删除节点时不需要前驱指针
-
循环：简化边界条件判断，所有节点都有前驱和后继
Q3: container_of宏是如何工作的？
A: 这是一个巧妙的指针运算：
c
// 假设结构体地址为0，计算成员的偏移量
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// 通过成员指针获取结构体指针
#define container_of(ptr, type, member) ({
(type *)((char *)ptr - offsetof(type, member));
})
Q4: 内核链表的list_for_each_safe为什么安全？
A: 它在遍历时保存了下一个节点的指针，即使当前节点被删除，也能继续遍历：
c
#define list_for_each_safe(pos, n, head)
for (pos = (head)->next, n = pos->next; pos != (head);
pos = n, n = pos->next)
五、实际应用场景
1. 操作系统
-
进程调度队列
-
文件描述符表
-
内存页管理
2. 嵌入式系统
-
设备驱动管理
-
定时器队列
-
中断处理队列
3. 应用软件
-
LRU缓存淘汰算法
-
内存池管理
-
连接池管理
