1. 链表结构介绍
在前面章节已经学习了数组的使用，数组的空间是连续空间，数组的大小恒定的，在很多动态数据存储的应用场景下，使用不方便；而这篇文章介绍的链表结构，支持动态增加节点，释放节点，比较适合存储动态数据的应用场景，而且链表的空间是存储在堆上面的，可以动态分配，释放。从效率上来讲，数组的空间是连续的，查询、读取数据数组占优势；链表的优势在于节点可以动态增加、动态删除，删除支持任意位置的节点删除。
特点:
数组的空间是连续的，可以直接通过[]下标访问。
链表的节点是不连续的，需要通过每个节点的指针，来找到上一个节点或者下一个节点的地址。
链表的每个节点就是一个结构体变量，节点里有一个或者两个指针，可以保存上一个节点和下一个节点的地址，方便遍历链表，删除、插入节点时定位位置。
2. 案例: 单向链表的创建与使用
下面例子采用函数封装的形式编写，每个功能都使用子函数实现。
实现的功能如下:
初始化链表头 插入节点的函数(链表任意位置插入，链表尾插入) 删除节点的函数（链表任意位置删除、链表尾删除） 遍历链表，输出链表里的所有信息 复制#include #include //定义链表节点的结构体 struct app { int a; struct app *next; //能保存结构体的地址 }; struct app *list_head=NULL; //链表的头指针 void list_print(struct app *head); struct app *list_HeadInit(struct app *head); void list_add(int a,struct app *head); void list_del(int a,struct app *head); int main() { //1. 初始化链表头 list_head=list_HeadInit(list_head); //2. 在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add(13,list_head); //3. 删除节点 list_del(11,list_head); //4. 输出链接节点里的数据 list_print(list_head); return 0; } /* 函数功能: 初始化链表头–给链表头申请空间 */ struct app *list_HeadInit(struct app *head) { if(head==NULL) //没有空间 { //1. 申请链表头空间 head=malloc(sizeof(struct app)); //2. 初始化链表头 head->next=NULL; } return head; } /* 函数功能: 在链表尾插入数据 int a 插入的数据值 struct app *head 链表头 */ void list_add(int a,struct app *head) { struct app *new_p=NULL; struct app *next_p=head; struct app *tmp_p; //保存上一个节点的地址 //1.申请空间并给空间成员赋值 new_p=malloc(sizeof(struct app)); new_p->a=a; new_p->next=NULL; //2. 找到链表尾 while(next_p!=NULL) { tmp_p=next_p; next_p=next_p->next; //指针指向下一个节点 } //3. 插入新节点–链接结尾 tmp_p->next=new_p; } /* 函数功能: 遍历输出链接里的所有数据 */ void list_print(struct app *head) { struct app *next_p=head; int cnt=0; if(head!=NULL) { while(next_p->next!=NULL) { next_p=next_p->next; printf(“链表节点[%d]:a=%d\n”,cnt++,next_p->a); } } } /* 函数功能:链表的删除－－按照指定的数据删除 */ void list_del(int a,struct app *head) { struct app *next_p=head; struct app *tmp_p; //保存上一个节点的地址 //1. 找到要删除的链表 if(next_p!=NULL) { while(next_p->next!=NULL) { tmp_p=next_p; //保存上一个节点的地址 next_p=next_p->next; //获取有效节点的地址 if(next_p->a==a) //判断是否需要删除 { tmp_p->next=next_p->next; free(next_p); } } } } 复制代码3. 案例: 单向循环链表
代码直接在上面的案例2例子上改造的，区别就是尾结点指向了头结点而不是NULL。
复制#include #include //定义链表节点的结构体 struct app { int a; struct app *next; //能保存结构体的地址 }; struct app *list_head=NULL; //链表的头指针 void list_print(struct app *head); struct app *list_HeadInit(struct app *head); void list_add(int a,struct app *head); void list_del(int a,struct app *head); int main() { //1. 初始化链表头 list_head=list_HeadInit(list_head); //2. 在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add(13,list_head); //3. 删除节点 list_del(11,list_head); //4. 输出链接节点里的数据 list_print(list_head); return 0; } /* 函数功能: 初始化链表头–给链表头申请空间 */ struct app *list_HeadInit(struct app *head) { if(head==NULL) //没有空间 { //1. 申请链表头空间 head=malloc(sizeof(struct app)); //2. 初始化链表头 head->next=head; } return head; } /* 函数功能: 在链表尾插入数据 int a 插入的数据值 struct app *head 链表头 */ void list_add(int a,struct app *head) { struct app *new_p=NULL; struct app *next_p=head; struct app *tmp_p; //保存上一个节点的地址 //1.申请空间并给空间成员赋值 new_p=malloc(sizeof(struct app)); new_p->a=a; new_p->next=head; //2. 找到链表尾 if(head!=NULL) { if(next_p->next==head) //表示第一次插入节点 { next_p->next=new_p; //head —-<节点1>—head } else { while(next_p->next!=head) { next_p=next_p->next; //指针指向下一个节点 } //3. 插入新节点–链接结尾 next_p->next=new_p; } } } /* 函数功能: 遍历输出链接里的所有数据 */ void list_print(struct app *head) { struct app *next_p=head; int cnt=0; if(head!=NULL) { printf(“头地址: %#x\n”,next_p); //头 printf(“第一个节点地址:%#x\n”,next_p->next); //下一个节点地址 printf(“第二个节点地址:%#x\n”,next_p->next->next); //下下一个节点地址 printf(“第三个节点地址:%#x\n”,next_p->next->next->next); printf(“第四个节点地址:%#x\n”,next_p->next->next->next->next); while(next_p->next!=head) { next_p=next_p->next; printf(“链表节点[%d]:a=%d\n”,cnt++,next_p->a); } } } /* 函数功能:链表的删除－－按照指定的数据删除 */ void list_del(int a,struct app *head) { struct app *next_p=head; struct app *tmp_p; //保存上一个节点的地址 //1. 找到要删除的链表 if(next_p!=NULL) { while(next_p->next!=head) { tmp_p=next_p; //保存上一个节点的地址 next_p=next_p->next; //获取有效节点的地址 if(next_p->a==a) //判断是否需要删除 { tmp_p->next=next_p->next; free(next_p); } } } } 复制代码4. 案例: 创建双向链表循环，实现插入、删除、遍历
双向链表在每个节点里新增加了一个指针，用于保存上一个节点的地址，现在的节点里一个用两个指针，一个保存上一个节点的地址，一个保存下一个节点的地址。
复制#include #include //定义链表节点的结构体 struct app { int a; struct app *next; //下一个节点地址 struct app *prev; //前一个节点地址 }; //全局变量声明区域 struct app *list_head=NULL; //链表的头指针 //函数声明 struct app *List_HeadInit(struct app *head); void list_add(int a,struct app *head); void list_print(struct app *head); void list_del(int a,struct app *head); int main() { /*1. 初始化链表*/ list_head=List_HeadInit(list_head); /*2. 添加链表节点*/ list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add(13,list_head); list_add(14,list_head); /*3.删除指定节点*/ list_del(12,list_head); /*4. 遍历输出所有节点信息*/ list_print(list_head); return 0; } /* 函数功能: 创建链表头 */ struct app *List_HeadInit(struct app *head) { if(head==NULL) { head=malloc(sizeof(struct app)); head->a=0; head->next=head; head->prev=head; } return head; } /* 函数功能: 添加数据-链表尾添加数据 */ void list_add(int a,struct app *head) { struct app *next_p=head; struct app *new_p=NULL; /*1. 申请新的节点*/ new_p=malloc(sizeof(struct app)); new_p->a=a; new_p->next=head; /*2. 完成新节点的添加*/ //遍历链表 while(next_p->next!=head) { next_p=next_p->next; } //添加新节点 new_p->prev=next_p; next_p->next=new_p; //修改链表头的上一个节点地址 head->prev=new_p; } /* 函数功能:输出链表里的所有数据 */ void list_print(struct app *head) { struct app *next_p=head; int cnt=0; /*1. 顺向遍历*/ while(next_p->next!=head) { next_p=next_p->next; printf(“节点[%d]:%d\n”,cnt++,next_p->a); } /*2. 反向遍历*/ next_p=head; while(next_p->prev!=head) { next_p=next_p->prev; printf(“节点[%d]:%d\n”,cnt–,next_p->a); } } /* 函数功能:删除链表里的指定节点 */ void list_del(int a,struct app *head) { struct app *next_p=head; struct app *tmp_p=NULL; while(next_p->next!=head) { tmp_p=next_p; //保存上一个节点的地址 next_p=next_p->next; if(next_p->a==a) { //方式1 tmp_p->next=tmp_p->next->next; tmp_p->next->prev=tmp_p; //方式2 //tmp_p->next=next_p->next; //next_p->next->prev=tmp_p; //printf(“%d\n”,tmp_p->a); //11 //printf(“%d\n”,tmp_p->next->a); //13 //printf(“%d\n”,next_p->next->prev->a); //11 free(next_p); break; } } } 审核编辑 黄昊宇
