文章目录一、链表的分类常用链表类型1无头单向非循环链表(单链表)2带头双向循环链表(双向链表)二、双向链表的结构三、双向链表的实现1. 节点结构定义2. 主要操作函数(1) 初始化LTInit(2)销毁函数LTDestroy(3)打印LTPrint(4)尾插LTPushBack(5)尾删LTPopBack(6)头插LTPushFront(7)头删LTPopFront(8)指定位置后插入函数LTInsert(9)指定位置删除函数LTErase(10) 查找函数LTFind四、顺序表和双向链表的优缺点分析一、链表的分类链表的结构多样可通过以下三个维度组合出 8 种类型方向单向:只能从一个方向遍历双向:可以从两个方向遍历头部带头有哨兵位不带头循环性循环非循环常用链表类型1无头单向非循环链表(单链表)特点结构简单无哨兵位节点最后一个节点的next为NULL应用场景多作为其他数据结构的子结构如哈希桶、图的邻接表笔试面试高频考点2带头双向循环链表(双向链表)特点包含哨兵位头节点每个节点有prev和next两个指针尾节点的next指向头节点优势操作统一无需特殊处理空链表或首尾节点实现简单应用场景单独存储数据如STL中的list二、双向链表的结构双向链表中我们重点关注的是带头双向循环链表。这里的“带头”需要特别说明它和单链表中我们常说的“头节点”不是一个概念。在单链表阶段我们对“头节点”的称呼其实并不严谨为了便于理解才那样称呼。而带头双向循环链表中的“头节点”实际是“哨兵位”。“哨兵位”节点不存储任何有效元素它就像一个站在那里“放哨”的节点其存在的最大意义是避免在遍历循环链表时出现死循环。有了这个哨兵位我们在进行链表的遍历等操作时就有了一个明确的起点和终点判断依据大大降低了出错的概率。三、双向链表的实现1. 节点结构定义双向链表的节点结构。每个节点不仅要存储数据还要有两个指针分别指向它的前一个节点和后一个节点具体定义如下typedefintLTDataType;typedefstructListNode{structListNode*next;// 下一个节点structListNode*prev;// 前一个节点LTDataType data;}LN;2. 主要操作函数(1) 初始化LTInit初始化函数用于创建双向链表的哨兵位节点并构建带头双向循环的初始结构。注意单链表初始化空链表双向链表初始化只有一个头节点哨兵位实现思路动态开辟一个哨兵位节点。让哨兵位节点的prev和next指针都指向自身形成循环结构。注意不可以把prev和next指向空无法达到循环的效果LN*LTInit(){LN*phead(LN*)malloc(sizeof(LN));if(pheadNULL){perror(malloc fail);exit(-1);}phead-nextphead;phead-prevphead;returnphead;}该函数返回初始化好的哨兵位节点(2)销毁函数LTDestroy销毁函数用于释放链表中所有节点包括哨兵位的内存避免内存泄漏。实现思路先判断链表是否为空若为空则直接释放哨兵位。若不为空通过遍历找到每一个节点并释放最后释放哨兵位。voidLTDes(LN*phead){assert(phead);LN*pcurphead-next;while(pcur-next!phead){LN*nextpcur-next;free(pcur);pcurnext;}free(phead);pheadNULL;}通过循环遍历释放除哨兵位外的所有节点最后释放哨兵位完成链表的销毁。(3)打印LTPrint实现思路哨兵位没有有效数据从哨兵位的下一个节点开始遍历。遍历至重新回到哨兵位时停止依次打印每个节点的数据。voidLTPrint(LN*phead){assert(phead);LN*curphead-next;printf(哨兵位-);while(cur!phead){printf(%d-,cur-data);curcur-next;}printf(\n);}(4)尾插LTPushBack注意无论头插尾插还是头删尾删都不可以改变哨兵位因此这里传递一级指针即可实现思路找到链表的尾节点哨兵位的prev指针所指节点。建立新节点与尾节点、哨兵位之间的双向链接。voidLTPushBack(LN*phead,LTDataType x){assert(phead);LN*newNodeLTBuyNode(x);//先改newNodenewNode-prevphead-prev;newNode-nextphead;//两行代码不能交换phead-prev-nextnewNode;phead-prevnewNode;}(5)尾删LTPopBack实现思路先判断链表是否为空为空则无法删除。找到尾节点及其前一个节点通过调整指针解除尾节点的链接并释放其内存。voidLTPopBack(LN*phead){assert(pheadphead-next!phead);LN*delphead-prev;del-prev-nextphead;phead-prevdel-prev;free(del);delNULL;}(6)头插LTPushFront头部插入函数用于在哨兵位之后添加新节点。实现思路找到哨兵位的下一个节点原头节点。建立新节点与哨兵位、原头节点之间的双向链接。voidLTPushFront(LN*phead,LTDataType x){assert(phead);LN*newNodeLTBuyNode(x);newNode-nextphead-next;newNode-prevphead;//这两行代码不可以交换phead-next-prevnewNode;phead-nextnewNode;}利用双向链表的指针特性快速完成头部插入操作。(7)头删LTPopFront头部删除函数用于移除哨兵位之后的第一个节点。实现思路先判断链表是否为空为空则无法删除。找到原头节点及其下一个节点调整指针解除原头节点的链接并释放其内存。voidLTPopFront(LN*phead){assert(pheadphead-next!phead);LN*delphead-next;phead-nextdel-next;del-next-prevphead;free(del);delNULL;}(8)指定位置后插入函数LTInsert实现思路找到pos节点的下一个节点。建立新节点与pos节点、pos下一个节点之间的双向链接。voidLTInsert(LN*pos,LTDataType x){assert(pos);LN*newNodeLTBuyNode(x);newNode-prevpos;newNode-nextpos-next;pos-next-prevnewNode;pos-nextnewNode;}该方法可以包含头插操作但是头插不包含该操作。根本区别是头插给定的节点是哨兵位哨兵位不能存放有效数据(9)指定位置删除函数LTErase实现思路找到pos节点的前一个和后一个节点。调整这两个节点的指针解除与pos节点的链接并释放pos节点的内存。voidLTErase(LN*pos){assert(pospos-next!pos);pos-next-prevpos-prev;pos-prev-nextpos-next;free(pos);posNULL;}通过该函数可方便地实现头删、尾删等操作。(10) 查找函数LTFind查找函数用于在链表中寻找数据为x的节点。实现思路从哨兵位的下一个节点开始遍历。若找到数据为x的节点则返回该节点遍历结束仍未找到则返回NULL。LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*curphead-next;while(cur!phead){if(cur-datax){returncur;}curcur-next;}returnNULL;}注意理论上来说以下三个函数应该传二级指针但是这会增加调用方记忆成本。void LTInsert(LN* pop, LTDataType x);void LTErase(LN* pop);void LTDes(LN* phead);为了统一接口可以统一传入一级指针但存在的问题是形参改变phead置为NULL不会影响实参这就需要调用方手动把plist置空四、顺序表和双向链表的优缺点分析为了更好地理解双向链表的适用场景我们将它与顺序表进行对比分析不同点顺序表链表这里主要指双向链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持时间复杂度为O(1)不支持时间复杂度为O(N)任意位置插入或者删除元素可能需要搬移元素效率低时间复杂度为O(N)只需修改指针指向效率高插入相关动态顺序表在空间不够时需要扩容没有容量的概念不需要扩容应用场景适用于元素高效存储且需要频繁访问的场景适用于任意位置插入和删除操作频繁的场景