深入分析 Linux 内核链表
深入分析 Linux 内核链表
级别： 初级
杨沙洲 (pubb@163.net)国防科技大学计算机学院
2004 年 8 月 01 日
本文详细分析了 2.6.x 内核中链表结构的实现，并通过实例对每个链表操作接口进行了详尽的讲解。
一、 链表数据结构简介
链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：
1． 单链表
图1 单链表
单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点（next），因此，对单链表的遍历只能从头至尾（通常是NULL空指针）顺序进行。
2． 双链表
图2 双链表
通过设计前驱和后继两个指针域，双链表可以从两个方向遍历，这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点（如图2中虚线部分），就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。
3． 循环链表
循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图，它的特点是从任意一个节点出发，沿两个方向的任何一个，都能找到链表中的任意一个数据。如果去掉前驱指针，就是单循环链表。
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。本文的后继部分就将通过示例详细介绍这一数据结构的组织和使用。
回页首
二、 Linux 2.6内核链表数据结构的实现
尽管这里使用2.6内核作为讲解的基础，但实际上2.4内核中的链表结构和2.6并没有什么区别。不同之处在于2.6扩充了两种链表数据结构：链表的读拷贝更新（rcu）和HASH链表（hlist）。这两种扩展都是基于最基本的list结构，因此，本文主要介绍基本链表结构，然后再简要介绍一下rcu和hlist。
链�
相关文档：
文章来源：http://dev.yesky.com/468/7601968.shtml
2007-10-12 11:01作者：宋宝华出处：天极网软件频道责任编辑：方舟
1.Linux文件系统
Linux支持多种文件系统，如ext、ext2、minix、iso9660、msdos、fat、vfat、nfs等。在这些具体文件系统的上层，Linux提供了虚拟文件系统（VFS）来统一它们的行为，虚拟文件系统为 ......
2.2 构建ARM Linux交叉编译工具链
构建交叉编译器的第一个步骤就是确定目标平台。在GNU系统中，每个目标平台都有一个明确的格式，这些信息用于在构建过程中识别要使用的不同工具的正确版本。因此，当在一个特定目标机下运行GCC时，GCC便在目录路径中查找包含该目标规范的应用程序路径。GNU的目标规范格式为CPU-PLATF ......
<!--
@page { margin: 2cm }
P { margin-bottom: 0.21cm }
-->
当前，一个很明显的事实是，
Linux
桌面并不普及。原因何在？
在
XP
盗版海洋中，普及
Linux
，谈何容易？十几年了，说尽
XP
盗版的坏话也无用（不灵验）。
Linux
国产化也失败了。问题究竟 ......
方便的linux命令手册
来源: ChinaUnix博客 日期： 2006.07.24 00:31 (共有0条评论) 我要评论
NO
分类
PS1
命令名
用法及参数
功能注解
对应章节
1
文件管理
#
ls
ls -a
列出当前目录下的所有文件，包括以.头的隐含文件
文件管理
#
ls
ls -l或ll
列出当前目录下文件的详细� ......
在linux的日常服务器维护站点维护中，经常需要批量操作一部分文件，比如数据库用户的资料变更，那么所以相关站点的数据库配置文件要相应的修改。大家都知道，linux下面几乎所有的配置文件都是纯粹的文本文件，所以这其实就是一个基本的文本操作。一台服务器上有上百个甚至上千个的网站。如果我们一个个来修改不是不可以，但 ......
