【数据结构与算法】-双向链表

个人主页深邃-❄️专栏传送门《C语言》《数据结构》Gitee仓库《C语言》《数据结构》目录链表的分类概念与结构概念结构实现双向链表双向链表申请新节点初始化链表销毁链表尾插头插打印链表链表判空尾删头删查找元素在pos位置之后插入数据删除pos位置的节点顺序表与链表的分析链表的分类以下两张链表的分类概念与结构概念注意这里的“带头”跟前面我们说的“头结点”是两个概念实际前面的在单链表阶段称呼不严谨但是为了同学们更好的理解就直接称为单链表的头结点。带头链表里的头结点实际为“哨兵位”哨兵位结点不存储任何有效元素只是站在这里“放哨的结构头文件定义双向链表结构//定义双向链表结构typedefintLTDataType;typedefstructListNode{LTDataType data;structListNode*next;//指向下一个节点的指针structListNode*prev;//指向前一个节点的指针}LTNode;接下来实现的函数声明//初始化//void LTInit(LTNode** pphead);LTNode*LTInit();//销毁---为了保持接口一致性//void LTDesTroy(LTNode** pphead);voidLTDesTroy(LTNode*phead);//在双向链表中增删改查都不会改变哨兵位节点//尾插voidLTPushBack(LTNode*phead,LTDataType x);//头插voidLTPushFront(LTNode*phead,LTDataType x);//尾删voidLTPopBack(LTNode*phead);//头删voidLTPopFront(LTNode*phead);boolLTEmpty(LTNode*phead);voidLTPrint(LTNode*phead);LTNode*LTFind(LTNode*phead,LTDataType x);//在pos位置之后插⼊数据----在pos位置之前插入数据自行实现voidLTInsert(LTNode*pos,LTDataType x);//删除pos位置的节点voidLTErase(LTNode*pos);实现双向链表源文件双向链表申请新节点LTNode*LTBuyNode(LTDataType x){LTNode*newnode(LTNode*)malloc(sizeof(LTNode));if(newnodeNULL){perror(malloc fail!);exit(1);}newnode-datax;newnode-nextnewnode-prevnewnode;returnnewnode;}初始化链表传二级针织修改外部pheadvoidLTInit(LTNode**pphead)//传二级针织修改外部phead{*ppheadLTBuyNode(-1);}优化不需要传任何值直接返回初始化的节点 不需要传任何值直接返回初始化的节点不需要传任何值直接返回初始化的节点//初始化LTNode*LTInit(){LTNode*pheadLTBuyNode(-1);returnphead;}销毁链表voidLTDesTroy(LTNode**pphead){LTNode*pcur(*pphead)-next;while(pcur!*pphead){LTNode*nextpcur-next;free(pcur);pcurnext;}//销毁头结点free(*pphead);*ppheadNULL;}为了保证接口一致性我们给出优化但是注意传一级指针返回新的头指针切记用头指针接收否则成为野指针//销毁LTNode*LTDesTroy(LTNode*phead){assert(phead!NULL);LTNode*pcurphead-next;while(pcur!phead){LTNode*nextpcur-next;free(pcur);pcurnext;}//销毁头结点free(phead);returnNULL;}尾插注意顺序先改头节点的前驱指针的后继节点再改头节点的前驱指针否则找尾节点很费劲//尾插voidLTPushBack(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTBuyNode(x);//phead phead-prev newnodenewnode-prevphead-prev;newnode-nextphead;phead-prev-nextnewnode;phead-prevnewnode;}头插注意顺序同上//头插voidLTPushFront(LTNode*phead,LTDataType x){assert(phead);LTNode*newnodeLTBuyNode(x);//phead newnode phead-nextnewnode-nextphead-next;newnode-prevphead;phead-next-prevnewnode;phead-nextnewnode;}打印链表voidLTPrint(LTNode*phead){LTNode*pcurphead-next;while(pcur!phead){printf(%d - ,pcur-data);pcurpcur-next;}printf(\n);}链表判空链表成环即为空boolLTEmpty(LTNode*phead){assert(phead);returnphead-nextphead;}尾删//尾删voidLTPopBack(LTNode*phead){assert(!LTEmpty(phead));LTNode*delphead-prev;del-prev-nextphead;phead-prevdel-prev;free(del);delNULL;}头删//头删voidLTPopFront(LTNode*phead){assert(!LTEmpty(phead));LTNode*delphead-next;del-next-prevphead;phead-nextdel-next;free(del);delNULL;}查找元素LTNode*LTFind(LTNode*phead,LTDataType x){assert(phead);LTNode*pcurphead-next;while(pcur!phead){if(pcur-datax){returnpcur;}pcurpcur-next;}//未找到returnNULL;}在pos位置之后插入数据注意顺序同上//在pos位置之后插⼊数据voidLTInsert(LTNode*pos,LTDataType x){assert(pos);LTNode*newnodeLTBuyNode(x);//pos newnode pos-nextnewnode-prevpos;newnode-nextpos-next;pos-next-prevnewnode;pos-nextnewnode;}删除pos位置的节点//删除pos位置的节点voidLTErase(LTNode*pos){assert(pos);//pos-prev pos pos-nextpos-prev-nextpos-next;pos-next-prevpos-prev;free(pos);posNULL;}顺序表与链表的分析通过表格理解 \color{blue}{通过表格理解}通过表格理解不同点顺序表链表单链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容和空间浪费没有容量的概念按需申请释放不存在空间浪费应用场景元素高效存储频繁访问任意位置高效插入和删除