文章目录什么是双链表双链表的结构定义双链表的初始化双链表的插入按位序插入前插操作双链表的删除拓展按位序删除拓展已知结点 p直接删除自身销毁双链表双链表的遍历正向遍历反向遍历时间复杂度什么是双链表单链表结点只有一个 next 指针只能向后遍历无法直接找到前驱结点。双链表每个结点包含两个指针可实现双向遍历可进可退。next指向后继结点prior指向前驱结点优点可以向前、向后双向遍历已知某结点p可以直接找到前驱删除、前插都不需要遍历时间复杂度为 O(1)。双链表的结构定义typedefstructDNode{intdata;// 数据域structDNode*prior;// 前驱指针指向前一个结点structDNode*next;// 后继指针指向后一个结点}DNode,*DLinkList;// DLinkList 与 DNode * 等价// 初始化与单链表相似只是多了一个前驱指针对比单链表单链表只有 next只能往右走双链表多了 prior能往左走。下面将只介绍带头结点的双链表也强烈建议使用“带头结点”的双链表。头结点不存有效数据头结点:prior NULL头结点的priorNULL绝不指向任何有效数据节点尾结点:next NULL双链表的初始化// 初始化带头结点的双链表boolInitDLinkList(DLinkListL){L(DNode*)malloc(sizeof(DNode));// 创建头结点if(LNULL)returnfalse;L-priorNULL;// 头结点的 prior 永远指向 NULL没有前驱L-nextNULL;// 头结点后面暂时没有节点置空returntrue;}// 判断双链表是否为空带头结点boolEmpty(DLinkList L){return(L-nextNULL);}双链表的插入在p结点之后插入s结点已知结点指针p在p后面插入新结点s按位序插入和前插操作都可以理解成后插。利用双向性找到i的前驱结点i-1对前驱结点进行后插操作。// 在 p 结点之后插入 s 结点后插boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)returnfalse;// 1. s 先抓住后面的节点远方s-nextp-next;// 2. s 指回 p近处s-priorp;// 3. 如果 p 原来后面有节点即 p 不是尾结点让那个节点的 prior 指向 sif(p-next!NULL){p-next-priors;}// 4. p 的 next 断开旧的指向 sp-nexts;returntrue;}按位序插入思路先用类似单链表的方式找到第i-1个结点 p调用上面后插函数。boolDListInsert(DLinkListL,inti,inte){if(i1)returnfalse;DNode*pL;intj0;while(p!NULLji-1){pp-next;j;}if(pNULL)returnfalse;returnInsertNextDNode(p,e);}前插操作想要在p结点前面插入s不需要向前遍历找到p的前驱pre p-prior在pre后面插入s复用InsertNextDNodeInsertNextDNode(p-prior,e);双链表的删除删除 p 的后继结点 q。// 删除 p 结点的后继结点并将数据带回boolDeleteNextDNode(DNode*p,inte){if(pNULL)returnfalse;DNode*qp-next;// q 指向要被删除的节点if(qNULL)returnfalse;// p 后面没有节点无法删除eq-data;// 保存数据// 1. 让 p 的 next 跳过 q指向 q 后面的节点p-nextq-next;// 2. 如果 q 不是尾结点即 q-next 不为空让后面那个节点的 prior 指回 pif(q-next!NULL){q-next-priorp;}// 3. 释放 q 的内存free(q);returntrue;}拓展按位序删除先找到第i-1个结点 p删除 p 后继boolDListDelete(DLinkListL,inti,inte){if(i1)returnfalse;DNode*pL;intj0;while(p!NULLji-1){pp-next;j;}if(pNULL)returnfalse;returnDeleteNextDNode(p,e);}拓展已知结点 p直接删除自身// 删除结点pboolDeleteDNode(DNode*p){if(pNULL)returnfalse;DNode*prep-prior;pre-nextp-next;if(p-next!NULL){p-next-priorpre;}free(p);returntrue;}销毁双链表利用上面的删除函数可以轻松销毁整张表voidDestroyList(DLinkListL){while(L-next!NULL){// 只要头结点后面还有节点inte;// 不需要保存数据DeleteNextDNode(L,e);// 一直删除头结点的后继}free(L);// 最后释放头结点LNULL;}双链表的遍历正向遍历// 正向遍历从第一个有效节点开始voidPrintListForward(DLinkList L){DNode*pL-next;// 跳过头结点while(p!NULL){printf(%d ,p-data);pp-next;}}反向遍历// 反向遍历从最后一个节点往前找需要先找到尾结点voidPrintListBackward(DLinkList L){DNode*pL;// 1. 先走到最后一个节点尾结点while(p-next!NULL){pp-next;}// 2. 从尾结点利用 prior 指针倒着走while(p!L){// 没回到头结点之前printf(%d ,p-data);pp-prior;}}时间复杂度双链表不可随机存取按位查找、按值查找操作都只能用遍历的方式实现时间复杂度为O(n)。删除、前插都不需要遍历时间复杂度为 O(1)。