首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Linux内核链表使用

/******************** * 内核中链表应用 ********************/ (1)介绍 在Linux内核中使用了大量链表结构来组织数据,包括设备列表以及各种功能模块中数据组织...这些链表大多采用在include/linux/list.h实现一个相当精彩链表数据结构。...和以前介绍链表结构模型不同,这里list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是在数据结构中包含链表节点。...如: struct my_struct{ struct list_head list; unsigned long dog; void *cat; }; linux链表没有固定表头,从任何元素开始访问都可以...定义在 a.增加节点 list_add(struct list_head *new, struct list_head *head); 向指定链表head

2.3K30

linux通用链表

引言 链表实现是基于结构体与指针两者实现,常用链表数据结构如下: //将int起别名ELEMTYPE,是为了方便修改链表数据域类型。...在Linux中设计了一种适合于各种类型数据域都可以使用通用型链表: struct list_head { struct list_head *prev, *next; }; 摒弃掉数据域,只保留头尾指针...内核链表 链表主要意义就是将分散地址数据域通过指针排列成有序队列。因此数据域是链表不可或缺一部分,但是在实际使用中需要不同类型数据域,因此也就限制了链表通用。...Linux中在声明中抛弃了数据域,也就解决掉了这一问题。 原理 Linux使用链表方法:使用时,自定义结构体包含数据域+链表结构体。...链表.png 如上图所示,将结构体A、B、C中内核结构体指针构建成双链表,这样结构体A、B、C中链表成员就可以互相索引了。

1.1K20
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    C 链表 - linux 如何实现

    链表是基本数据结构, 一开始学习数据结构时, 我一般这么定义, 对应实现从头或尾插入处理函数, struct int_node_old { int val; struct int_node_old...想起前段时间, 看到FreeRTOS提供链表处理方式(《 FreeRTOS 任务调度 List 组织 》), 将链表结构定义和实际使用时具体节点数据内容分开定义, 供系统各个模块使用。...查看linux源码, 发现linux中也为我们提供了相似的实现(源码), 把一些共性统一起来。 类是 python 中for_each处理,有些意思。...linux链表定义在文件 include/linux/types.h, 采用是双向列表 struct list_head { struct list_head *next, *prev;...list 利用这个定义, 我定义了一个自己list数据结构, 并copy了一些接口实现,感受下,linux 是如何管理链表

    2.7K30

    linux内核源码 -- list链表

    linux kernel中list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下; linux kernel里很多数据结构都很经典, list链表就是其中之一 本篇要介绍内容: list...定义 list提供操作方法 注意事项 使用实例 ---- List 所在文件: List所有操作可以在 include/linux/list.h找到; List head定义可以在 include.../linux/types.h找到; 定义 实际上这就是一个双向循环链表, 且有一个头指针 list head定义: struct list_head { struct list_head *next...__list_del_entry(list); // 添加到新链表头部 list_add(list, head); } 将一个元素移动到另一个list队尾 static...struct中,这个宏就是由这个list_head ptr来获取当前所处struct对象指针, 用了linux经典宏定义 container_of #define list_entry(ptr,

    2.3K10

    Linux内核中双向链表经典实现

    概要 本文对双向链表进行探讨,介绍内容是Linux内核中双向链表经典实现和用法。其中,也会涉及到Linux内核中非常常用两个经典宏定义offsetof和container_of。...内容包括: 1.Linux两个经典宏定义 2.Linux中双向链表经典实现 Linux两个经典宏定义 倘若你查看过Linux Kernel源码,那么你对 offsetof 和 container_of...Linux中双向链表经典实现 1.Linux中双向链表介绍 Linux双向链表定义主要涉及到两个文件: include/linux/types.h include/linux/list.h Linux...list_del(entry) 和 list_del_init(entry)是linux内核对外接口。 list_del(entry) 作用是从双链表中删除entry节点。...3.Linux中双向链表使用示例 双向链表代码(list.h): 1 #ifndef _LIST_HEAD_H 2 #define _LIST_HEAD_H 3 // 双向链表节点 4 struct

    2.6K30

    Linux 内核通用链表学习小结

    描述 在linux内核中封装了一个通用双向链表库,这个通用链表库有很好扩展性和封装性,它给我们提供了一个固定指针域结构体,我们在使用时候,只需要在我们定义数据域结构体中包含这个指针域结构体就可以了...传统链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们指针域结构体...list_add-先入先出模式 我们链表节点,实际在内存中展示形态 ?...反推结构体首地址 举个例子 这个例子包括简单增、删、遍历 #include #include #include <linux...内核提供这个通用链表库里面还有很多其他接口,这里没有详细一一举例,有兴趣可以自己去看看,在源码包 include/linux/list.h 文件里面,不过通过阅读一些源代码确实对我们也有很大提高

    1.3K21

    工作当中非常实用Linux内核链表

    前言: 在上期文章中,已经给大家分享过offsetof()和container_of两个宏函数,这两个宏函数在Linux内核链表里面有大量应用,对于我们平时工作写代码有很大帮助。...下面是Linux内核链表内容分享。...做内核驱动开发经常会使用linux内核最经典双向链表 list_head, 以及它拓展接口(或者宏定义): list_add , list_add_tail, list_del , list_entry...; }; 然后就开始围绕这个结构开始构建链表,然后插入、删除节点 ,遍历整个链表等等,其实内核已经提供好了现成接口,接下来就让我们进入 kernel/include/linux/list.h中: 一...做linux驱动开发同学是不是想到了LDD3这本书中经常使用一个非常经典宏定义呢!

    1K10

    002 Linux内核中双向链表经典实现

    概要 本文对双向链表进行探讨,介绍内容是Linux内核中双向链表经典实现和用法。其中,也会涉及到Linux内核中非常常用两个经典宏定义offsetof和container_of。...内容包括: 1.Linux两个经典宏定义 2.Linux中双向链表经典实现 Linux两个经典宏定义 倘若你查看过Linux Kernel源码,那么你对 offsetof 和 container_of...Linux中双向链表经典实现 1.Linux中双向链表介绍 Linux双向链表定义主要涉及到两个文件: include/linux/types.h include/linux/list.h Linux...list_del(entry) 和 list_del_init(entry)是linux内核对外接口。 list_del(entry) 作用是从双链表中删除entry节点。...3.Linux中双向链表使用示例 双向链表代码(list.h): 1 #ifndef _LIST_HEAD_H 2 #define _LIST_HEAD_H 3 // 双向链表节点 4 struct

    1.8K20

    Linux C 数据结构 ->单向链表

    简介   链表Linux 内核中最简单,最普通数据结构。...链表是一种存放和操作可变数量元素(常称为节点)   数据结构,链表和静态数组不同之处在于,它所包含元素都是动态创建并插入链表,在编译   时不必知道具体需要创建多少个元素,另外也因为链表中每个元素创建时间各不相同...根据它特性,链表可分为:单链表,双链表,单向循环链表和双向循环链表,今天总结记录就是   最简单链表,   1.1 节点类型描述   1 typedef struct node_t {   ...链表基本运算相关"算法"操作 or 操刀(~烹羊宰牛且为乐,会须一饮三百杯~)   链表运算除了上面的创建空链表,还有数据插入,删除,查找等函数,链表运算有各种实现方   法,如何写出一个高效...,封装性较好函数是我们要考虑,比如数据插入函数,我们就要尽可能   考虑所有能出现结果,比如:1)如果需插入数据链表是个空表;2)所插入位置超过了链表   长度;如果我们函数能包含所有能出现情况

    1.1K00

    【Leetcode】反转链表 合并链表 相交链表 链表回文结构

    【Leetcode21】合并两个有序链表 1.链接 合并两个有序链表 2.题目再现 3.三指针尾插法 思路:创建一个新链表,分别遍历两个链表,小就尾插到新链表,然后指针向后走一步,直到有一方为空时就结束循环...;结束循环后,判断哪个链表不为空,把不为空尾插到新链表中去。...【Leetcode160】相交链表 1.链接 相交链表 2.题目再现 3.解法 1.先分别遍历两个链表,记录下两个链表长度; 2.如果两个链表尾节点地址一样,则说明它们相交,否则不相交,(注意是地址不是值...); 3.求出两个链表长度差gap; 4.先让长链表走差距步gap,短链表先不动; 5.然后两个链表同时走一步,比较每走一步时两个链表当前节点地址,如果一样,则说明找到了它们相交起始位置...1.找到链表中间节点; 2.逆置链表中间节点以后部分,rmid 为后半部分逆置后第一个节点; 3.头指针 head 和 rmid 同时向后遍历,若 head 值不等于 rmid 值,则不是回文结构

    11110

    链表和双向链表实现

    前言 ---- 链表数据通过指针连接,添加、插入或删除节点只需要修改指针指向 实现思路 实现一个链表需要具备以下方法 在链表尾部添加节点 获取链表所有节点数据 链表指定位置插入元素 获取链表指定位置节点数据...获取节点在链表位置 更新链表指定位置数据 移除链表指定位置节点 移除链表指定节点 判断链表是否为空 获取链表长度 链表内部需要定义head指针和链表长度 实现代码 定义head指针和length...this.length += 1 } 获取链表所有节点数据 toString() { //声明空字符串存储链表节点数据 let listString = '' //获取第一个节点...(linkedList.size()) 双向链表 双向链表指针是双向,前指针指向上一个节点,后指针指向下一个节点 head指向第一个节点,tail指向最后一个节点 双向链表实现思路 需要具备以下方法...尾部插入元素 任意位置插入元素 获取所有节点数据 正向遍历链表获取节点数据 反向遍历链表获取节点数据 获取指定位置节点数据 获取指定数据在链表位置 更新指定位置节点数据 移除指定位置节点 移除指定数据节点

    70140

    Linux C语言链表详细分析

    链表是一种常见基础数据结构,结构体指针在这里得到了充分利用。...链表可以动态进行存储分配,也就是说,链表是一个功能极为强大数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入节点。链表都有一个头指针,一般以head来表示,存放是一个地址。...链表节点分为两类,头结点和一般节点,头结点是没有数据域链表中每个节点都分为两部分,一个数据域,一个是指针域。...作为有强大功能链表,对他操作当然有许多,比如:链表创建,修改,删除,插入,输出,排序,反序,清空链表元素,求链表长度等等。   ...  删除链表节点   删除链表元素也就是把前节点指针域越过要删除节点指向下下个节点。

    1.1K20

    Linux C语言链表你学会了吗?

    链表是一种常见基础数据结构,结构体指针在这里得到了充分利用。...链表可以动态进行存储分配,也就是说,链表是一个功能极为强大数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入节点。链表都有一个头指针,一般以head来表示,存放是一个地址。...链表节点分为两类,头结点和一般节点,头结点是没有数据域链表中每个节点都分为两部分,一个数据域,一个是指针域。...作为有强大功能链表,对他操作当然有许多,比如:链表创建,修改,删除,插入,输出,排序,反序,清空链表元素,求链表长度等等。   ...下面是一个传入链表和要修改节点,来修改值函数。

    1.3K20

    链表基本操作_简单链表

    链表基本操作 单链表 链表基本操作 一:单链表基础操作 二:单链表建立 头插法 尾插法 三:单链表遍历 四:单链表结点数目判断 五:单链表插入 链表头插入 任意结点插入 链表尾部插入...六:单链表删除 七 :单链表查询 一:单链表基础操作 为什么需要链表?...---- 二:单链表建立 单链表建立即从无到有创建一个链表,一个一个分配结点储存空间,然后输出每一个结点数据域,然后建立结点之间关系。...单链表建立可以分为两种方法,(1)头插法,(2)尾插法(更易理解) 头插法 即在单链表头部插入新结点方法成为头插法。 数据读入顺序和链表结点顺序正好相反。...计数器,每移动一次p指针且p指向不为空,iCount++; ---- 五:单链表插入 链表插入,有三种方式,可以从链表头部插入,可以从链表尾部插入,也可以在指定位置进行插入。

    60120

    leetcode链表之删除链表节点

    序 本文主要记录一下leetcode链表之删除链表节点 OIP (45).jpeg 题目 给定单向链表头指针和一个要删除节点值,定义一个函数删除该节点。 ​...返回删除后链表头节点。 ​...注意:此题对比原题有改动 ​ 示例 1: ​ 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 第二个节点,那么在调用了你函数之后,该链表应变为...示例 2: ​ 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 第三个节点,那么在调用了你函数之后,该链表应变为 4 -> 5 ->...说明: ​ 题目保证链表中节点值互不相同 若使用 C 或 C++ 语言,你不需要 free 或 delete 被删除节点 ​ 来源:力扣(LeetCode) 链接:https://leetcode-cn.com

    53900

    c++链表-C++链表

    C++链表   链表是由一系列连接在一起结点构成,其中每个结点都是一个数据结构。   ...除了数据之外,每个结点还包含一根后继指针指向链表下一个结点。   单个结点组成   非空链表第一个结点称为链表头。要访问链表结点,需要有一个指向链表指针。...从链表头开始,可以按照存储在每个结点中后继指针访问链表其余结点。最后一个结点中后继指针被设置为 以指示链表结束。   指向链表指针用于定位链表头部,所以也可以认为它代表了链表头。...由 3 个结点组成链表,其中显示了指向头部指针,链表 3 个结点以及表示链表末尾 指针。   链表结构图解   一、单向链表   单链表有一个头结点head,指向链表在内存首地址。...链表按此结构对各结点访问需从链表头找起,后续结点地址由当前结点给出。无论表中访问那一个结点,都需要从链表头开始。顺序向后查找。

    95820

    leetcode链表之删除链表节点

    序 本文主要记录一下leetcode链表之删除链表节点 题目 给定单向链表头指针和一个要删除节点值,定义一个函数删除该节点。 返回删除后链表头节点。...注意:此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 第二个节点,那么在调用了你函数之后,该链表应变为...示例 2: 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 第三个节点,那么在调用了你函数之后,该链表应变为 4 -> 5 ->...说明: 题目保证链表中节点值互不相同 若使用 C 或 C++ 语言,你不需要 free 或 delete 被删除节点 来源:力扣(LeetCode) 链接:https://leetcode-cn.com...cursor.next; } preNode.next = preNode.next.next; return head; } } 小结 这里关键在于要设计一个

    62420
    领券