文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > linux 内核分析之list_head
侵权投诉

linux 内核分析之list_head

一、 链表数据结构简介

linux 内核分析之list_head

链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,

linux 内核分析之list_head

是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。

通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:

1. 单链表

图1 单链表

单链表是最简单的一类链表,它的特点是仅有一个指针域指向后继节点(next),因此,对单链表的遍历只能从头至尾(通常是NULL空指针)顺序进行。

2. 双链表

图2 双链表

通过设计前驱和后继两个指针域,双链表可以从两个方向遍历,这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系,就可以构成"二叉树";如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点(如图2中虚线部分),就构成了循环链表;如果设计更多的指针域,就可以构成各种复杂的树状数据结构。

3. 循环链表

循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图,它的特点是

第1页

你可能喜欢

热门文档

相关文档

  • linux 内核分析之list_head 双向链表结构

    linux 内核分析之 list_head 双向链表结构本文详细分析了 2.6.x 内核中链表结构的实现,并通过实例对每个链表操作接口进行了详尽的讲解。 链表数据结构简介 一、 ...

  • Linux内核之list_head

    Linux内核之list_head_IT/计算机_专业资料。关于Linux内核中的链表的实现原理和... 对于 RCU 的实现分析已超出了本文所及,有兴趣的读者可以自行参阅本文的参考...

  • linux内核部件分析-连通世界的list head

    linux内核部件分析-连通世界的list head_计算机软件及应用_IT/计算机_专业资料。在 linux 内核中,有一种通用的双向循环链表,构成了各种队列的基础。链表的结构定义...

  • 深入浅出linux内核源代码之双向链表list_head(list.h)

    Linux内核之list_head 23页 免费 深入分析 Linux 内核链表... 9页 免费 ...*/ static __inline__ void list_add(struct list_head *new, struct list...

  • linux内核head.S分析

    linux内核head.S分析_IT/计算机_专业资料。其中涉及到的文件有head.S head-...* * See linux/arch/arm/tools/mach-types for the complete list of ...

  • Linux内核链表list_head扩展---klist

    看SPI 驱动核心模块时,看到用到很多 klist,之前没多深入理解,现在来一步步分析源码。 klist 是对 list_head 的扩展,实现代码很少。内核代码: include/linux/...

  • Linux内核源码分析

    Linux 内核源码分析-链表代码分析 分析人:余旭 分析时间:2005 年 11 月 17 ...static inline void list_add(struct list_head *new, struct list_head *...

  • 分析Linux 内核链表

    深入分析 Linux 内核链表(转) 本文详细分析了 2.6.x 内核中链表结构的实现,...Linux为此提供了两个接口: static inline void list_add(struct list_head *...

  • Linux内核中的双循环链表解析

    下面我们将基于 Linux 2.4.21 分析 Linux 内核双循环链表的实现及应用。 声明和初始化 链表结构定义如下: struct list_head { struct list_head *next, *prev...

  • list_head小解析

    list_head 小解析 [Linux 内核] post by 陈俊生 / 2012-1-13 17:17 ...10.遍历 下面我们要分析链表的遍历。虽然涉及到遍历的宏比较多,但是根据我们前面...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email