[PHP] 链表数据结构（单链表）_PHP教程_ThinkSAAS
[PHP] 链表数据结构（单链表）
[PHP] 链表数据结构（单链表）
内容来源： 网络
链表：是一个有序的列表，但是它在内存中是分散存储的，使用链表可以解决类似约瑟夫问题，排序问题，搜索问题，广义表
单向链表，双向链表，环形链表
PHP的底层是C，当一个程序运行时，内存分成五个区（堆区，栈区，全局区，常量区，代码区）
规定：基本数据类型，一般放在栈区
复合数据类型，比如对象，放在堆区
定义一个类Hero
定义成员属性排名 $no
定义成员属性姓名 $name
定义成员属性昵称 $nickname
定义成员属性 $next，是一个引用，指向下一个Hero对象
定义构造函数，传递参数：$no，$name，$nickname
创建一个头head，该head只是一个头，不放入数据
获取$head对象，new Hero()
获取第一个Hero对象$hero，new Hero(1,”宋江”,”及时雨”)
连接两个对象，$head-&next=$hero
获取第二个Hero对象$hero2，new Hero(2,”卢俊义”,”玉麒麟”)
连接两个对象，$hero-&next=$hero2
遍历链表
定义一个函数showHeros()，参数：$head对象
定义一个临时变量$cur来存储 $head对象
while循环，条件$cur-&next不为null
打印一下
指针后移，$cur=$cur-&next
PHP版：
&?php
* 英雄类
class Hero{
public $no;
public $name;
public $nickname;
public $next=null;
public function __construct($no=&&,$name=&&,$nickname=&&){
$this-&no=$no;
$this-&name=$name;
$this-&nickname=$nickname;
class LinkListDemo{
public static function main(){
$head=new Hero();
$hero1=new Hero(1,"宋江","及时雨");
$head-&next=$hero1;
$hero2=new Hero(2,"卢俊义","玉麒麟");
$hero1-&next=$hero2;
LinkListDemo::showHeros($head);
* 展示英雄
public static function showHeros($head){
$cur=$head;
while($cur-&next!=null){
echo "姓名：".$cur-&next-&name."&br/&";
$cur=$cur-&next;
LinkListDemo::main();
java版：
class Hero{
public int
public S
public S
public Hero next=null;
public Hero(){
public Hero(int no,String name,String nickname) {
this.no=
this.name=
this.nickname=
public class LinkListDemo {
* @param args
public static void main(String[] args) {
Hero head=new Hero();
Hero hero1=new Hero(1, "宋江", "及时雨");
head.next=hero1;
Hero hero2=new Hero(2, "卢俊义", "玉麒麟");
hero1.next=hero2;
showHeros(head);
* 展示英雄
* @param head
public static void showHeros(Hero head){
Hero cur=
while(cur.next!=null){
System.out.println("姓名："+cur.next.name);
cur=cur.
内容来源：
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信2.3线性表的链式存储和运算―单链表基本运算
1. 建立单链表 (1)在链表的头部插入结点建立单链表 链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系
1. 建立单链表
(1)在链表的头部插入结点建立单链表
链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部，如图2.10 展现了线性表：（25,45,18,76,29）之链表的建立过程，因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。
算法如下：
LinkList Creat_LinkList1( )
{ LinkList L=NULL；/*空表*/
/*设数据元素的类型为int*/
scanf(＂%d＂,&x);
while (x!=flag)
{ s=malloc(sizeof(LNode));
s-&data=x;
s-&next=L; L=s;
Scanf (＂%d＂,&x);
(2)在单链表的尾部插入结点建立单链表
头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针r 用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部，如图2.11展现了在链表的尾部插入结点建立链表的过程。
算法思路：
初始状态：头指针H=NULL，尾指针r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到r 所指结点的后面，然后r 指向新结点（但第一个结点有所不同，读者注意下面算法中的有关部分）。
H=NULL r=NULL /*初始状态*/
算法如下：
LinkList Creat_LinkList2( )
{ LinkList L=NULL;
Lnode *s,*r=NULL;
/*设数据元素的类型为int*/
scanf(＂%d＂,&x);
while (x!=flag)
{ s=malloc(sizeof(LNode)); s-&data=x;
if (L==NULL) L=s; /*第一个结点的处理*/
else r-&next=s; /*其它结点的处理*/
r=s; /*r 指向新的尾结点*/
scanf(＂%d＂,&x);
if ( r!=NULL) r-&next=NULL; /*对于非空表，最后结点的指针域放空指针*/
在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针， 需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。&第一个结点&的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的，等等，为了方便操作，有时在链表的头部加入一个&头结点&，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。
头结点的加入使得&第一个结点&的问题不再存在，也使得&空表&和&非空表&的处理成为一致。
头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。图2.12(a)、（b）分别是带头结点的单链表空表和非空表的示意图。
算法思路：设一个移动指针ｐ和计数器ｊ，初始化后，ｐ所指结点后面若还有结点，ｐ向后移动，计数器加1。
(1)设L是带头结点的单链表(线性表的长度不包括头结点)。
算法如下：
int Length_LinkList1 (LinkList L)
{ Lnode * p=L; /* p指向头结点*/
while (p-&next)
{ p=p-& j++ } /* p所指的是第j 个结点*/
算法2.10(a)
(2)设L是不带头结点的单链表。
算法如下：
int Length_LinkList2 (LinkList L)
{ Lnode * p=L;
if (p==NULL) return 0; /*空表的情况*/
j=1; /*在非空表的情况下，p所指的是第一个结点*/;
while (p-&next )
{ p=p-& j++ }
算法2.10(b)
从上面两个算法中看到，不带头结点的单链表空表情况要单独处理，而带上头结点之后则不用了。在以后的算法中不加说明则认为单链表是带头结点的。算法2.10(a)、(b)的时间复杂度均为O(n)。
3. 查找操作
(1) 按序号查找Get_Linklist(L,i)
算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第ｉ个结点时返回空。算法如下：
Lnode * Get_LinkList(LinkList L, Int i);
/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/
{ Lnode * p=L;
while (p-&next !=NULL && j&i )
{ p=p-& j++; }
else return NULL;
算法2.11(a)
(2) 按值查找即定位Locate_LinkList(L,x)
算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空。算法如下：
Lnode * Locate_LinkList( LinkList L, datatype x)
/*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/
{ Lnode * p=L-&
while ( p!=NULL && p-&data != x)
算法2.11(b)
算法2.11(a)、(b)的时间复杂度均为O(n)。
(1)后插结点：
设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面，插入示意图如图2.13。操作如下：
①s-&next=p-&
②p-&next=s;
注意：两个指针的操作顺序不能交换。
(2)前插结点：
设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图2.14，与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下：
while (q-&next!=p)
q=q-& /*找*p的直接前驱*/
s-&next=q-&
q-&next=s;
后插操作的时间复杂性为O(1)，前插操作因为要找*p 的前驱，时间性能为O(n)；其实我们关心的更是数据元素之间的逻辑关系，所以仍然可以将*s 插入到*p 的后面，然后将ｐ-&data与s-&data交换即可，这样即满足了逻辑关系，也能使得时间复杂性为O(1)。
(3)插入运算Insert_LinkList(L,i,x)
算法思路：
1.找到第i-1个结点；若存在继续2，否则结束
2.申请、填装新结点；
3.将新结点插入。结束。
算法如下：
int Insert_LinkList( LinkList L, int i, datatype x)
/*在单链表L的第i个位置上插入值为x的元素*/
{ Lnode * p,*s;
p=Get_LinkList(L,i-1); /*查找第i-1个结点*/
if (p==NULL)
{ printf(＂参数i错＂);return 0; } /*第i-1个不存在不能插入*/
s=malloc(sizeof(LNode)); /*申请、填装结点*/
s-&data=x;
s-&next=p-& /*新结点插入在第i-1个结点的后面*/
算法2.12。算法2.12的时间复杂度为O(n)。
(1)删除结点：
设p指向单链表中某结点，删除*p。操作示意图如图2.15所示。
通过示意图可见，要实现对结点*p的删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：
q-&next=p-&
显然找*p前驱的时间复杂性为O(n)。若要删除*p的后继结点(假设存在)，则可以直接完成：
p-&next=s-&
该操作的时间复杂性为O(1) 。
(2)删除运算：Del_LinkList(L,i)
算法思路：
1.找到第i-1个结点；若存在继续2，否则结束；
2.若存在第i个结点则继续3，否则结束；
3.删除第i个结点，结束。
算法如下：
int Del_LinkList(LinkList L，int i)
/*删除单链表L上的第i个数据结点*/
{ LinkList p,s;
p=Get_LinkList(L,i-1); /*查找第i-1个结点*/
if (p==NULL)
{ printf(＂第i-1个结点不存在＂);return -1; }
else { if (p-&next==NULL)
{ printf(＂第i个结点不存在＂);return 0; }
{ s=p-& /*s指向第i个结点*/
p-&next=s-& /*从链表中删除*/
free(s); /*释放*s */
算法2.13。算法2.13的时间复杂度为O(n)。
通过上面的基本操作我们得知：
(1) 在单链表上插入、删除一个结点，必须知道其前驱结点。
(2) 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。
搜索相关文章：
(责任编辑：admin)
------分隔线----------------------------
不少学习C语言的同学在复印店购买了C语言程序设计的答案，计算中心强烈建议不要使用，...
Mysql4.1开始支持SQL的子查询。这个技术可以使用SELECT语句来创建一个单列的查询结果...
需要将自己设计的产品提供给他人使用时，针对前述的Sample工程，只需将链接产生的可执...
尽管在读取键盘输入时，scanf()是用得最多的函数，但有时最好还是不使用scanf()。这些...
如果两个指针向同一个数组，它们就可以相减，其为结果为两个指针之间的元素数目。仍以...
【真题1】 程序通过定义学生结构体变量，存储了学生的学号、姓名和3门课的成 绩。所有...C语言创建和操作单链表数据结构的实例教程
作者：xubin341719
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了C语言创建和操作单链表数据结构的实例教程,讲解使用C语言实现链表结构时指针的使用,需要的朋友可以参考下
1，为什么要用到链表
数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。
我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。
链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。
2，单向链表
单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。
如图所示：
上图还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。
3，单向链表程序的实现
（1），链表节点的数据结构定义
struct node
struct node *p;
在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。
在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。
（2），链表的创建、输出步骤
单链表的创建过程有以下几步：
1 ) 定义链表的数据结构;
2 ) 创建一个空表;
3 ) 利用malloc ( )函数向系统申请分配一个节点;
4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
节点接到表尾;
5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
单链表的输出过程有以下几步
1) 找到表头;
2) 若是非空表，输出节点的值成员，是空表则退出;
3 ) 跟踪链表的增长，即找到下一个节点的地址;
4) 转到2 ).
（3），程序代码例子：
创建一个存放正整数单链表，输入0或小于0的数，结束创建链表，并打印出链表中的值，程序如下：
#include &stdlib.h& /*含ma l l o c ( ) 的头文件*/
#include &stdio.h&
//①定义链表数据结构
struct node
struct node *
//函数声明
struct node *creat();
void print();
struct node *
head=NULL;
//②建一个空表
head=creat(head);/*创建单链表*/
print(head);/*打印单链表*/
/******************************************/
struct node*creat(struct node *head)/*返回的是与节点相同类型的指针*/
struct node*p1,*p2;
//③利用malloc ( )函数向系统申请分配一个节点
p1=p2=(struct node*)malloc(sizeof(struct node));/*新节点*/
printf("请输入值，值小于等于0结束，值存放地址为：p1_ADDR= %d\n",p1);
scanf("%d",&p1-&num);/*输入节点的值*/
p1-&next=NULL;/*将新节点的指针置为空*/
while(p1-&num&0)/*输入节点的数值大于0*/
//④将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾;
if(head==NULL)
head=p1;/*空表，接入表头*/
p2-&next=p1;/*非空表，接到表尾*/
p1=(struct node*)malloc(sizeof(struct node));/*下一个新节点*/
printf("请输入值，值小于等于0结束，值存放地址为：p%d_ADDR= %d\n",i,p2);
scanf("%d",&p1-&num);/*输入节点的值*/
//⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
//==============原来程序更正部分：（多谢@daling_datou提醒）================================
free(p1); //申请到的没录入，所以释放掉
//使指向空
p2-&next = NULL; //到表尾了，指向空
printf("链表输入结束（END）\n");
//==============================================
/*返回链表的头指针*/
/*******************************************/
void print(struct node*head)/*出以head为头的链表各节点的值*/
struct node *
temp=/*取得链表的头指针*/
printf("\n\n\n链表存入的值为：\n");
while(temp!=NULL)/*只要是非空表*/
printf("%6d\n",temp-&num);/*输出链表节点的值*/
temp=temp-&/*跟踪链表增长*/
printf("链表打印结束!!");
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。
程序执行流程：
4，单链表操作基础示例
#include &stdio.h&
#include &malloc.h&
#define LEN sizeof(NODE)
typedef struct _NODE//节点声明
struct _NODE*
} NODE, *PNODE;
void print(PNODE head){//打印所有节点
while (head)
printf("%3d",head-&val);
head = head-&
printf("\n");
void insertHead(PNODE *pHead, int val){//头插法
PNODE n = (PNODE)malloc(LEN);
n-&next = *pH
void insertTail(PNODE *pHead, int val){//尾插法
PNODE t = *pH
PNODE n = (PNODE)malloc(LEN);
n-&next = NULL;
if (*pHead == NULL)
n-&next = *pH
while (t-&next)
void deleteHead(PNODE *pHead){//删除头
if (*pHead == NULL)
PNODE t = *pH
*pHead = (*pHead)-&
void deleteTail(PNODE *pHead){//删除尾
PNODE t = *pH
if (t == NULL)
else if (t-&next == NULL)
*pHead = NULL;
while (t-&next-&next != NULL)
free(t-&next);
t-&next = NULL;
PNODE findByVal(PNODE head, int val){//根据值找到满足条件的第一个节点
while (head != NULL && head-&val != val)
head = head-&
PNODE findByIndex(PNODE head, int index){//根据索引找节点
if (index == 1)
int c = 1;
while (head != NULL && index != c)
head = head-&
void insertByIndex(PNODE *pHead, int index, int val){//根据索引插入节点
if (index == 1)
insertHead(pHead, val);
PNODE t = findByIndex(*pHead,index - 1);
if (t == NULL)
PNODE n = t-&
t-&next = (PNODE)malloc(LEN);
t-&next-&next =
t-&next-&val =
void deleteByIndex(PNODE *pHead, int index)//根据结点索引删除结点
if (index == 1)
deleteHead(pHead);
PNODE t= findByIndex(*pHead, index - 1);
if (t == NULL || t-&next == NULL)
PNODE n = t-&next-&
free(t-&next);
void deleteByVal(PNODE *pHead, int val)//根据值删掉第一个满足条件的
if (*pHead == NULL)//如果空表退出
if ((*pHead)-&val == val)//如果第一个就是，删头
deleteHead(pHead);
PNODE t = *pH
while (t-&next != NULL && t-&next-&val != val)//遍历，若t的next为空或者next是要找的节点则退出
if (t-&next)//如果t指向要找的结点的上一个节点
PNODE n = t-&next-&//删除要找的结点
free(t-&next);
void clear(PNODE *pHead)//清除链表
while ((*pHead) != NULL)
deleteHead(pHead);//从头删除
void main()
PNODE head = NULL;
insertTail(&head,1);
deleteHead(&head);
insertTail(&head,2);
insertTail(&head,3);
insertTail(&head,4);
insertTail(&head,5);
insertTail(&head,6);
print(head);
insertByIndex(&head, 6, 9);
print(head);
//deleteByIndex(&head,3);
deleteByVal(&head, 2);
print(head);
clear(&head);
print(head);
insertByIndex(&head,1,12);
print(head);
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具在线提问问题标题：问题描述：(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)C++技术网群幕群聊弹幕内核数据结构之——链表
转载请注明出处：
看内核代码时经常会遇到一些数据结构，包括链表，散列表，树等。之前遇到，仅仅只是从原理上了解大概是干嘛用的，没有深入详细分析代码。这里我想逐步就一些常用的数据结构进行总结，一些代码设计颇为精妙，对于自己编程也会有很大帮助。
1.1基本链表结构
链表是Linux内核中最简单也是最常用的数据结构。简单的链表结构形如：
循环链表（分别是单向循环链表和双向循环链表）：
尽管Linux中链表实现十分独特，但本质上是一个双向循环链表。
1.2Linux中链表的实现
自己之前写代码时，定义链表结点均类似上面所示，即将所需的数据结构包含在链表节点中。但是在Linux中，有很多数据结构需要使用链表将其串连，如，task_struct、super_block等等。这样如果按照传统的设计，对于每个链表，必须分别实现一组基本操作：初始化链表，插入删除元素，扫描链表等。这可能既浪费开发人员的精力，也因为对每个不同的链表都要重复相同的基本操作而造成存储空间的浪费。
为此，Linux将链表节点嵌入到需要形成链式结构的数据结构中。内核定义了list_head数据结构，如下所示：
228 &include/linux/types.h&
229 struct list_head {
struct list_head *next, *
显然，next和prev分别指向下一个和前一个list_head的地址，而并非包含list_head整个数据结构的地址。如下图所示：
那么，这样的list_head是如何使用的呢，也就是如何通过指向list_head的next\prev指针，来获取包含list_head的整个数据结构的地址？
Linux为此提供了一个list_entry(ptr,type,member)宏，其中ptr是指向该数据中list_head成员的指针，也就是存储在链表中的地址值，type是数据项的类型，member则是数据项类型定义中list_head成员的变量名。
例如：定义了如下一个结构
struct fox{
struct list_
struct list_head *p; //p指向fox_a中的list
struct fox *f;
则f可以这样获取fox_a的地址：
f=list_entry(p,struct fox, list);
下面具体看看其实现：
343 &include/linux/list.h&
* list_entry - get the struct for this entry
the &struct list_head pointer.
the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
350 #define list_entry(ptr, type, member) \
container_of(ptr, type, member)
由于在C语言中，一个数据结构分量的偏移地址在编译时就已经确定，则通过container_of()宏，能够很容易获取包含任意成员变量的父数据结构：
672 &include/linux/kernel.h&
* container_of - cast a member of a structure out to the containing structure
the pointer to the member.
the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
680 #define container_of(ptr, type, member) ({
const typeof( ((type *)0)-&member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member) );})
其中，offsetof定义如下（&include/linux/stddef.h&）：
20 #define offsetof(TYPE, MEMBER)
((size_t) &((TYPE *)0)-&MEMBER)
size_t最终定义为unsigned long（i386）。
这里使用的是一个利用编译器技术的小技巧，即先求得结构成员在与结构中的偏移量，然后根据成员变量的地址反过来得出属主结构变量的地址。
container_of()和offsetof()并不仅用于链表操作，这里最有趣的地方是
((type*)0)-&member，它将0地址强制&转换&为type结构的指针，再访问到type结构中的member成员。在container_of宏中，它用来给typeof()提供参数（typeof()是gcc的扩展，和sizeof()类似），以获得member成员的数据类型；在offsetof()中，这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。（看，符号&用于取地址，这里由于((TYPE*)0)的作用，也就是结构变量起始地址为0，那么获得MEMBER的地址当然是偏移值了。size_t再将地址类型强制转换为整数类型，用于减法）
***这样看上面的式子还是有些怪异，比如就前面f=list_entry(p,struct
fox, list); 这句话来说，宏展开后即为
const typeof( (( struct fox *)0)-&list)
* __mptr = (p);
( struct fox *)( (char *)__mptr – offsetof( struct fox,list) );
上面这个赋值语句，其右值为一个复合语句，问题就是既然复合语句能够赋值给f，那么这个复合语句的值又是多少呢？复合语句能作为右值出现么？我查了一下资料：（）GCC对C的扩展，有机会需要详细看看语法，现在就不管这么多吧。
在GNUC中，允许用小括号括起来的复合语句出现在一个表达式中。
例如下面程序：
运行结果：
因此，可以知道f的值实际上为该复合语句最后一句话的值，该语句返回一个struct fox *类型值。这样，所有问题应该都弄清楚了吧。
能够从嵌入的list_head类型变量的地址获取包含它的数据结构的地址，剩下的问题就好办了，这样便可以根据list_head定义一组关于链表的基本操作（Armed
with list_entry(), the kernel provides routines to create,manipulate, and otherwise manage linked lists—all without knowinganything about the structures that the list_head resides within.）：
1.3list_head相关操作（&include/linux/list.h&）
(1)定义链表(声明和初始化)
实际上Linux只定义了链表节点，并没有专门定义链表头，那么一个链表结构是如何建立起来的呢？让我们来看看LIST_HEAD()这个宏：
19 #define LIST_HEAD_INIT(name) { &(name), &(name) }
21 #define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
LIST_HEAD(name)定义了类型为list_head的新变量name，该变量作为新链表头的占位符，是一个哑元素，同时初始化了prev、next字段，让它们指向name变量本身，见前面图3-3。
对于很多包含list_head的数据结构，需要在动态运行时初始化，此时需要使用INIT_LIST_HEAD()内联函数进行初始化，如下：
24 static inline void INIT_LIST_HEAD(struct list_head *list)
list-&next =
list-&prev =
* list_empty - tests whether a list is empty
* @head: the list to test.
186 static inline int list_empty(const struct list_head *head)
return head-&next ==
* list_empty_careful - tests whether a list is empty and not being modified
* @head: the list to test
* Description:
* tests whether a list is empty _and_ checks that no other CPU might be
* in the process of modifying either member (next or prev)
* NOTE: using list_empty_careful() without synchronization
* can only be safe if the only activity that can happen
* to the list entry is list_del_init(). Eg. it cannot be used
* if another CPU could re-list_add() it.
204 static inline int list_empty_careful(const struct list_head *head)
struct list_head *next = head-&
return (next == head) && (next == head-&prev);
（3）插入/删除/移动/替换/合并/旋转
对链表的插入操作有两种：在指定节点后插入和之前插入。Linux为此提供了两个接口：
60 static inline void list_add(struct list_head *new, struct list_head *head)
__list_add(new, head, head-&next);
74 static inline void list_add_tail(struct list_head *new, struct list_head *head)
__list_add(new, head-&prev, head);
因为Linux链表是双向循环表，所以，list_add和list_add_tail的区别并不大，实际上，Linux最后均调用__list_add()函数：
* Insert a new entry between two known consecutive entries.
* This is only for internal list manipulation where we know
* the prev/next entries already!
37 static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
next-&prev =
new-&next =
new-&prev =
prev-&next =
99 static inline void __list_del_entry(struct list_head *entry)
__list_del(entry-&prev, entry-&next);
104 static inline void list_del(struct list_head *entry)
__list_del(entry-&prev, entry-&next);
entry-&next = LIST_POISON1;
entry-&prev = LIST_POISON2;
同时需要注意，list_del不会释放任何属于entry或者它所在数据结构的内存空间，仅仅是将entry元素从链表上摘下来：
设置LIST_POISON1和LIST_POISON2是为了保证不在链表中的节点项不可访问——对LIST_POSITION1和LIST_POSITION2的访问都将引起缺页。
86 static inline void __list_del(struct list_head * prev, struct list_head * next)
next-&prev =
prev-&next =
同时，内核提供了这样一个函数：
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
142 static inline void list_del_init(struct list_head *entry)
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
这样的好处是可以重利用从链表上删除的元素。
很简单，如下：153 static inline void list_move(struct list_head *list, struct list_head *head)
__list_del_entry(list);
list_add(list, head);
164 static inline void list_move_tail(struct list_head *list,
struct list_head *head)
__list_del_entry(list);
list_add_tail(list, head);
d)替换115 /**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
* If @old was empty, it will be overwritten.
122 static inline void list_replace(struct list_head *old,
struct list_head *new)
new-&next = old-&
new-&next-&prev =
new-&prev = old-&
new-&prev-&next =
131 static inline void list_replace_init(struct list_head *old,
struct list_head *new)
list_replace(old, new);
INIT_LIST_HEAD(old);
e）合并287 /**
* list_splice - join two lists, this is designed for stacks
* @list: the new list to add.
* @head: the place to add it in the first list.
292 static inline void list_splice(const struct list_head *list,
struct list_head *head)
if (!list_empty(list))
__list_splice(list, head, head-&next);
* list_splice_tail - join two lists, each list being a queue
* @list: the new list to add.
* @head: the place to add it in the first list.
304 static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
if (!list_empty(list))
__list_splice(list, head-&prev, head);
273 static inline void __list_splice(const struct list_head *list,
struct list_head *prev,
struct list_head *next)
struct list_head *first = list-&
struct list_head *last = list-&
first-&prev =
prev-&next =
last-&next =
next-&prev =
类似的，还有318 static inline void list_splice_init(struct list_head *list,
struct list_head *head)
if (!list_empty(list)) {
__list_splice(list, head, head-&next);
INIT_LIST_HEAD(list);
335 static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
if (!list_empty(list)) {
__list_splice(list, head-&prev, head);
INIT_LIST_HEAD(list);
f）旋转210 /**
* list_rotate_left - rotate the list to the left
* @head: the head of the list
214 static inline void list_rotate_left(struct list_head *head)
struct list_head *
if (!list_empty(head)) {
first = head-&
list_move_tail(first, head);
g）其他224 /**
* list_is_singular - tests whether a list has just one entry.
* @head: the list to test.
228 static inline int list_is_singular(const struct list_head *head)
return !list_empty(head) && (head-&next == head-&prev);
233 static inline void __list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
struct list_head *new_first = entry-&
list-&next = head-&
list-&next-&prev =
list-&prev =
entry-&next =
head-&next = new_
new_first-&prev =
* list_cut_position - cut a list into two
* @list: a new list to add all removed entries
* @head: a list with entries
* @entry: an entry within head, could be the head itself
and if so we won't cut the list
* This helper moves the initial part of @head, up to and
* including @entry, from @head to @list. You should
* pass on @entry an element you know is on @head. @list
* should be an empty list or a list you do not care about
* losing its data.
259 static inline void list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
if (list_empty(head))
if (list_is_singular(head) &&
(head-&next != entry && head != entry))
if (entry == head)
INIT_LIST_HEAD(list);
__list_cut_position(list, head, entry);
遍历是链表最经常的操作之一，为了方便核心应用遍历链表，Linux链表将遍历操作抽象成几个宏。
最基本的当然是list_for_each()宏，如下：
* list_for_each
iterate over a list
the &struct list_head to use as a loop cursor.
the head for your list.
369 #define list_for_each(pos, head) \
for (pos = (head)-& pos != (head); pos = pos-&next)
当然，遍历链表的目的是为了获取包含list_head结构的数据结构，那么此时可以这样使用，如下：static LIST_HEAD(fox_list);
struct list_head *p;
struct fox *f;
list_for_each(p, &fox_list){
f=list_entry(p,struct fox,list);
大多数内核使用list_for_each_entry()宏来遍历链表412 /**
* list_for_each_entry
iterate over list of given type
the type * to use as a loop cursor.
the head for your list.
* @member: the name of the list_struct within the struct.
418 #define list_for_each_entry(pos, head, member)
for (pos = list_entry((head)-&next, typeof(*pos), member);
&pos-&member != (head);
pos = list_entry(pos-&member.next, typeof(*pos), member))
某些应用需要反向遍历链表，Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作，使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。
如果遍历不是从链表头开始，而是从已知的某个节点pos开始，则可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求，即经过一系列计算后，如果pos有值，则从pos开始遍历，如果没有，则从链表头开始，为此，Linux专门提供了一个list_prepare_entry(pos,head,member)宏，将它的返回值作为list_for_each_entry_continue()的pos参数，就可以满足这一要求。
遍历时节点删除
前面介绍了用于链表遍历的几个宏，它们都是通过移动pos指针来达到遍历的目的。但如果遍历的操作中包含删除pos指针所指向的节点，pos指针的移动就会被中断，因为list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
当然，调用者完全可以自己缓存next指针使遍历操作能够连贯起来，但为了编程的一致性，Linux链表仍然提供了两个对应于基本遍历操作的&_safe&接口：list_for_each_safe(pos,n,
head)、list_for_each_entry_safe(pos,n, head,member)，它们要求调用者另外提供一个与pos同类型的指针n，在for循环中暂存pos下一个节点的地址，避免因pos节点被释放而造成的断链。
* list_for_each_safe - iterate over a list safe against removal of list entry
the &struct list_head to use as a loop cursor.
another &struct list_head to use as temporary storage
the head for your list.
397 #define list_for_each_safe(pos, n, head) \
for (pos = (head)-&next, n = pos-& pos != (head); \
pos = n, n = pos-&next)
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
the type * to use as a loop cursor.
another type * to use as temporary storage
the head for your list.
* @member: the name of the list_struct within the struct.
492 #define list_for_each_entry_safe(pos, n, head, member)
for (pos = list_entry((head)-&next, typeof(*pos), member),
n = list_entry(pos-&member.next, typeof(*pos), member); \
&pos-&member != (head);
pos = n, n = list_entry(n-&member.next, typeof(*n), member))
对于其他一些定义的宏或者函数，功能和作用也都类似，这里就不再分析了，Linux链表这块，差不多就结束了吧，以后如果发现有意思的新内容再添加吧。
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？