linux下c语言中的单向列表,双向链表,内核双向列表,及适用场景

2024-09-05 23:12

本文主要是介绍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语言中的单向列表,双向链表,内核双向列表,及适用场景的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1140334

相关文章

Linux中修改Apache HTTP Server(httpd)默认端口的完整指南

《Linux中修改ApacheHTTPServer(httpd)默认端口的完整指南》ApacheHTTPServer(简称httpd)是Linux系统中最常用的Web服务器之一,本文将详细介绍如何... 目录一、修改 httpd 默认端口的步骤1. 查找 httpd 配置文件路径2. 编辑配置文件3. 保存

Linux使用scp进行远程目录文件复制的详细步骤和示例

《Linux使用scp进行远程目录文件复制的详细步骤和示例》在Linux系统中,scp(安全复制协议)是一个使用SSH(安全外壳协议)进行文件和目录安全传输的命令,它允许在远程主机之间复制文件和目录,... 目录1. 什么是scp?2. 语法3. 示例示例 1: 复制本地目录到远程主机示例 2: 复制远程主

Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析

《Spring组件实例化扩展点之InstantiationAwareBeanPostProcessor使用场景解析》InstantiationAwareBeanPostProcessor是Spring... 目录一、什么是InstantiationAwareBeanPostProcessor?二、核心方法解

Java 枚举的基本使用方法及实际使用场景

《Java枚举的基本使用方法及实际使用场景》枚举是Java中一种特殊的类,用于定义一组固定的常量,枚举类型提供了更好的类型安全性和可读性,适用于需要定义一组有限且固定的值的场景,本文给大家介绍Jav... 目录一、什么是枚举?二、枚举的基本使用方法定义枚举三、实际使用场景代替常量状态机四、更多用法1.实现接

java -jar命令运行 jar包时运行外部依赖jar包的场景分析

《java-jar命令运行jar包时运行外部依赖jar包的场景分析》:本文主要介绍java-jar命令运行jar包时运行外部依赖jar包的场景分析,本文给大家介绍的非常详细,对大家的学习或工作... 目录Java -jar命令运行 jar包时如何运行外部依赖jar包场景:解决:方法一、启动参数添加: -Xb

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

Linux CPU飙升排查五步法解读

《LinuxCPU飙升排查五步法解读》:本文主要介绍LinuxCPU飙升排查五步法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录排查思路-五步法1. top命令定位应用进程pid2.php top-Hp[pid]定位应用进程对应的线程tid3. printf"%

Linux下安装Anaconda3全过程

《Linux下安装Anaconda3全过程》:本文主要介绍Linux下安装Anaconda3全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录简介环境下载安装一、找到下载好的文件名为Anaconda3-2018.12-linux-x86_64的安装包二、或者通

Linux系统之stress-ng测压工具的使用

《Linux系统之stress-ng测压工具的使用》:本文主要介绍Linux系统之stress-ng测压工具的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、理论1.stress工具简介与安装2.语法及参数3.具体安装二、实验1.运行8 cpu, 4 fo