本文主要是介绍linux下c语言中的单向列表，双向链表，内核双向列表，及适用场景，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 单向链表（Singly Linked List）
1.1 定义与结构
单向链表是链式存储结构中最简单的一种。它的每个节点包含两个部分：
- 数据域：存储数据元素
- 指针域：存储指向下一个节点的指针
在单向链表中，节点通过指针域相互链接，形成一个线性结构。链表的最后一个节点指向 `NULL`，表示链表的结束。
C 语言中单向链表的定义：
struct Node {
int data; // 数据域
struct Node *next; // 指针域，指向下一个节点
};
1.2 操作与实现
插入节点
插入节点通常有几种方式：
- 在链表头插入节点
- 在链表尾插入节点
- 在链表中的某个位置插入节点
在链表头插入节点的代码示例：
void insert_at_head(struct Node **head, int new_data) {
struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head;
*head = new_node;
}
删除节点
删除节点同样可以根据位置（头节点、尾节点、中间节点）来进行操作。
删除指定值节点的代码示例：
void delete_node(struct Node **head, int key) {
struct Node *temp = *head, *prev;
if (temp != NULL && temp->data == key) {
*head = temp->next; // 如果头节点就是要删除的节点
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return; // 如果没有找到该节点
prev->next = temp->next; // 解除该节点与链表的链接
free(temp);
}
遍历链表
遍历链表是通过一个临时指针从头到尾遍历所有节点。
遍历链表的代码示例：
void print_list(struct Node *node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
1.3 适用场景
单向链表适合用于需要频繁在表头插入或删除元素的场景，例如：
- 实现堆栈（栈顶元素可以快速插入和删除）
- 需要动态增加或删除元素且对内存要求敏感时
然而，由于单向链表只能向一个方向遍历，查找和插入某些特定位置的性能较差。
2. 双向链表（Doubly Linked List）
2.1 定义与结构
双向链表相比单向链表，增加了对每个节点前驱节点的引用。每个节点包含三个部分：
- 数据域：存储数据
- 前驱指针域：指向上一个节点
- 后继指针域：指向下一个节点
C 语言中双向链表的定义：
struct Node {
int data;
struct Node *prev; // 前驱指针
struct Node *next; // 后继指针
};
2.2 操作与实现
由于双向链表的节点有两个指针，操作和单向链表相比稍显复杂，但在链表的遍历、删除和插入操作中，灵活性更强。
插入节点
在链表头插入节点：
void insert_at_head(struct Node **head, int new_data) {
struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head;
new_node->prev = NULL;
if (*head != NULL) {
(*head)->prev = new_node;
}
*head = new_node;
}
删除节点
删除指定节点：
void delete_node(struct Node **head, struct Node *del_node) {
if (*head == NULL || del_node == NULL) return;
if (*head == del_node) *head = del_node->next;
if (del_node->next != NULL) del_node->next->prev = del_node->prev;
if (del_node->prev != NULL) del_node->prev->next = del_node->next;
free(del_node);
}
遍历链表
双向链表可以从任意节点向前或向后遍历，提供了更灵活的遍历方式。
从头到尾遍历双向链表的代码：
void print_list(struct Node *node) {
struct Node *last;
printf("Traversal in forward direction: ");
while (node != NULL) {
printf("%d -> ", node->data);
last = node;
node = node->next;
}
printf("NULL\n");
printf("Traversal in reverse direction: ");
while (last != NULL) {
printf("%d -> ", last->data);
last = last->prev;
}
printf("NULL\n");
}
2.3 适用场景
双向链表特别适用于需要双向遍历的场景，例如：
- 实现双端队列（Deque）
- 实现导航系统，用户可以前后移动（如浏览器的前进/后退操作）
双向链表的缺点是每个节点需要额外的空间来存储 `prev` 指针，相比单向链表占用更多内存。
3. 内核双向链表（Linux Kernel Doubly Linked List）
3.1 定义与结构
在 Linux 内核中，双向链表的实现采用了高度模块化和通用化的设计。Linux 内核中的双向链表不会直接与数据绑定，而是通过一个独立的 `list_head` 结构体表示链表节点的指针。这使得链表可以灵活地嵌入任意数据结构中。
Linux 内核双向链表的定义：
struct list_head {
struct list_head *next, *prev;
};
每个节点的数据存储在包含 `list_head` 的外部数据结构中。
3.2 操作与实现
内核提供了一套高效的宏和函数来简化双向链表的操作。例如：
- *`INIT_LIST_HEAD(&head)`：初始化链表头节点。
- `list_add()` 和 `list_add_tail()`：在链表头或尾部插入节点。
- `list_del()`：删除节点。
插入节点示例
struct my_data {
int value;
struct list_head list;
};
struct list_head my_list;
INIT_LIST_HEAD(&my_list);
struct my_data data1 = { .value = 1 };
list_add(&data1.list, &my_list);
遍历节点示例
使用宏遍历链表中的每个节点：
struct my_data *entry;
list_for_each_entry(entry, &my_list, list) {
printk(KERN_INFO "Value: %d\n", entry->value);
}
3.3 适用场景
Linux 内核双向链表广泛用于内核中的各种模块，例如：
- 实现任务队列
- 管理内核资源
- 设备驱动程序中的资源管理
内核双向链表特别适合场景复杂、需要高度通用性和高效链表操作的场合。
4. 总结与比较
5. 选择建议
- 单向链表：适合于内存受限、操作简单、只需要单向遍历的场景，如堆栈、队列。
- 双向链表：适合需要双向遍历、插入和删除频繁的场景，如双端队列、双向导航应用。
- 内核双向链表：适用于高效链表操作、复杂系统管理场景，尤其是嵌入式系统、内核模块和驱动开发。
这篇关于linux下c语言中的单向列表，双向链表，内核双向列表，及适用场景的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
