单链表专题（完整代码版）

单链表专题完整代码版文章目录单链表专题完整代码版一、链表的概念及结构1.1 什么是链表1.2 链表的节点结构二、单链表的完整实现2.1 节点定义与函数声明2.2 打印链表2.3 尾插在链表末尾插入节点2.4 头插在链表头部插入节点2.5 尾删删除最后一个节点2.6 头删删除第一个节点2.7 查找节点返回第一个值为x的节点指针2.8 在指定位置之前插入2.9 在指定位置之后插入2.10 删除指定节点2.11 删除指定节点之后的节点2.12 销毁整个链表三、测试代码示例四、链表的分类4.1 单向 or 双向4.2 带头 or 不带头4.3 循环 or 不循环4.4 实际中最常用的两种结构五、总结一、链表的概念及结构1.1 什么是链表链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。;// 打印链表voidSLTPushBack(SLTNode**pphead,SLTDataType x);// 尾插voidSLTPushFront(SLTNode**pphead,SLTDataType x);// 头插voidSLTPopBack(SLTNode**pphead);// 尾删voidSLTPopFront(SLTNode**pphead);// 头删SLTNode*SLTFind(SLTNode*phead,SLTDataType x);// 查找voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);// 在pos之前插入voidSLTInsertAfter(SLTNode*pos,SLTDataType x);// 在pos之后插入voidSLTErase(SLTNode**pphead,SLTNode*pos);// 删除pos节点voidSLTEraseAfter(SLTNode*pos);// 删除pos之后的节点voidSLTDestroy(SLTNode**pphead);// 销毁链表为什么很多函数需要二级指针因为我们要修改头指针本身例如头插、头删、销毁等操作会改变链表的头节点地址必须传二级指针才能改变实参。2.2 打印链表voidSLTPrint(SLTNode*phead){SLTNode*curphead;while(cur!NULL){printf(%d - ,cur-data);curcur-next;}printf(NULL\n);}2.3 尾插在链表末尾插入节点voidSLTPushBack(SLTNode**pphead,SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextNULL;// 空链表特殊处理if(*ppheadNULL){*ppheadnewnode;return;}// 找到尾节点SLTNode*tail*pphead;while(tail-next!NULL){tailtail-next;}tail-nextnewnode;}2.4 头插在链表头部插入节点voidSLTPushFront(SLTNode**pphead,SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-next*pphead;*ppheadnewnode;}2.5 尾删删除最后一个节点voidSLTPopBack(SLTNode**pphead){// 空链表if(*ppheadNULL)return;// 只有一个节点if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;return;}// 多个节点SLTNode*prevNULL;SLTNode*tail*pphead;while(tail-next!NULL){prevtail;tailtail-next;}prev-nextNULL;free(tail);}2.6 头删删除第一个节点voidSLTPopFront(SLTNode**pphead){if(*ppheadNULL)return;SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}2.7 查找节点返回第一个值为x的节点指针SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*curphead;while(cur){if(cur-datax)returncur;curcur-next;}returnNULL;}2.8 在指定位置之前插入voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){// 如果pos是头节点相当于头插if(*ppheadpos){SLTPushFront(pphead,x);return;}// 找到pos的前一个节点SLTNode*prev*pphead;while(prevprev-next!pos){prevprev-next;}if(prevNULL)return;// pos不在链表中SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextpos;prev-nextnewnode;}2.9 在指定位置之后插入voidSLTInsertAfter(SLTNode*pos,SLTDataType x){if(posNULL)return;SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);return;}newnode-datax;newnode-nextpos-next;pos-nextnewnode;}2.10 删除指定节点voidSLTErase(SLTNode**pphead,SLTNode*pos){if(*ppheadNULL||posNULL)return;// 删除头节点if(*ppheadpos){*ppheadpos-next;free(pos);return;}// 找pos的前一个节点SLTNode*prev*pphead;while(prevprev-next!pos){prevprev-next;}if(prevNULL)return;// pos不在链表中prev-nextpos-next;free(pos);}2.11 删除指定节点之后的节点voidSLTEraseAfter(SLTNode*pos){if(posNULL||pos-nextNULL)return;SLTNode*delpos-next;pos-nextdel-next;free(del);}2.12 销毁整个链表voidSLTDestroy(SLTNode**pphead){SLTNode*cur*pphead;while(cur){SLTNode*nextcur-next;free(cur);curnext;}*ppheadNULL;}三、测试代码示例intmain(){SLTNode*plistNULL;// 尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPrint(plist);// 1 - 2 - 3 - NULL// 头插SLTPushFront(plist,0);SLTPrint(plist);// 0 - 1 - 2 - 3 - NULL// 查找SLTNode*posSLTFind(plist,2);if(pos){printf(找到了节点%d\n,pos-data);// 在2之前插入99SLTInsert(plist,pos,99);SLTPrint(plist);// 0 - 1 - 99 - 2 - 3 - NULL// 在2之后插入100SLTInsertAfter(pos,100);SLTPrint(plist);// 0 - 1 - 99 - 2 - 100 - 3 - NULL// 删除2节点SLTErase(plist,pos);SLTPrint(plist);// 0 - 1 - 99 - 100 - 3 - NULL}// 头删SLTPopFront(plist);SLTPrint(plist);// 1 - 99 - 100 - 3 - NULL// 尾删SLTPopBack(plist);SLTPrint(plist);// 1 - 99 - 100 - NULL// 销毁链表SLTDestroy(plist);return0;}四、链表的分类链表的结构非常多样以下情况组合起来共有8种分类维度类型单向 / 双向单向链表、双向链表带头 / 不带头带头结点、不带头结点循环 / 不循环循环链表、非循环链表4.1 单向 or 双向单向链表每个节点只有一个指向下一个节点的指针。![单向链表](https://img-blog.csdnimg.cn/direct/xxx双向链表每个节点有指向前一个和后一个节点的两个指针可以双向遍历。4.2 带头 or 不带头带头链表有一个哨兵位头节点不存储有效数据简化插入删除操作。![带头链表](https://img-blog.csdnimg.cn/direct/xxx不带头链表头指针直接指向第一个有效节点。4.3 循环 or 不循环循环链表尾节点的next指向头节点形成一个环。![循环链表](https://img-blog.csdnimg.cn/direct/xxx非循环链表尾节点的next为NULL。4.4 实际中最常用的两种结构无头单向非循环链表结构简单常用于其他数据结构的子结构如哈希桶、图的邻接表笔试面试中出现频率很高带头双向循环链表结构最复杂但实现起来反而简单因为边界条件少常用于实际存储数据如C STL中的list五、总结链表是动态数据结构插入删除不需要移动元素但需要额外的指针存储空间。单链表实现简单但只能单向遍历删除节点时需要找到前驱。带头双向循环链表虽然结构复杂但操作统一实际开发中更常用。掌握单链表是理解更复杂链表的基础也是面试中的高频考点。