C语言数据结构编程笔记：链表

前言本文面向编程零基础小白用生活化案例通俗讲解C语言中指针、链表核心概念、组成要素与完整实操流程手把手演示基础动态链表的完整可运行代码示例。一、核心概念指针的是可以储存某个 内存地址 的变量。一般来说指针变量并不储存某个有效数据而是指向某个存了有效数据的变量所在的地址可以指是向一个变量的内存地址也可以是指向一个结构体的内存地址甚至可以是存了另一个指针的的内存地址。节点本质上是一个结构体一个包含了数据与指针的结构体。一般来说链表中的每一个节点都会有一个数据并有着至少一个指针可能是一个指向下一个节点的指针也可以是指向下一节点与指向上一节点两个指针。//节点存数据、下一节点指针、上一节点指针typedefstructNode{void*data;//存指针可以指向任意类型structNode*next;//下一个节点structNode*prev;//上一个节点}Node;内存分配在C语言中可以通过头文件stdlib.h中的 malloc 函数来申请分配一些内存然后将这些内存的地址赋值给一个指针。//为新节点初始化的函数Node*nodeCreate(void*data){//先分一块内存给 node 指针Node*node(Node*)malloc(sizeof(Node));//为节点内的数据、指针初始化node-datadata;node-nextNULL;node-prevNULL;//最后将 node 的地址返回returnnode;}随后通过调用该方法为一个新节点赋值Node*newNodenodeCreate(data);这一步相是在把方法返回的值赋值给一个节点变量于是就可以通过这个变量操作那块被分配的内存了。链表本质上就是将分散在内存堆中的一些数据节点通过指针串联起来的一种数据结构。数组是一段连续的内存通过对指针的增减就可以访问到对应的位置链表则是许多散落在堆中的内存直接对它们的指针进行增减操作并不能访问到对应节点因此每个节点中都至少存了一个其它节点的地址。数组就像你访问你的邻居出门下一间房就到了但链表就像是你的远房亲戚你出门敲下一间屋的房门是找不到他的。但只要你有他家的地址你就可以借着地址访问到他。每个节点中都有指向其它节点的指针通过指针让 A 节点指向 B 节点再通过 B 节点指向 C 节点……将所有的节点像链条或是像一串珠子一样串起来就是链表的结构。二、链表的组成要素节点本质上是储存在内存堆中打包了数据和指针的结构体。节点之间通过指针互相连接的结构就被称为链表。指针指针是一种变量里面存了指向内存中某个地方的“地址”。每个节点中至少存有一个指向其他节点的内存所在地址的指针通过访问指针变量就可以访问到链表中其它节点的内存进行获取、添加、删改数据等操作。头尾指针创建链表时首个节点为头结点并把头结点的指针保存在结构体 LinkList 中。需要访问链表中的某个节点时通过访问 LinkList 中的头指针变量找到头结点再访问头结点的下一节点指针找到第二节点再通过节点中的下一节点指针找到第三节点如此循环直到遍历到指定位置就实现了链表的遍历查找。计数器通过 LinkList 结构体中的计数变量控制遍历查找的循环次数。因为链表并不像数组拥有下标所以需要额外用一个变量来控制查找、删改、添加等操作的次数或是否超出链表长度。三、完整实操案例#includestdbool.h#includestdio.h#includestdlib.h//节点存数据、下一节点指针、上一节点指针typedefstructNode{void*data;//存指针可以指向任意类型structNode*next;//下一个节点structNode*prev;//上一个节点}Node;//链表size 是元素个数first 是头last 是尾typedefstructLinkList{intsize;Node*first;Node*last;}LinkList;//创建新链表LinkList*linkListCreate(){LinkList*list(LinkList*)malloc(sizeof(LinkList));list-firstNULL;list-lastNULL;list-size0;returnlist;}//创建新节点Node*nodeCreate(void*data){Node*node(Node*)malloc(sizeof(Node));node-datadata;node-nextNULL;node-prevNULL;returnnode;}//销毁链表//freeFn 用来释放每个节点的 data传 NULL 表示不释放voidlinkListDestroy(LinkList*list,void(*freeFn)(void*)){//空链表直接释放结构体if(list-size0){free(list);return;}Node*currlist-first;for(inti0;ilist-size;i){Node*nextcurr-next;//先留后路否则 free 之后就找不到了if(freeFn!NULL){freeFn(curr-data);}free(curr);currnext;}free(list);}//末尾添加voidlinkListAdd(LinkList*list,void*data){Node*newNodenodeCreate(data);//空链表新节点同时成为头和尾if(list-firstNULL){list-firstnewNode;list-lastnewNode;newNode-nextnewNode;newNode-prevnewNode;}//非空链表插到 last 和 first 之间else{list-last-nextnewNode;newNode-prevlist-last;newNode-nextlist-first;list-first-prevnewNode;list-lastnewNode;}list-size;}//获取指定位置数据void*linkListGet(LinkList*list,intindex){//下标不合法返回 NULLif(index0||indexlist-size){returnNULL;}Node*curr;//下标在前半段从头往后走if(indexlist-size/2){currlist-first;for(inti0;iindex;i){currcurr-next;}}//下标在后半段从尾往前走else{currlist-last;for(intilist-size-1;iindex;i--){currcurr-prev;}}returncurr-data;}//插入添加voidlinkListAddAt(LinkList*list,intindex,void*data){//下标不合法直接返回if(index0||indexlist-size){return;}//空链表或者插在末尾直接调用已经写好的末尾添加函数if(list-size0||list-sizeindex){linkListAdd(list,data);return;}//插在开头if(index0){Node*newNodenodeCreate(data);newNode-nextlist-first;newNode-prevlist-last;list-first-prevnewNode;list-last-nextnewNode;list-firstnewNode;list-size;return;}//插在中间先找到 index 位置的节点Node*newNodenodeCreate(data);Node*curr;if(indexlist-size/2){currlist-first;for(inti0;iindex;i){currcurr-next;}}else{currlist-last;for(intilist-size-1;iindex;i--){currcurr-prev;}}//把新节点插到 curr 前面Node*prevcurr-prev;newNode-prevprev;newNode-nextcurr;curr-prevnewNode;prev-nextnewNode;list-size;}//删除指定位置返回被删的指针void*linkListRemoveAt(LinkList*list,intindex){//下标不合法返回 NULLif(index0||indexlist-size){returnNULL;}//先找到 index 位置的节点Node*curr;if(indexlist-size/2){currlist-first;for(inti0;iindex;i){currcurr-next;}}else{currlist-last;for(intilist-size-1;iindex;i--){currcurr-prev;}}//只有一个节点的话直接清空就好if(list-size1){list-firstNULL;list-lastNULL;}//多个节点把 curr 从链表中删除else{curr-next-prevcurr-prev;curr-prev-nextcurr-next;//删的是头、尾更新 first、lastif(currlist-first){list-firstcurr-next;}if(currlist-last){list-lastcurr-prev;}}//先存 data再释放节点void*datacurr-data;free(curr);list-size--;returndata;}//删除首个匹配数据//泛型版只能比指针地址不能比内容boollinkListRemove(LinkList*list,void*data,void(*freeFn)(void*)){Node*currlist-first;for(inti0;ilist-size;i){if(curr-datadata){freeFn(curr-data);//先释放元素linkListRemoveAt(list,i);//再删节点returntrue;}currcurr-next;}returnfalse;}//链表翻转boollinkListReversal(LinkList*list){if(list-size0){returnfalse;}//每个节点的 next 和 prev 互换Node*currlist-first;for(inti0;ilist-size;i){Node*tempcurr-next;//留后路curr-nextcurr-prev;curr-prevtemp;currtemp;}//最后交换 first 和 lastNode*templist-first;list-firstlist-last;list-lasttemp;returntrue;}//获取链表长度intlinkListSize(LinkList*list){returnlist-size;}四、个人收获总结以前用 Java 仿照官方库写链表时一直搞不懂那些指针变量与一般变量的区别对指针的理解其实只是一知半解好像懂了但又没有完全搞懂。因为 Java 已经把指针以及调用方法时的 this 参数等都帮你处理好了使用起来比C语言方便许多但不如C语言那么接近底层它把许多底层都打包好了。在学习C语言时我真正接触了“指针变量”以前在 Java 中一知半解的概念如今看来也十分清晰。这是我写C语言链表的最大的收获。拓展阅读C语言数据结构笔记指针、动态数组Java数据结构基础笔记动态数组、链表