0
0

【带你了解C++标准库为何在八大链表结构中选择了它】双向循环带头链表的实质性操作

在这里插入图片描述

文章目录

🚀八大链表结构为何选择了它

C++的STL库选择的最终链表结构为双向循环带头链表
为什么选择了它呢，是因为它的结构更优，虽然形式看似复杂，但的它便利性相比其他链表好得多
C++标准库中把list设计为带头节点的双向循环链表是很合理的，不信你往后看它的操作实现过程相比于单链表来说有多简单，当然你也可以用其他的六种结果来对比，结果一定是双向循环带头链表更胜一筹认识八种链表的类型

  1. 单向带头非循环链表
  2. 单向不带头循环链表
  3. 单向不带头非循环链表
  4. 双向带头循环链表
  5. 双向带头非循环链表
  6. 双向不带头循环链表
  7. 双向不带头非循环链表
  8. 双向循环带头链表✨

一些链表图示
这里是引用

常用的两类链表结构
我们在单链表的一系列操作中讲过单链表是在一些OJ题的常考题

单链表只能单向循环链表
循环双向链表就是一个环形，可以逆时针走，可以顺时针走，而双向链表是一个链，只能双向遍历。这里是引用

🚀初始化和打印

初始化

我们的双向循环链表采用的是带哨兵位的头结点，它的初始化为了避免要传二级指针，可以设置用返回值的函数带回地址
下面一张图再次带你认识带哨兵位的头结点和不带哨兵位的头结点区别

在这里插入图片描述
要注意双向循环带头链表的初始化跟单链表有所区别，双向循环链表是不会指向NULL的，它没有节点的时候是下面的这种形式>

在这里插入图片描述
其实就是自己的头和尾都指向自己，这才能体现它的循环结构

在初始的时候是需要创建新节点作为头结点的，而且后续的头插，尾插等等都需要创建新节点，为了避免重复操作，直接建立一个BuyListNode函数用来创建新节点

//创建新节点
LTNode*BuyListNode(LTDateType x){
    LTNode* newNode =(LTNode*)malloc(sizeof(LTNode));if(newNode ==NULL){exit(-1);}
    newNode->date = x;
    newNode->next =NULL;
    newNode->prev =NULL;return newNode;}

//初始化
LTNode*ListInit(){
    LTNode* phead =BuyListNode(0);

    phead->prev = phead;
    phead->next = phead;return phead;}//用一个指针接收地址
LTNode* list =ListInit();

打印

打印过程图解
这里是引用

//打印voidListPrint(LTNode* phead){
    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->date);
        cur = cur->next;}printf("\n");}

🚀尾插和尾删

尾插

双向循环带头链表的 尾插实在比单链表简单得多了，因为它是循环双向链表，你看 尾节点的next不就指向头结点的phead吗，那头结点的prev不就指向尾节点吗
是不是就直接省去了像单链表哪样遍历链表找尾的过程，直接将时间复杂度优化到O(1)
那找到尾之后的操作就是连接节点之间的关系，比较简单，直接看图理解
这里是引用

//尾插voidListPushBack(LTNode* phead,LTDateType x){assert(phead);//新节点
    LTNode* newNode =BuyListNode(x);//找尾
    LTNode* tail = phead->prev;//连接
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = phead;
    phead->prev = newNode;}

尾删

尾删也不难，同样的找尾步骤，注意的是要记录好尾节点的前一个节点，让它来当新的尾节点

动画演示>在这里插入图片描述

//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;}

🚀头插和头删

头插

头插要注意的是不是在哨兵位的头前面插入，而是在哨兵位的头结点的后一个插入，因为哨兵位只是是不存放有效数据的，但它一定是在最前的

动画演示>
在这里插入图片描述

//头插voidListPushFront(LTNode* phead, LTDateType x){assert(phead);
    LTNode* newNode =BuyListNode(x);//连接
    LTNode* next = phead->next;
    phead->next = newNode;
    newNode->prev = phead;

    newNode->next = next;
    next->prev = newNode;}

头删

头删也是像尾删一样要记录好要删节点的下一个节点

在这里插入图片描述

//头删voidListPopFront(LTNode* phead){assert(phead);//链表为空assert(phead->next != phead);

    LTNode* next = phead->next;
    LTNode* nextNext = next->next;free(next);
    phead->next = nextNext;
    nextNext->prev = phead;}

🚀查找和插入

查找

查找就是遍历链表，跟单链表一样的操作，找到了就返回改节点的地址，找不到就返回NULL

//查找
LTNode*ListFind(LTNode* phead, LTDateType x){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){if(cur->date == x)return cur;
        cur = cur->next;}returnNULL;}

插入

插入是往该数据的前一个位置插入
插入就跟单链表的操作大大不同了， 双向循环带头链表的插入比起 单链表来说是非常容易的，你把你要在哪个位置插入的指针传给它，它可以直接找到 前一个节点，而单链表却没有这个性质

插入功能是和查找功能搭配使用的，用之前先用查找获取把该数据的指针，然后传给插入函数
那你们想想，如果我把phead的指针传给插入函数，那phead的前一个不就是尾节点吗，那不就是相当于尾插吗，同样如果我们把phead的next传给插入函数，哪不就是相当于头插吗！！
所以我们的头插和尾插是不是可以改造成这样子
在这里插入图片描述
这样之后我们写头插和尾插就省去了很大时间

//插入voidListInsert(LTNode* pos, LTDateType x){assert(pos);

    LTNode* newNode =BuyListNode(x);

    LTNode* posPrev = pos->prev;

    posPrev->next = newNode;
    newNode->prev = posPrev;
    newNode->next = pos;
    pos->prev = newNode;}

🚀删除和销毁

删除

删除也是搭配查找函数一起使用，把要的地址传过去即可删除

在这里插入图片描述

//删除voidListErase(LTNode* pos){assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    posPrev->next = posNext;
    posNext->prev = posPrev;free(pos);}

销毁

销毁就是遍历链表一个一个的free即可

//销毁链表voidListDestroy(LTNode* phead){
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;free(cur);
        cur = next;}free(phead);}//记得最后把销毁链表，还要把list置空ListDestroy(list);
    list =NULL;

🚀小结

如果你动手实操了，一定感受到双向循环链表中的一些操作实现是不用考虑像单链表那样的分情况讨论，比如单链表在实现头插的时候不就是要分链表为空和不为空的情况吗，而它却不必考虑这些顾虑，还有很多区别于其他链表的优势，只能你自己去一 一感受！！

✨链表功能动画演示

在这里插入图片描述

✨逻辑实现text.c

text.c为工程整体逻辑实现

voidmenu(){printf("*******************************\n");printf("       1.尾插   2.尾删         \n");printf("       3.头插   4.头删         \n");printf("       5.插入   6查找          \n");printf("       7.删除   -1.退出        \n");printf("       8.打印                  \n");printf("*******************************\n");printf(" 请选择>:   \n");}voidTextmenu(){
    LTNode* list =ListInit();int input =0;
    LTDateType x1 =0;
    LTNode* pos =NULL;while(input !=-1){menu();scanf("%d",&input);switch(input){case1:printf("请输入要尾插的数据，以-1为结束\n");scanf("%d",&x1);while(x1 !=-1){ListPushBack(list, x1);scanf("%d",&x1);}printf("尾插成功\n");break;case2:ListPopBack(list);printf("尾删成功\n");break;case3:printf("请输入要头插的数据，以-1为结束\n");scanf("%d",&x1);while(x1 !=-1){ListPushFront(list, x1);scanf("%d",&x1);}printf("头插成功\n");break;case4:ListPopFront(list);printf("头删成功\n");break;case5:printf("请输入你要在哪里个数据前插入>:\n");scanf("%d",&x1);
             pos=ListFind(list, x1);if(pos !=NULL){printf("请输入你要插入的数据>:\n");scanf("%d",&x1);ListInsert(pos, x1);printf("插入成功\n");}else{printf("无此数据\n");}break;case6:printf("请输入你要查找的数据\n");scanf("%d",&x1);
            pos=ListFind(list, x1);if(pos !=NULL){printf("%d的地址为%p\n", x1, pos);}else{printf("链表没有此数据\n");}break;case7:printf("请输入你要删除的数据\n");scanf("%d",&x1);
            pos =ListFind(list, x1);if(pos !=NULL){ListErase(pos);printf("删除成功\n");}else{printf("链表中没有此数据\n");}break;case8:printf("链表数据为：");ListPrint(list);break;case-1:printf("退出成功\n");break;default:printf("无此选项，请重新输入！\n");break;}}//记得最后把销毁链表，还要把list置空ListDestroy(list);
    list =NULL;}intmain(){Textmenu();}

✨头文件List.h

List.h为工程头文件（头文件和函数声明）

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint LTDateType;typedefstructListNode{
    LTDateType date;structListNode* next;structListNode* prev;}LTNode;//初始化
LTNode*ListInit();//打印voidListPrint(LTNode* phead);//创建新节点
LTNode*BuyListNode(LTDateType x);//尾插voidListPushBack(LTNode* phead, LTDateType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LTDateType x);//头删voidListPopFront(LTNode* phead);//查找,找到返回对应数据地址，找不到返回NULL
LTNode*ListFind(LTNode* phead, LTDateType x);//插入，在pos位置之前插入voidListInsert(LTNode* pos, LTDateType x);//删除指定位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

✨函数实现List.c

List.c为工程源文件（函数实现）

#define_CRT_SECURE_NO_WARNINGS#include"List.h"//初始化
LTNode*ListInit(){
    LTNode* phead =BuyListNode(0);

    phead->prev = phead;
    phead->next = phead;return phead;}//打印voidListPrint(LTNode* phead){
    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->date);
        cur = cur->next;}printf("\n");}//尾插voidListPushBack(LTNode* phead,LTDateType x){assert(phead);//新节点//LTNode* newNode = BuyListNode(x);//找尾//LTNode* tail = phead->prev;//连接//tail->next = newNode;//newNode->prev = tail;//newNode->next = phead;//phead->prev = newNode;//可用插入函数代替尾插ListInsert(phead, x);}//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//free(tail);//tailPrev->next = phead;//phead->prev = tailPrev;//可用删除函数代替尾删ListErase(phead->prev);}//头插voidListPushFront(LTNode* phead, LTDateType x){assert(phead);
    LTNode* newNode =BuyListNode(x);//连接
    LTNode* next = phead->next;
    phead->next = newNode;
    newNode->prev = phead;

    newNode->next = next;
    next->prev = newNode;//可用插入函数代替头插//ListInsert(phead->next, x);}//头删voidListPopFront(LTNode* phead){assert(phead);//链表为空assert(phead->next != phead);

    LTNode* next = phead->next;
    LTNode* nextNext = next->next;free(next);
    phead->next = nextNext;
    nextNext->prev = phead;//可用删除函数代替头删//ListErase(phead->next);}//查找
LTNode*ListFind(LTNode* phead, LTDateType x){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){if(cur->date == x)return cur;
        cur = cur->next;}returnNULL;}//插入voidListInsert(LTNode* pos, LTDateType x){assert(pos);

    LTNode* newNode =BuyListNode(x);

    LTNode* posPrev = pos->prev;

    posPrev->next = newNode;
    newNode->prev = posPrev;
    newNode->next = pos;
    pos->prev = newNode;}//删除voidListErase(LTNode* pos){assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    posPrev->next = posNext;
    posNext->prev = posPrev;free(pos);}//创建新节点
LTNode*BuyListNode(LTDateType x){
    LTNode* newNode =(LTNode*)malloc(sizeof(LTNode));if(newNode ==NULL){exit(-1);}
    newNode->date = x;
    newNode->next =NULL;
    newNode->prev =NULL;return newNode;}//销毁链表voidListDestroy(LTNode* phead){
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;free(cur);
        cur = next;}free(phead);}
标签： 链表 c++ 数据结构
本文转载自: https://blog.csdn.net/dongming8886/article/details/124550703
版权归原作者 Next week* 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【带你了解C++标准库为何在八大链表结构中选择了它】双向循环带头链表的实质性操作”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航