Doubletful的博客数据结构专栏路漫漫其修远兮吾将上下而求索文章目录前言一、概念线性表概念线性表的存储结构顺序存储结构链式存储结构链表概念二、代码实现准备头文件内容总览另一种节点别名结构定义创建新节点添加尾插数据添加头插数据删除尾部数据删除头部数据添加指定位置前插入添加指定位置后插入删除指定位置删除指定位置后查找数据销毁链表一份测试代码三、总结优缺点总结与其他链表对比四、练习前言——链表是程序员的“基本功”而单向不带头不循环链表则是链表的“Hello World”。文章从线性表的概念出发带你彻底理解单向不循环链表的底层逻辑手写实现并分析其优缺点与应用场景。本博客将使用C语言实现基础数据结构——单链表主要内容包括1.使用头文件声明、源文件定义的形式实现2.从线性表到链表的概念实现原理与操作接口的详解3.提供完整的代码示例和实际应用场景分析一、概念线性表概念定义n 个数据元素的有限序列元素之间具有线性关系前驱、后继特点同一性、有穷性、有序性常见例子数组、链表、栈、队列解释表头元素没有前驱其余的任意元素都有唯⼀的前驱元素表尾元素没有后继其余的任意元素都有唯⼀的后继元素。特点为表中的元素类型一致元素个数有限且元素间的相对位置有意义如同线性统计图。线性表的存储结构顺序存储结构特点物理地址连续随机访问的时间复杂度为O(1)但插入与删除需要移动大量元素其空间在程序运行前静态分配(给定唯一值)或动态扩容(在程序运行时才能确定具体大小)。链式存储结构特点物理地址不连续逻辑上通过每一个由结构体定义的节点结构中的 next 指针链接随机访问的最坏时间复杂度为O(n)其中 n 为链的节点个数。插入与删除只需修改指针指向无需移动元素容量无上限。顺序存储结构与链式存储结构的对比示例图链表概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序通过链表中的指针链接实现。链表能分为带头和不带头单向和双向循环和不循环结合起来共六个种类其中最常用的有两种不带头单向不循环链表(各种层面的重点考察)和带头双向循环链表下图是链表种类的对比示例图而我们将要实现的是不带头单向不循环链表(以下简称单链表)单链表的每个结构体单独作为节点所有节点链接后为完整链表而顺序表用一个结构体存储主体数组及属性容量和大小。二、代码实现准备前置知识assert()函数介绍C语言标准库中的调试宏用于在程序运行时检查条件是否成立。若条件为假0则输出错误信息文件、行号、表达式并调用 abort()终止程序若条件为真非0则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等。perror()函数介绍C 语言标准库函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”常用于系统调用或库函数失败后快速定位错误原因。exit()函数介绍C 语言标准库函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统0or EXIT_SUCCESS表示成功-1or EXIT_FAILURE表示失败。头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.htypedefintSNDataType;#定义单向链表的节点结构typedefstructSListNode{SNDataType data;#存储值structSListNode*next;#指向下一个节点的指针}SN;#添加尾插数据voidSNPushBack(SN**pphead,SNDataType x);#添加头插数据voidSNPushFront(SN**pphead,SNDataType x);#删除尾部数据voidSNPopBack(SN**pphead);#删除头部数据voidSNPopFront(SN**pphead);#添加指定位置前插入voidSNInsert(SN**pphead,SN*pos,SNDataType x);#添加指定位置后插入voidSNInsertAfter(SN*pos,SNDataType x);#删除指定位置voidSNErase(SN**pphead,SN*pos);#删除指定位置后voidSNEraseAfter(SN*pos);#销毁链表voidSNDestroy(SN**pphead);与顺序表的相同之处使用 typedef 为表内存储的数据类型起别名方便类型替换。有增删和销毁操作不需要初始化操作指定位置插入和删除相比于顺序表多做出了两个分类操作针对于依赖指定位置进行的细致操作。※由于不使用初始化操作而且每次的增加和删除操作都有可能改变链表头指针 head 指向的节点因此在涉及到增加和删除操作的函数中传入的指针应该为指向头指针的指针应使用二级指针修改一级指针的指向否则因为形参是实参的一份临时拷贝传入一级指针相当于拷贝了一份头指针函数内针对于拷贝头指针的任何操作都不会影响到原头指针的指向。另一种节点别名结构定义某些代码在节点结构定义时采用了如下方式typedefstructSListNode{SNDataType data;structSListNode*next;}SN,*pSN;#同时为节点指针也创建别名定义后pSN 这种写法等价于 SN*以下是这两种命名别名的代码写法typedef struct SListNode SN;typedef struct SListNode* pSN;这样就能直观的看到定义时分别给什么起了什么别名学校教科书上喜欢采用这种定义形式但在接下来中我们将采用SN*这种方式创建节点指针。创建新节点SN*SNBuyNode(SNDataType x){SN*newnode(SN*)malloc(sizeof(SN));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}添加元素都需要创建节点定义一个专门创建新节点的函数避免重复造轮子。使用 malloc 分配空间并判断操作是否成功在确认无误后将数据 x 存入节点的 data 属性由于不知道链接的位置因此将 next 初始化为 NULL。最后返回创建好的新节点由于该节点的空间是动态开辟的因此不会因为函数栈帧在函数执行完成后而被一同销毁。添加尾插数据voidSNPushBack(SN**pphead,SNDataType x){assert(pphead);SN*nodeSNBuyNode(x);#尾插if(*ppheadNULL)#链表为空时{*ppheadnode;return;}SN*prev*pphead;#链表不为空时while(prev-next){prevprev-next;}prev-nextnode;}⇒传入链表与要添加的元素断言传入指针不为 NULL创建新节点尾插时有两种情况如果传入指针指向为空代表链表为空此时利用二级指针让头节点指向新创建的节点 node如果不为空即为正常的尾插操作利用循环从头结点开始遍历找尾。新创建一个指向头结点的指针用于遍历如果直接使用二级指针指向的头指针遍历会修改指针指向导致表头丢失。循环的结束条件为当前的指针指向节点的 next 为 NULL此时当前指针指向的节点为尾节点修改尾节点的 next 为创建的新节点完成尾插 。添加头插数据voidSNPushFront(SN**pphead,SNDataType x){assert(pphead);SN*nodeSNBuyNode(x);#头插 node-next*pphead;*ppheadnode;}⇒传入链表与要添加的元素断言传入指针不为 NULL创建新节点。直接先将新创建节点的 next 指向当前的头节点防止断链后将头指针指向的节点修改为新创建的节点。如果当前头指针指向 NULL (链表为空)当前的操作就为添加新节点并让头指针指向新节点无需额外判断为空情况。删除尾部数据voidSNPopBack(SN**pphead){assert(pphead*pphead);#尾删if((*pphead)-nextNULL)#链表只有一个节点时{free(*pphead);*ppheadNULL;return;}SN*prev*pphead;#链表有多个节点时while(prev-next-next){prevprev-next;}free(prev-next);prev-nextNULL;}⇒传入链表断言传入指针不为 NULL 且链表不为空。尾删时有两种情况当链表只有一个节点时释放链表后应该将头指针指向置空避免因空间释放后造成的野指针问题。如果链表不只有一个元素即为正常的尾删操作需遍历到尾节点的前一个结点后通过其 next 指向删除尾节点循环的结束条件为当前的指针指向节点的 next 的 next 为 NULL此时当前指针指向的节点为尾节点的前一个结点释放尾节点并将尾节点的前一个结点的 next 置空完成尾删。删除头部数据voidSNPopFront(SN**pphead){assert(pphead*pphead);#头删 SN*prev*pphead;*pphead(*pphead)-next;free(prev);}⇒传入链表断言传入指针不为 NULL 且链表不为空。创建一个临时指针指向当前的头节点用于删除操作让指向头节点的指针 head 指向链表的下一个节点此为新的头节点最后销毁原头节点完成头删。注意不能先删除当前的头节点后再让 head 指向新的头节点访问被销毁(还给操作系统)的空间会造成野指针访问问题。添加指定位置前插入voidSNInsert(SN**pphead,SN*pos,SNDataType x){assert(pphead*ppheadpos);#指定位置前插入if(*ppheadpos)#pos在头节点时{SNPushFront(pphead,x);return;}SN*nodeSNBuyNode(x);#pos在头节点后时 SN*prev*pphead;while(prev-next!pos){prevprev-next;}node-nextprev-next;prev-nextnode;}⇒传入链表、指定位置(结点)与要添加的元素断言传入指针不为 NULL、pos不为空且链表不为空创建新节点。指定位置前插入有两种情况当 pos 的位置为头结点时在其位置插入相当于头插操作为避免代码重复能直接将头节点与要添加的元素传入头插函数这种在函数内调用其他函数的情况称被调用的函数为回调函数。第二种情况为正常的指定位置前插入操作在 pos 位置前插入循环的结束条件为当前用于遍历的指针指向 pos 的前一个结点。循环结束后先让新结点的 next 指向 pos 位置防止断链后修改 pos 的前一个节点的 next 指向新结点完成指定位置前插入操作。添加指定位置后插入voidSNInsertAfter(SN*pos,SNDataType x){assert(pos);#指定位置后插入 SN*nodeSNBuyNode(x);node-nextpos-next;pos-nextnode;}⇒传入指定位置与要添加的元素断言传入指针不为 NULL创建新节点先将新节点的 next 指向 pos 的下一个节点防止断链后将 pos 的 next 指向新节点完成指定位置后插入。当链表只有一个节点时 pos 的 next 指向 NULL无空指针访问问题因此无需特判。删除指定位置voidSNErase(SN**pphead,SN*pos){assert(pphead*ppheadpos);#指定位置删除if((*pphead)pos)#pos在头节点时{SNPopFront(pphead);return;}SN*prev*pphead;#pos在头节点后时while(prev-next!pos){prevprev-next;}prev-nextpos-next;free(pos);}⇒传入链表与指定位置断言传入指针不为空、pos不为空且链表不为空指定位置删除有两种情况当 pos 指向头节点时相当于头删操作直接将 pphead 传入头删函数。情况二为常规的指定位置删除操作需遍历链表找到 pos 的前一个结点当链表中的某个节点的 next 等于 pos 节点时结束循环遍历让 pos 的前一个结点的 next 指针指向越过删除位置 pos 指向 pos 的 next 最后销毁指定节点完成指定位置删除。删除指定位置后voidSNEraseAfter(SN*pos){assert(pospos-next);#指定位置后删除 SN*prevpos-next;pos-nextprev-next;free(prev);}⇒传入指定位置结点断言传入指针和指定位置的 next 不为 NULL为什么要判断指定位置的 next 不为空答指定位置往往不在链表末尾要删除指定位置后的节点一定需利用指定位置后节点的 next 找到链表的后半部分并链接到指定位置的 next然后销毁指定位置的后一个节点防止断链。使用临时指针记录删除节点待上述操作完成后完成指定位置后删除。查找数据SN*SNFind(SN*phead,SNDataType x){assert(phead);#查找数据while(phead){if(phead-datax)returnphead;pheadphead-next;}returnNULL;}⇒传入链表与要查找的元素断言传入指针不为 NULL。遍历链表查找元素找到返回元素对应的节点否则返回 NULL因为查找操作不可能修改链表的头节点因此传入一级指针利用一级指针遍历链表。销毁链表voidSNDestroy(SN**pphead){assert(pphead*pphead);SN*next*pphead;while(next){SN*ruinnext;nextnext-next;free(ruin);}*ppheadNULL;}⇒传入链表断言传入指针不为 NULL 且链表不为空。完全销毁整个链表需要动态的删除每一个链表中的节点。遍历链表存储当前节点让指向当前节点的指针移动到下一个节点销毁当前节点直到当前节点为 NULL 后修改头指针指向为 NULL完成销毁链表。一份测试代码voidTest_SListNode(){SN*plistNULL;#尾插测试SNPushBack(plist,4);SNPushBack(plist,5);SNPushBack(plist,6);#头插测试SNPushFront(plist,3);SNPushFront(plist,2);SNPushFront(plist,1);#尾删测试SNPopBack(plist);SNPopBack(plist);#头删测试SNPopFront(plist);SNPopFront(plist);#查找测试 SN*nodeSNFind(plist,3);if(node!NULL){printf(%d\n,node-data);}#指定位置前插入测试SNInsert(plist,node,2);#指定位置后插入测试SNInsertAfter(plist,3);#指定位置删除测试SNErase(plist,node);nodeNULL;#指定位置后删除测试SNEraseAfter(plist);#销毁测试SNDestroy(plist);}三、总结优缺点总结优点缺点动态扩容没有容量上限不支持随机访问无法通过下标 O(1) 获取元素插入删除修改指针不移动数据每个元素多消耗指针内存内存利用率高按需分配缓存不友好结点在内存中离散分布方便实现栈、队列、哈希表拉链等代码比数组稍复杂容易指针错误缓存不友好指链表的缓存命中率低解释如下➤当数据较小时系统以寄存器作为媒介利用 CPU 对数据进行操作因为内存与 CPU 不同频如果直接访问内存操作数据效率会变低因此先将内存中的数据加载到寄存器中完成操作后再放回内存。➤当数据较大时会先将数据从内存加载到缓存后利用 CPU 操作如果当时数据在缓存中称为缓存命中直接访问如果不在缓存中称为不命中要先把数据从内存加载到缓存后再访问。➤实际加载时会一次性加载一定量的、连续的数据而链表的每个节点在物理存储上不连续因此缓存命中率一定比在物理存储上连续的顺序表要低存储器结构层次结构示例图与其他链表对比类型优点缺点典型场景单向不循环链表简单内存小无法从任意结点反向遍历栈、队列、拉链法单向循环链表从任意结点可遍历全表小心死循环约瑟夫环、轮询调度双向链表可反向遍历删除尾结点 O(1)多一个前驱指针内存翻倍LRU 缓存、编辑器撤销双向循环链表灵活插入删除最强复杂易出错Linux 内核链表小结单向不循环链表是内存最紧凑、代码最简单的链表适合资源受限或只需单向遍历的场景。四、练习推荐以下LeetCode题目203. 移除链表元素 链接link.21. 合并两个有序链表 链接link.206. 反转链表 链接link.876. 链表的中间结点 链接link.234. 回文链表 链接link.经典推荐题目160. 相交链表 链接link.138. 随机链表的复制 链接link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定何时创作双向链表专题博客