一.为什么需要链表？

(1)数组有2个缺陷，

• 数组中所有元素的类型必须一致；
• 数组的元素个数必须事先指定并且一旦指定之后不能更改。

(2)如何解决数组的2个缺陷：

数组的第一个缺陷靠结构体去解决。结构体允许其中的元素的类型不相同，因此解决了数组的第一个缺陷。所以说结构体是因为数组不能解决某些问题所以才发明的。

(3)如何解决数组的第二个缺陷？
我们希望数组的大小能够实时扩展。

譬如我刚开始定了一个元素个数是10，后来程序运行时觉得不够因此动态扩展为20。

普通的数组显然不行，我们可以对数组进行封装以达到这种目的；我们还可以使用一个新的数据结构来解决，这个新的数据结构就是链表。

二.单链表的实现

链表就是一个元素个数可以实时变大/变小的数组。

(1)链表是由节点组成的，节点中包含：有效数据和指针。
(2)定义的struct node只是一个结构体*，本身并没有变量生成，也不占用内存。

结构体定义相当于为链表节点定义了一个模板，但是还没有一个节点，将来在实际创建链表时需要一个节点时用这个模板来复制一个即可。

有效数据区域用来存储信息完成任务的，指针区域用于指向链表的下一个节点从而构成链表。

(3)链表的内存要求比较灵活，不能用栈，也不能用data数据段。只能用堆内存。

1.使用堆内存来创建一个链表节点的步骤

• 要用的c库

#include<stdio.h>
#include<stdlib.h>

• 创建结构体节点

struct node
{int date;    //节点数据struct node *pNext;    //指向下一个节点的指针};

• 头指针*并不是节点，而是一个普通指针，只占4字节。头指针的类型是struct node 类型的，所以它才能指向链表的节点。

头指针指向链表的第1个节点，然后第1个节点中的指针指向下一个节点，然后依次类推一直到最后一个节点。这样就构成了一个链。

struct node * pHeader = NULL;

• 申请堆内存，大小为一个节点的大小（检查申请结果是否正确）；
  使用malloc函数

malloc(类型)

struct node * p = (struct node *)malloc(sizeof(struct node));

• 判断申请到的堆内存空间是否为NULL,申请失败返回-1

if (NULL == p)    //最好把NULL写在前面
{printf("malloc error.\n");return -1;
}

• 清理申请到的堆内存；
  使用bzero或者memset函数
  

bzero(p, sizeof(struct node));

• 现在就可以将节点的数据和指向下一个节点的指针赋值

p->data = 1;
p->pNext = NULL;

• 理清前后指针连接关系

pHeader = p;

实例：构建一个链表，然后将一些数据（譬如1，2，3三个数字）存储在链表中

先简单实现，还未用函数

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>//创建一个节点结构体
struct node
{int data;    //数据struct node *pNext;   //指向下一个节点的指针};int main(void)
{//创建一个头指针,先置为null,再有了其它节点再进行关联，这个主要用来指向头指针struct node *pHeader = NULL;/**************************************************************///创建一个新节点，并且要把前后节点关联起来struct node *p = (struct node *)malloc(sizeof(struct node));//判断申请的空间是否为NULL，malloc的返回值：成功申请空间后返回这个内存空间的指针，//申请失败时返回NULL。所以**malloc获取的内存指针使用前一定要先检验是否为NULLif (NULL == p){printf("malloc error.\n");return -1;}//清理申请到的堆内存bzero(p, sizeof(struct node));p->data = 1;     //该节点的数据p->pNext = NULL;  //暂时没关联其它节点，先置为nullpHeader = p; //将头结点指向该节点的首地址/**********************************************************//**********************************************************///创建第2个节点struct node *p1 = (struct node *)malloc(sizeof(struct node));//判断申请的空间是否为NULL，malloc的返回值：成功申请空间后返回这个内存空间的指针，//申请失败时返回NULL。所以**malloc获取的内存指针使用前一定要先检验是否为NULLif (NULL == p1){printf("malloc error.\n");return -1;}//清空申请到的内存bzero(p1, sizeof(struct node));p1->data = 2;p1->pNext = NULL;p->pNext = p1;/**********************************************************//**********************************************************///创建第3个节点struct node *p2 =  (struct node *)malloc(sizeof(struct node));//判断申请的空间是否为NULLif (NULL == p2){printf("malloc error.\n");return -1;}		//申请到的空间清零bzero(p2,sizeof(struct node));p2->data = 3;p1->pNext = p2;/**********************************************************///至此3个节点创建完成}

2.插入节点

2.1、访问链表中各个节点的数据

(1)只能用头指针，不能用各个节点自己的指针。因为在实际当中我们保存链表的时候是不会保存各个节点的指针的，只能通过头指针来访问链表节点。

(2)前一个节点内部的pNext指针能帮助我们找到下一个节点。

/**********************************************************///使用头指针访问链表中各个节点的数据//访问第一个节点的数据printf("p->data = %d.\n", pHeader->data);  //之前在单链表的简单创建中我们已经将p的指针（左值）赋值给pHeader（右值）//所以这里相当于p->dataprintf("p->data = %d.\n", p->data);    //访问第2个节点printf("p1->data = %d.\n", pHeader->pNext->data);  //此时相当于p1-dataprintf("p1->data = %d.\n", p1->data);//访问第3个节点printf("p2->data = %d.\n", pHeader->pNext->pNext->data);  //p2->dataprintf("p2->data = %d.\n", p2->data);/**********************************************************/

运行显示结果相等：

2.2、 将创建节点的代码封装成一个函数

之前简单的直接实现了一个单链表
现在要创建函数来实现复用

封装时的关键点就是函数的接口（函数参数和返回值）的设计v

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>//创建一个结构体节点
struct node
{int data;                //存储的有效数据struct node *pNext;      //指向下一个节点的指针};// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error.\n");return NULL;}// 清理申请到的堆内存bzero(p, sizeof(struct node));// 填充节点p->data = data;p->pNext = NULL;return p;}int main(void)
{struct node * pHeader = NULL;pHeader = create_node(1);    //其实就是pHeader = p;pHeader->pNext = create_node(2);   //p->pNext = p1;pHeader->pNext->pNext = create_node(3);   //p1->pNext = p2;printf("node1 %d.\n", pHeader->data);   //p->dataprintf("node2 %d.\n", pHeader->pNext->data);   //p1->dataprintf("node3 %d.\n", pHeader->pNext->pNext->data);   //p2->datareturn 0;}

2.3封装函数插入新节点

2.3.1、 尾插法

从链表尾部插入新节点
尾部插入简单点，因为前面已经建立好的链表不用动。直接动最后一个就可以了。

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>//创建一个结构体节点
struct node
{int data;                //存储的有效数据struct node *pNext;      //指向下一个节点的指针};// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error.\n");return NULL;}// 清理申请到的堆内存bzero(p, sizeof(struct node));// 填充节点p->data = data;p->pNext = NULL;return p;}// 思路：由头指针向后遍历，直到走到原来的最后一个节点。
//原来最后一个节点里面的pNext是NULL，现在我们只要将它改成new就可以了。添加了之后新节点就变成了最后一个
void insert_tail(struct node *pH, struct node *new)
{// 分两步来完成插入// 第一步，先找到链表中最后一个节点struct node *p = pH;while (NULL != p->pNext){p = p->pNext;   //往后走}// 第二步，将新节点插入到最后一个节点尾部p->pNext = new;}int main(void)
{//struct node * pHeader = NULL;  //这么把pHdear再调用插入调用插入函数会发生段错误struct node * pHeader = create_node(0);    //头节点insert_tail(pHeader, create_node(1));    //注意这里是两个节点，一个是头结点，另一个是新插入的节点insert_tail(pHeader, create_node(2));insert_tail(pHeader, create_node(3));printf("node1 %d.\n", pHeader->data);   //p->dataprintf("node2 %d.\n", pHeader->pNext->data);   //p1->dataprintf("node3 %d.\n", pHeader->pNext->pNext->data);   //p2->datareturn 0;}

什么是头节点

1. 问题：因为我们在insert_tail中直接默认了头指针指向的有一个节点，因此如果程序中直接定义了头指针对于NULL后就直接insert_tail就会报段错误。
   我们不得不在定义头指针之后先create_node创建一个新节点给头指针初始化，否则不能避免这个错误；但是这样解决让程序看起来逻辑有点不太顺，因为看起来第一个节点和后面的节点的创建、添加方式有点不同。
2. 链表还有另外一种用法，就是把头指针指向的第一个节点作为头节点使用。
   头节点的特点是：
   第一，它紧跟在头指针后面。
   第二，头节点的数据部分是空的（有时候不是空的，而是存储整个链表的节点数），指针部分指向下一个节点，也就是第一个节点。
3. 这样看来，头节点确实和其他节点不同。我们在创建一个链表时添加节点的方法也不同。头节点在创建头指针时一并创建并且和头指针关联起来；后面的真正的存储数据的节点用节点添加的函数来完成，譬如insert_tail.
4. 链表有没有头节点是不同的。体现在链表的插入节点、删除节点、遍历节点、解析链表的各个算法函数都不同。所以如果一个链表设计的时候就有头节点那么后面的所有算法都应该这样来处理；如果设计时就没有头节点，那么后面的所有算法都应该按照没有头节点来做。实际编程中两种链表都有人用，所以大家在看别人写的代码时一定要注意看它有没有头节点。

规范：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//创建一个链表的节点
struct node
{int data;                   //有效数据struct node *pNext;         //指向下一个节点的指针
};// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{//malloc申请堆内存struct node * p = (struct node *)malloc(sizeof(struct node));//判断是否申请到堆内存if (NULL == p){printf("malloc error.\n");return NULL;}//清空堆内存bzero(p, sizeof(struct node));//赋值p->data = data;p->pNext = NULL;return p;
}// 思路：由头指针向后遍历，直到走到原来的最后一个节点。原来最后一个节点里面的pNext是NULL，现在我们只要将它改成new就可以了。添加了之后新节点就变成了最后一个。
// 计算添加了新的节点后总共有多少个节点，然后把这个数写进头节点中。
//有头结点的尾插法,头结点存放插入节点的个数
void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;    //用来记录节点个数struct node *p = pH;    //指向头结点// 分两步来完成插入// 第一步，先找到链表中最后一个节点//判断下一个节点是否空，不为空就继续向后遍历，并记录节点个数while (NULL != p->pNext){p = p->pNext;   // 往后走一个节点cnt++;}// 第二步，将新节点插入到最后一个节点尾部p->pNext = new;    //为空跳出while 循环，并将new节点赋上pH->data = cnt + 1;    //遍历完成后即是当前节点个数（除了头节点）,加1是因为循环里面的只是之前插入的节点总个数，现在加入了一个新节点，所以加1
}int main(void)
{struct node *pHeader = create_node(0);insert_tail(pHeader, create_node(1));insert_tail(pHeader, create_node(2));insert_tail(pHeader, create_node(3));printf("header node : %d.\n", pHeader->data);    //头结点中存储的插入节点的总个数printf("node1: %d.\n", pHeader->pNext->data);  //p->dataprintf("node2: %d.\n", pHeader->pNext->pNext->data);   //p1->dataprintf("node3: %d.\n", pHeader->pNext->pNext->pNext->data); //p2->datareturn 0;}

2.3.2、头插法

从链表头部插入新节点

(1)注意写代码过程中的箭头符号，和说话过程中的指针指向。这是两码事，容易搞混。箭头符号实际上是用指针方式来访问结构体，所以箭头符号的实质是访问结构体中的成员。更清楚一点说程序中的箭头和链表的连接没有任何关系；链表中的节点通过指针指向来连接，编程中表现为一个赋值语句（用=来进行连接），实质是把后一个节点的首地址，赋值给前一个节点中的pNext元素做为值。
(2)链表可以从头部插入，也可以从尾部插入。也可以两头插入。头部插入和尾部插入对链表来说几乎没有差别。对链表本身无差别，但是有时候对业务逻辑有差别。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//创建一个结构体节点
struct node
{int data;                   //有效数据struct node *pNext;         //指向下一个节点的指针
};//创建节点
struct node * create_node(int data)
{//malloc申请堆内存struct node * p = (struct node *)malloc(sizeof(struct node));//判断是否申请到堆内存if (NULL == p){printf("malloc error.\n");return NULL;}//清空堆内存bzero(p, sizeof(struct node));//赋值p->data = data;p->pNext = NULL;return p;
}//有头结点的尾插法,头结点存放节点的个数
void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;    //用来记录节点个数struct node *p = pH;    //指向头结点//判断下一个节点是否空，不为空就继续向后遍历，并记录节点个数while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;    //为空跳出while 循环，并将new节点赋上pH->data = cnt + 1;    //遍历完成后即是当前节点个数（除了头节点）,加1是因为循环里面的只是之前插入的节点总个数，现在加入了一个新节点，所以加1
}//头插法,在原来的第一个节点前面插入
void insert_head(struct node *pH, struct node *new)
{//新节点的next指向原来的第一个节点new->pNext = pH->pNext;//头结点的next指向新节点的地址pH->pNext = new;//头结点中的计数加1pH->data += 1;
}int main(void)
{//struct node * pHeader = NULL;  //这么把pHdear再调用插入调用插入函数会发生段错误 ，没有头节点容易出现段错误/*尾插法struct node *pHeader = create_node(0);insert_tail(pHeader, create_node(1));insert_tail(pHeader, create_node(2));insert_tail(pHeader, create_node(3));printf("header node : %d.\n", pHeader->data);    //头结点中存储的插入节点的总个数printf("node1: %d.\n", pHeader->pNext->data);  //p->dataprintf("node2: %d.\n", pHeader->pNext->pNext->data);   //p1->dataprintf("node3: %d.\n", pHeader->pNext->pNext->pNext->data); //p2->data*///头插法struct node * pHeader = create_node(0);    //头节点insert_head(pHeader, create_node(3));    //注意这里是两个节点，一个是头结点，另一个是新插入的节点insert_head(pHeader, create_node(2));insert_head(pHeader, create_node(1));printf("header node : %d.\n", pHeader->data);    //头结点中存储的插入节点的总个数printf("node1: %d.\n", pHeader->pNext->data);  //p->dataprintf("node2: %d.\n", pHeader->pNext->pNext->data);   //p1->dataprintf("node3: %d.\n", pHeader->pNext->pNext->pNext->data); //p2->datareturn 0;}

3.遍历节点

3.1、什么是遍历

(1)遍历就是把单链表中的各个节点挨个拿出来，就叫遍历。
(2)遍历的要点：一是不能遗漏、二是不能重复、追求效率。

3.2、如何遍历单链表

(1)分析一个数据结构如何遍历，关键是分析这个数据结构本身的特点。然后根据本身特点来制定它的遍历算法。

(2)单链表的特点就是由很多个节点组成，头指针+头节点为整个链表的起始，最后一个节点的特征是它内部的pNext指针值为NULL。从起始到结尾中间由各个节点内部的pNext指针来挂接。由起始到结尾的路径有且只有一条。单链表的这些特点就决定了它的遍历算法。

(3)遍历方法：从头指针+头节点开始，顺着链表挂接指针依次访问链表的各个节点，取出这个节点的数据，然后再往下一个节点，直到最后一个节点，结束返回。

3.3、写一个链表遍历的函数，void bianli(struct node*pH);

错误示范1：

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>struct node
{int data;struct node *pNext;};struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(struct node));p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;struct node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了struct node *p = pH;printf("-----------开始遍历-----------\n");while (NULL != p->pNext){printf("node data :%d.\n", p->data);}		printf("-------------完了-------------\n");
}int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(1));insert_head(pHeader, create_node(2));insert_head(pHeader, create_node(3));printf("beader node data: %d.\n", pHeader->data);	bianli(pHeader);}

运行时产生循环打印错误：

原因是while循环里没有增量

错误示范2：

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>struct node
{int data;struct node *pNext;};struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(struct node));p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;struct node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了struct node *p = pH;printf("-----------开始遍历-----------\n");while (NULL != p->pNext){printf("node data :%d.\n", p->data);p = p->pNext;  //增加增量}		printf("-------------完了-------------\n");
}int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(11));insert_head(pHeader, create_node(12));insert_head(pHeader, create_node(13));printf("beader node data: %d.\n", pHeader->data);	bianli(pHeader);}

运行结果没有11：

原因是头指针直接指向头结点，在循环里先打印了头结点的数据

错误示范3：

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>struct node
{int data;struct node *pNext;};struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(struct node));p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;struct node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了//struct node *p = pH;   //这里头指针直接遍历到了头节点，所以在循环里p->data会先打印头结点的数据struct node *p = pH->pNext;   //指向第一个节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext){printf("node data :%d.\n", p->data);p = p->pNext;  //增加增量}		printf("-------------完了-------------\n");
}int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(11));insert_head(pHeader, create_node(12));insert_head(pHeader, create_node(13));printf("beader node data: %d.\n", pHeader->data);	bianli(pHeader);}

正确做法：

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>struct node
{int data;struct node *pNext;};struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(struct node));p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;struct node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了//struct node *p = pH;   //这里头指针直接遍历到了头节点，所以在循环里p->data会先打印头结点的数据struct node *p = pH->pNext;   //指向第一个节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext){printf("node data :%d.\n", p->data);p = p->pNext;  //增加增量}		printf("node data: %d.\n", p->data);printf("-------------完了-------------\n");
}int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(11));insert_head(pHeader, create_node(12));insert_head(pHeader, create_node(13));printf("beader node data: %d.\n", pHeader->data);	bianli(pHeader);}

因为循环到最后一个节点已经是指向NULL,所以直接跳出循环，没有打印最后一个节点

使用do while还是一样的情况

void bianli1(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了//struct node *p = pH;   //这里头指针直接遍历到了头节点，所以在循环里p->data会先打印头结点的数据struct node *p = pH->pNext;   //指向第一个节点printf("-----------开始遍历-----------\n");do{printf("node data :%d.\n", p->data);p = p->pNext;  //增加增量}while (NULL != p->pNext);	//printf("node data: %d.\n", p->data);printf("-------------完了-------------\n");
}

我们可以在while完成后再打印一次

优化：

#include <stdio.h>
#include <strings.h>
#include <stdlib.h>struct node
{int data;struct node *pNext;};struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(struct node));p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;struct node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(struct node *pH)
{//pH->data    //头节点，不是链表的常规数据，就不要算进去了//struct node *p = pH;   //这里头指针直接遍历到了头节点，所以在循环里p->data会先打印头结点的数据struct node *p = pH->pNext;   //指向第一个节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext){printf("node data :%d.\n", p->data);p = p->pNext;  //增加增量}		printf("node data: %d.\n", p->data);printf("-------------完了-------------\n");
}//正确优化思路
void bianli2(struct node *pH)
{struct node *p = pH;  //头节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext){p = p->pNext;     printf("node data: %d.\n", p->data);}printf("-------------完了-------------\n");}int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(11));insert_head(pHeader, create_node(12));insert_head(pHeader, create_node(13));printf("beader node data: %d.\n", pHeader->data);	bianli2(pHeader);}

4.删除节点

4.1、为什么要删除节点

(1)一直在强调，链表到底用来干嘛的？
(2)有时候链表节点中的数据不想要了，因此要删掉这个节点。

4.2、删除节点的2个步骤

第一步：找到要删除的节点；

第二步：删除这个节点。

4.3、如何找到待删除的节点

(1)通过遍历来查找节点。从头指针+头节点开始，顺着链表依次将各个节点拿出来，按照一定的方法比对，找到我们要删除的那个节点。

4.4、如何删除一个节点

(1)待删除的节点不是尾节点的情况:首先把待删除的节点的前一个节点的pNext指针指向待删除的节点的后一个节点的首地址（这样就把这个节点从链表中摘出来了），然后再将这个摘出来的节点free掉接口。

(2)待删除的节点是尾节点的情况：首先把待删除的尾节点的前一个节点的pNext指针指向null（这时候就相当于原来尾节点前面的一个节点变成了新的尾节点），然后将摘出来的节点free掉。

4.5、注意堆内存的释放

(1)前面我们写的代码最终都没有释放堆内存。当程序都结束了的情况下那些没有free的堆内存也被释放了。

(2)有时候我们的程序运行时间很久，这时候malloc的内存如果没有free会一直被占用直到你free释放它或者整个程序终止。

实例代码：

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 构建一个链表的节点
struct node
{int data;                     // 有效数据struct node * pNext;           // 指向下一个节点的指针};// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error.\n");return NULL;}// 清理申请到的堆内存bzero(p, sizeof(struct node));// 填充节点p->data = data;p->pNext = NULL;return p;}//尾插法
// 思路：由头指针向后遍历，直到走到原来的最后一个节点。原来最后一个节点里面的pNext是NULL，现在我们只要将它改成new就可以了。添加了之后新节点就变成了最后一个。
// 计算添加了新的节点后总共有多少个节点，然后把这个数写进头节点中。
void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;// 分两步来完成插入// 第一步，先找到链表中最后一个节点struct node *p = pH;while (NULL != p->pNext){p = p->pNext;   // 往后走一个节点cnt++;}// 第二步，将新节点插入到最后一个节点尾部p->pNext = new;pH->data = cnt +1;
}//头插法
void insert_head(struct node *pH, struct node *new)
{// 第1步： 新节点的next指向原来的第一个节点new->pNext = pH->pNext;// 第2步： 头节点的next指向新节点的地址pH->pNext = new;// 第3步： 头节点中的计数要加1pH->data += 1;}//正确优化思路
void bianli(struct node *pH)
{//pH->data				// 头节点数据，不是链表的常规数据，不要算进去了struct node *p = pH;  //头节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext)  // 是不是最后一个节点{p = p->pNext;        // 走到下一个节点，也就是循环增量printf("node data: %d.\n", p->data);}printf("-------------完了-------------\n");}// 从链表pH中删除节点，待删除的节点的特征是数据区等于data
// 返回值：当找到并且成功删除了节点则返回0，当未找到节点时返回-1
int delete_node(struct node *pH, int data)
{// 找到这个待删除的节点，通过遍历链表来查找struct node *p = pH;          // 用来指向当前节点struct node *pPrev = NULL;    // 用来指向当前节点的前一个节点while (NULL != p->pNext)  //判断该节点的下一个节点是否为NULL{pPrev = p;       //指向该节点的前一个节点，在p走向下一个节点前先将其保存p = p->pNext;    //不为NULL，指向该节点的下一个节点// 判断这个节点是不是我们要找的那个节点if (p->data == data)  {// 找到了节点，处理这个节点// 分为2种情况，一个是找到的是普通节点，另一个是找到的是尾节点// 删除节点的困难点在于：通过链表的遍历依次访问各个节点，找到这个节点// 后p指向了这个节点，但是要删除这个节点关键要操作前一个节点，但是这// 时候已经没有指针指向前一个节点了，所以没法操作。解决方案就是增加// 一个指针指向当前节点的前一个节点//情况1，尾节点if (NULL == p->pNext){pPrev->pNext = NULL;    //该节点的前一个节点指向NULL，成为新的尾节点free(p);                //释放该节点}else   //情况2，普通节点{pPrev->pNext = p->pNext;   //该节点的前一个节点指向该节点的后一个节点free(p);}// 处理完成之后退出程序return 0;}	}	//没找到，说明链表中没有给节点printf("链表中没有找到这个节点.\n");return -1;}int main(void)
{struct node *pHeader = create_node(0);/*insert_tail(pHeader, create_node(11));insert_tail(pHeader, create_node(22));insert_tail(pHeader, create_node(33));*/insert_head(pHeader, create_node(33));insert_head(pHeader, create_node(22));insert_head(pHeader, create_node(11));printf("pHeader node data : %d.\n", pHeader->data);bianli(pHeader);delete_node(pHeader, 22);printf("删除一个节点后：.\n");bianli(pHeader);delete_node(pHeader, 11);delete_node(pHeader, 33);printf("全部删除后：.\n");bianli(pHeader);}

但是在这个函数中，当遇到有相同数据的节点时，只会删除到遍历到的第一个节点

5.单链表的逆序

5.1、什么是链表的逆序

(1)链表的逆序又叫反向，意思就是把链表中所有的有效节点在链表中的顺序给反过来

5.2 、单链表逆序算法分析

(1)当我们对一个数据结构进行一个操作时，我们就需要一套算法。这就是数据结构和算法的关系。

(2)第一个层次是数学和逻辑上的算法；第二次个层次是用编程语言来实现算法。

(3)从逻辑上来讲，链表的逆序有很多种方法。这些方法都能实现最终的需要，但是效率是不一样的。彼此的可扩展性、容错性等不同。

(4)思路：首先遍历原链表，然后将原链表中的头指针和头节点作为新链表的头指针和头节点，原链表中的有效节点挨个依次取出来，采用头插入的方法插入新链表中即可。

(5)链表逆序 = 遍历 + 头插入

5.3、实例

简单实现方法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 构建一个链表的节点struct node 
{int data;                       // 有效数据struct node *pNext;             // 指向下一个节点的指针};// 作用：创建一个链表节点
// 返回值：指针，指针指向我们本函数新创建的一个节点的首地址
struct node * create_node(int data)
{struct node *p = (struct node *)malloc(sizeof(struct node));if (NULL == p){printf("malloc error.\n");return NULL;}// 清理申请到的堆内存bzero(p, sizeof(struct node));// 填充节点p->data = data;p->pNext = NULL;return p;}void insert_tail(struct node *pH, struct node *new)
{int cnt = 0;// 分两步来完成插入// 第一步，先找到链表中最后一个节点struct node *p = pH;while (NULL != p->pNext){p = p->pNext;    // 往后走一个节点cnt++;}// 第二步，将新节点插入到最后一个节点尾部p->pNext = new;pH->data = cnt + 1;}void insert_head(struct node *pH, struct node *new)
{// 第1步： 新节点的next指向原来的第一个节点new->pNext = pH->pNext;// 第2步： 头节点的next指向新节点的地址pH->pNext = new;// 第3步： 头节点中的计数要加1pH->data += 1;}// 遍历单链表，pH为指向单链表的头指针，遍历的节点数据打印出来
void bianli(struct node *pH)
{struct node *p = pH;  // 头指针后面是头节点printf("-----------开始遍历-----------\n");while (NULL != p->pNext)   // 是不是最后一个节点{p = p->pNext;    // 走到下一个节点，也就是循环增量printf("node data : %d.\n", p->data);}printf("-------------完了-------------\n");
}// 从链表pH中删除节点，待删除的节点的特征是数据区等于data
// 返回值：当找到并且成功删除了节点则返回0，当未找到节点时返回-1
int delete_node(struct node *pH, int data)
{// 找到这个待删除的节点，通过遍历链表来查找struct node *p = pH;                        // 用来指向当前节点struct node *pPrev = NULL;                   // 用来指向当前节点的前一个节点while (NULL != p->pNext)           // 是不是最后一个节点{pPrev = p;                       // 在p走向下一个节点前先将其保存p = p->pNext;                    // 走到下一个节点，也就是循环增量// 判断这个节点是不是我们要找的那个节点if (p->data == data){if (NULL == p->pNext){// 尾节点pPrev->pNext = NULL;           // 原来尾节点的前一个节点变成新尾节点free(p);                       // 释放原来的尾节点的内存}else{// 普通节点pPrev->pNext = p->pNext;   // 要删除的节点的前一个节点和它的后一个节点相连，这样就把要删除的节点给摘出来了free(p);}// 处理完成之后退出程序return 0;}}// 到这里还没找到，说明链表中没有我们想要的节点printf("链表中没有找到该节点。\n");return -1;}void reverse_linkedlist(struct node *pH)
{struct node *p = pH->pNext;    // 这里指向头结点后的第一个节点struct node *pBack = NULL;            // 这里用来保存节点p的下一个节点//如果该链表没有有效节点，或者只有一个有效节点//直接返回，因为这样做逆序无意义if (NULL == p->pNext || p == NULL)return;//当链表有2个或2个以上的有效节点，开始逆序while (NULL != p->pNext)    //判断是否为尾节点，之后进行遍历{pBack = p->pNext;   //先保存该节点的下一个节点，因为变换后地址信息会发生变化//分情况讨论//如果是第一个有效节点就插入到尾部，成为尾节点if (p == pH->pNext)   {p->pNext = NULL;}else //不是第一个有效节点，就是链表之间的节点{p->pNext = pH->pNext;    //让该节点的指向下一个节点变成对应的保存的下一个节点的地址//例如第一个有效节点已经在尾节点了，那么我们之前头结点pH指向的//下一个节点即是节点1，我们之前已经将这个节点2的下一个节点信息//已经保存，那么我们就可以开始逆序，将改节点指向的下一个节点(p->pNext)指向节点1‘//也就是逆序后的尾节点(pH->pNext)。2->1}//头节点指向这个新插入的节点pH->pNext = p;     //头插法，头节点指向这个新插入的节点p = pBack;  //将p指向之前顺序保存下的下一个节点，进行循环}//这种while循环结束后，会在最后少了一个节点//所以我们用头插法解决insert_head(pH, p);   }int main(void)
{struct node *pHeader = create_node(0);insert_head(pHeader, create_node(33));insert_head(pHeader, create_node(22));insert_head(pHeader, create_node(11));bianli(pHeader);//delete_node(pHeader, 33);//bianli(pHeader);reverse_linkedlist(pHeader);printf("------------------逆序后-------------\n");bianli(pHeader);return 0;}

其它方法：
单链表反转/逆序的第三种方法 _ IT技术精华 (taocms.org)
单链表反转/逆序的两种方法 _ IT技术精华 (taocms.org)

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>typedef struct node 
{int data;struct node *pNext;}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error");return NULL;}bzero(p, sizeof(node));p->data = data;p->pNext = NULL;return p;}void insert_tail(node *pH, node *new)
{int cnt = 0;node *p = pH;while (NULL != p->pNext){p = p->pNext;cnt++;}p->pNext = new;pH->data = cnt + 1;}void insert_head(node *pH, node *new)
{new->pNext = pH->pNext;pH->pNext = new;pH->data += 1;}void bianli(node *pH)
{node *p = pH;printf("------------开始遍历----------.\n");while (NULL != p->pNext){p = p->pNext;printf("node data : %d.\n", p->data);}printf("------------遍历结束----------.\n");}int delete_node(node *pH, int data)
{node *p = pH;node *pPrev = NULL;while (NULL != p->pNext){pPrev = p;p = p->pNext;if (p->data == data){if (NULL == p->pNext){pPrev->pNext = NULL;}else{pPrev->pNext = p->pNext;}free(p);return 0;}}printf("链表中没有这个节点.\n");return -1;}void reverse_linkedlist(node *pH)
{node *p = pH->pNext;node *pBack = NULL;if (NULL == p->pNext || NULL == p)return;while (NULL != p->pNext){pBack = p->pNext;if (p == pH->pNext){p->pNext = NULL;}else {p->pNext = pH->pNext;}			pH->pNext = p;p = pBack;}insert_head(pH, p);}int main(void)
{node *pHeader = create_node(0);insert_head(pHeader, create_node(33));insert_head(pHeader, create_node(22));insert_head(pHeader, create_node(11));bianli(pHeader);reverse_linkedlist(pHeader);printf("逆序后：.\n");bianli(pHeader);return 0;
}

三.双链表的实现

1、单链表的局限性

单链表的单向移动性导致我们在操作单链表时，当前节点只能向后移动不能向前移动，因此不自由，不利于解决更复杂的算法。

解决思路：有效数据+2个指针的节点（双链表）
(1)单链表的节点 = 有效数据 + 指针（指针指向后一个节点）
(2)双向链表的节点 = 有效数据 + 2个指针（一个指向后一个节点，另一个指向前一个节点）

2、双链表的封装和实现

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 双链表的节点
typedef struct node
{int data;                         // 有效数据struct node *pPrev;               // 前向指针，指向前一个节点struct node *pNext;               // 后向指针，指向后一个节点}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error.\n");return NULL;}		bzero(p, sizeof(node));p->data = data;p->pPrev = NULL;p->pNext = NULL;     // 默认创建的节点前向后向指针都指向NULLreturn p;
}int main(void)
{node *p = create_node(0);    // 头指针return 0;
}

3.双链表之插入节点

3.1尾插法

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 双链表的节点
typedef struct node
{int data;                         // 有效数据struct node *pPrev;               // 前向指针，指向前一个节点struct node *pNext;               // 后向指针，指向后一个节点}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error.\n");return NULL;}		bzero(p, sizeof(node));p->data = data;p->pPrev = NULL;p->pNext = NULL;     // 默认创建的节点前向后向指针都指向NULLreturn p;
}// 将新节点new插入到链表pH的尾部
//尾插法
void insert_tail(node *pH, node *new)
{node *p = pH;// 第一步先走到链表的尾节点while (NULL != p->pNext){p = p->pNext;    // 第一次循环走过了头节点}// 循环结束后p就指向了原来的最后一个节点// 第二步：将新节点插入到原来的尾节点的后面p->pNext = new;     // 后向指针关联好了。新节点的地址和前节点的nextnew->pPrev = p;     // 前向指针关联好了。新节点的prev和前节点的地址// 前节点的prev和新节点的next指针未变动}int main(void)
{node *pHeader = create_node(0);    // 头指针insert_tail(pHeader, create_node(1));  insert_tail(pHeader, create_node(2)); 	insert_tail(pHeader, create_node(3)); //手工遍历printf("node1 data : %d.\n", pHeader->pNext->data);printf("node2 data : %d.\n", pHeader->pNext->pNext->data);printf("node3 data : %d.\n", pHeader->pNext->pNext->pNext->data);printf("node2 data : %d.\n", pHeader->pNext->pNext->pNext->pPrev->data);return 0;
}

3.2头插法

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 双链表的节点
typedef struct node
{int data;                         // 有效数据struct node *pPrev;               // 前向指针，指向前一个节点struct node *pNext;               // 后向指针，指向后一个节点}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error.\n");return NULL;}		bzero(p, sizeof(node));p->data = data;p->pPrev = NULL;p->pNext = NULL;     // 默认创建的节点前向后向指针都指向NULLreturn p;
}// 将新节点new插入到链表pH的尾部
//尾插法
void insert_tail(node *pH, node *new)
{node *p = pH;// 第一步先走到链表的尾节点while (NULL != p->pNext){p = p->pNext;    // 第一次循环走过了头节点}// 循环结束后p就指向了原来的最后一个节点// 第二步：将新节点插入到原来的尾节点的后面p->pNext = new;     // 后向指针关联好了。新节点的地址和前节点的nextnew->pPrev = p;     // 前向指针关联好了。新节点的prev和前节点的地址// 前节点的prev和新节点的next指针未变动}// 将新节点new前插入链表pH中。
// 算法参照图示进行连接，一共有4个指针需要赋值。注意的是顺序。
void insert_head(node *pH, node *new)
{// 新节点的next指针指向原来的第1个有效节点的地址new->pNext = pH->pNext;// 原来第1个有效节点的prev指针指向新节点的地址if (NULL != pH->pNext){pH->pNext->pPrev = new;}// 头节点的next指针指向新节点地址pH->pNext = new;// 新节点的prev指针指向头节点的地址new->pPrev = pH;}int main(void)
{node *pHeader = create_node(0);    // 头指针/*尾插法insert_tail(pHeader, create_node(1));  insert_tail(pHeader, create_node(2)); 	insert_tail(pHeader, create_node(3)); *///头插法insert_head(pHeader, create_node(3));  insert_head(pHeader, create_node(2)); 	insert_head(pHeader, create_node(1)); //手工遍历printf("node1 data : %d.\n", pHeader->pNext->data);printf("node2 data : %d.\n", pHeader->pNext->pNext->data);printf("node3 data : %d.\n", pHeader->pNext->pNext->pNext->data);printf("node2 data : %d.\n", pHeader->pNext->pNext->pNext->pPrev->data);return 0;
}

注意头插时的链接顺序，先写后面的链接，再写前面的

4.双链表之遍历节点

(1)双链表是单链表的一个父集。双链表中如何完全无视pPrev指针，则双链表就变成了单链表。这就决定了双链表的正向遍历（后向遍历）和单链表是完全相同的。
(2)双链表中因为多了pPrev指针，因此双链表还可以前向遍历（从链表的尾节点向前面依次遍历直到头节点）。但是前向遍历的意义并不大，主要是因为很少有当前当了尾节点需要前向遍历的情况。
(3)总结：双链表是对单链表的一种有成本的扩展，但是这个扩展在有些时候意义不大，在另一些时候意义就比较大。因此在实践用途中要根据业务要求选择适合的链表。

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 双链表的节点
typedef struct node
{int data;                         // 有效数据struct node *pPrev;               // 前向指针，指向前一个节点struct node *pNext;               // 后向指针，指向后一个节点}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error.\n");return NULL;}		bzero(p, sizeof(node));p->data = data;p->pPrev = NULL;p->pNext = NULL;     // 默认创建的节点前向后向指针都指向NULLreturn p;
}// 将新节点new插入到链表pH的尾部
//尾插法
void insert_tail(node *pH, node *new)
{node *p = pH;// 第一步先走到链表的尾节点while (NULL != p->pNext){p = p->pNext;    // 第一次循环走过了头节点}// 循环结束后p就指向了原来的最后一个节点// 第二步：将新节点插入到原来的尾节点的后面p->pNext = new;     // 后向指针关联好了。新节点的地址和前节点的nextnew->pPrev = p;     // 前向指针关联好了。新节点的prev和前节点的地址// 前节点的prev和新节点的next指针未变动}// 将新节点new前插入链表pH中。
// 算法参照图示进行连接，一共有4个指针需要赋值。注意的是顺序。
void insert_head(node *pH, node *new)
{// 新节点的next指针指向原来的第1个有效节点的地址new->pNext = pH->pNext;// 原来第1个有效节点的prev指针指向新节点的地址if (NULL != pH->pNext){pH->pNext->pPrev = new;}// 头节点的next指针指向新节点地址pH->pNext = new;// 新节点的prev指针指向头节点的地址new->pPrev = pH;}// 后向遍历一个双链表
void bianli(node *pH)
{node *p = pH;while(NULL != p->pNext){p = p->pNext;printf("node data : %d.\n", p->data);}}// 前向遍历一个双遍历，参数pTail要指向链表末尾
void qianxiang_bianli(node *pTail)
{node *p = pTail;while (NULL != p->pPrev){printf("node data : %d.\n", p->data);   //注意这里是先打印p = p->pPrev;}}int main(void)
{node *pHeader = create_node(0);    // 头指针/*尾插法insert_tail(pHeader, create_node(1));  insert_tail(pHeader, create_node(2)); 	insert_tail(pHeader, create_node(3)); *///头插法insert_head(pHeader, create_node(3));  insert_head(pHeader, create_node(2)); 	insert_head(pHeader, create_node(1)); //手工遍历//printf("node1 data : %d.\n", pHeader->pNext->data);//printf("node2 data : %d.\n", pHeader->pNext->pNext->data);//printf("node3 data : %d.\n", pHeader->pNext->pNext->pNext->data);//printf("node2 data : %d.\n", pHeader->pNext->pNext->pNext->pPrev->data);//后向遍历一个双链表printf("后向遍历一个双链表：\n");bianli(pHeader);//前向遍历一个双链表printf("前向遍历一个双链表：\n");node *p = pHeader->pNext->pNext->pNext;qianxiang_bianli(p);return 0;
}

5.双链表之删除节点

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>// 双链表的节点
typedef struct node
{int data;                         // 有效数据struct node *pPrev;               // 前向指针，指向前一个节点struct node *pNext;               // 后向指针，指向后一个节点}node;node * create_node(int data)
{node *p = (node *)malloc(sizeof(node));if (NULL == p){printf("malloc error.\n");return NULL;}		bzero(p, sizeof(node));p->data = data;p->pPrev = NULL;p->pNext = NULL;     // 默认创建的节点前向后向指针都指向NULLreturn p;
}// 将新节点new插入到链表pH的尾部
//尾插法
void insert_tail(node *pH, node *new)
{node *p = pH;// 第一步先走到链表的尾节点while (NULL != p->pNext){p = p->pNext;    // 第一次循环走过了头节点}// 循环结束后p就指向了原来的最后一个节点// 第二步：将新节点插入到原来的尾节点的后面p->pNext = new;     // 后向指针关联好了。新节点的地址和前节点的nextnew->pPrev = p;     // 前向指针关联好了。新节点的prev和前节点的地址// 前节点的prev和新节点的next指针未变动}// 将新节点new前插入链表pH中。
// 算法参照图示进行连接，一共有4个指针需要赋值。注意的是顺序。
void insert_head(node *pH, node *new)
{// 新节点的next指针指向原来的第1个有效节点的地址new->pNext = pH->pNext;// 原来第1个有效节点的prev指针指向新节点的地址if (NULL != pH->pNext){pH->pNext->pPrev = new;}// 头节点的next指针指向新节点地址pH->pNext = new;// 新节点的prev指针指向头节点的地址new->pPrev = pH;}// 后向遍历一个双链表
void bianli(node *pH)
{node *p = pH;while(NULL != p->pNext){p = p->pNext;printf("node data : %d.\n", p->data);}}// 前向遍历一个双遍历，参数pTail要指向链表末尾
void qianxiang_bianli(node *pTail)
{node *p = pTail;while (NULL != p->pPrev){printf("node data : %d.\n", p->data);   //注意这里是先打印p = p->pPrev;}}int delete_node(node *pH, int data)
{node *p = pH;if (NULL == p){return -1;}while (NULL != p->pNext)   //遍历查找{p = p->pNext;if (p->data == data){//分两种情况//第一种，删除的节点是尾节点if (NULL == p->pNext){p->pPrev->pNext = NULL;}else{p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;}free(p);}return 0;}printf("在链表中没有找到该节点。\n");return -1;}int main(void)
{node *pHeader = create_node(0);    // 头指针/*尾插法insert_tail(pHeader, create_node(1));  insert_tail(pHeader, create_node(2)); 	insert_tail(pHeader, create_node(3)); *///头插法insert_head(pHeader, create_node(3));  insert_head(pHeader, create_node(2)); 	insert_head(pHeader, create_node(1)); //手工遍历//printf("node1 data : %d.\n", pHeader->pNext->data);//printf("node2 data : %d.\n", pHeader->pNext->pNext->data);//printf("node3 data : %d.\n", pHeader->pNext->pNext->pNext->data);//printf("node2 data : %d.\n", pHeader->pNext->pNext->pNext->pPrev->data);//后向遍历一个双链表printf("后向遍历一个双链表：\n");bianli(pHeader);//前向遍历一个双链表printf("前向遍历一个双链表：\n");node *p = pHeader->pNext->pNext->pNext;qianxiang_bianli(p);printf("删除一个节点后：\n");delete_node(pHeader, 1);bianli(pHeader);return 0;
}

四.linux内核链表

1.前述链表数据区域的局限性

(1)之前定义数据区域时直接int data;
我们认为我们的链表中需要存储的是一个int类型的数。
但是实际上现实编程中链接中的节点不可能这么简单，而是多种多样的。

(2)一般实际项目中的链表，节点中存储的数据其实是一个结构体，这个结构体中包含若干的成员，这些成员加起来构成了我们的节点数据区域。

2.一般性解决思路：数据区封装为一个结构体

(1)因为链表实际解决的问题是多种多样的，所以内部数据区域的结构体构成也是多种多样的。

这样也导致了不同程序当中的链表总体构成是多种多样的。

导致的问题是：我们无法通过一个泛性的、普遍适用的操作函数来访问所有的链表。这就意味着我们设计一个链表就得写一套链表的操作函数（节点创建、插入、删除、遍历······）

(2)实际上深层次分析会发现：
不同的链表虽然这些方法不能通用需要单独写
，但是实际上内部的思路和方法是相同的，只是函数的局部地区有不同。
（实际上链表操作是相同的，而涉及到数据区域的操作就有不同）

(3)鉴于以上2点：我们的理念就是，能不能有一种办法把所有链表中操作方法里共同的部分提取出来用一套标准方法实现，然后把不同的部分留着让具体链表的实现者自己去处理。

3.内核链表的设计思路

(1)内核链表中自己实现了一个纯链表（纯链表就是没有数据区域，只有前后向指针）的封装，以及纯链表的各种操作函数（节点创建、插入、删除、遍历······）。这个纯链表本身自己没有任何用处，它的用法是给我们具体链表作为核心来调用。

4.list.h文件简介

(1)内核中核心纯链表的实现在include/linux/list.h文件中
(2)list.h中就是一个纯链表的完整封装，包含节点定义和各种链表操作方法。

5.基本使用介绍

(1)问题：内核链表只有纯链表，没有数据区域，怎么使用？
(2)设计的使用方法是将内核链表作为将来整个数据结构的结构体的一个成员内嵌进去。

内核链表默认是双链表

内嵌举例：

#include <linux/list.h>struct driver_info
{int data;
};// driver结构体用来管理内核中的驱动
struct driver
{char name[20];				// 驱动名称int id;						// 驱动id编号struct driver_info info;	// 驱动信息struct list_head head;		// 内嵌的内核链表成员
};// 分析driver结构体，
//可知：前三个成员都是数据区域成员（就是我们之前简化为int data的东西），
//第4个成员是一个struct list_head类型的变量，这就是一个纯链表。// 本来driver结构体是没有链表的，也无法用链表来管理。但是我们driver内嵌的head成员本身就是一个纯链表，所以driver通过head成员给自己扩展了链表的功能。// driver通过内嵌的方式扩展链表成员，本身不只是有了一个链表成员，关键是可以通过利用list_head本身事先实现的链表的各种操作方法来操作head。// 最终效果：我们可以通过遍历head来实现driver的遍历；遍历head的函数在list.h中已经事先写好了，所以我们内核中去遍历driver时就不用重复去写了。// 通过操作head来操作driver，实质上就是通过操作结构体的某个成员变量来操作整个结构体变量。这里面要借助container_of宏struct driver2
{char name[20];				// 驱动名称int id;						// 驱动id编号struct driver_info info;	// 驱动信息//struct list_head head;		// 内嵌的内核链表成员struct driver *prev;struct driver *next;
};