当前位置： 首页 > news >正文

数据结构体进阶链表【带头双向循环链表，单向链表的优化，从根部解决了顺序表的缺点】一文带你深入理解链表

news 来源：原创 2024/4/24 15:28:20

 前言：

   对于链表，上一篇的单链表解决了顺序表的一部分缺陷，但并没有彻底的解决顺序表的问题，比如在进行单链表尾插尾删的时候还是需要进行遍历找尾，并没有达到全部的O(1)，并且在头插的时候还要分情况来考虑，比如传入为空指针和不是空指针时候还要分情况考虑，对于指针的改变还要传二级指针，这对于一部分人来说并不熟悉，所以！！！今天看完这篇文章，掌握带双向循环数据表，让我们不再害怕链表的增删插改😎😎

     💞 💞    欢迎来到小马学习代码博客！！！！

                

 思维导图：

目录

一、链表实现前的准备 

💜1.1结构

图：

💜1.2初步的理解：

二、带头双向链表功能实现前的准备

🤎 2.1链表实现所需要的头文件：

🤎2.2链表实现的初始化：

🤎2.2链表实现的打印：

🤎2.3定义一个节点为了实现插入：

🤎2.4判断节点是否为空节点：

🤎2.5链表实现后的销毁：

3、链表功能的实现

❤️3.1链表的头插：

❤️3.2链表的尾插：

❤️3.3链表的头删：

❤️3.4链表的尾删：

❤️3.5链表的pos位插入：

❤️3.6链表的pos位删除：

❤️3.7链表的查找：

4、带头双向循环链表的源码

💚4.1 List.h

💚4.2List.c

💚4.3Test.c

总结：

一、链表实现前的准备 

💜1.1结构图：

～带头双向循环链表我们不要被他的结构图所吓到，只要我么深入理解他的原理，你会发现它的代码实现起来比单链表还要简单。

💜1.2初步的理解：

1.2.1 对于带头双向循环链表，要知道它的结构是比较复杂的，但是他的代码实现是比较简单的，所以，对于代码实现前，我想先讲述一下带头双向循环链表：对于带头双向循环链表我们先一步步理解，👉带头的意思就是在插入之前我们先初始化一个结构体，他并不是用来存储数据，而是保证链表有一个头节点，就可以减少讨论（当传入指针为空时，当传入指针不为空时），👉双向是指我们的结构体中存量结构体指针，一个是指向下一个，另一个是指向他的前一个，这样就保证在寻找的时候找不到前一个的位置。 👉循环是指在尾节点我们并不让他指向空指针，而是让他指向头节点，而头节点的前一个也不让他指向空指针，而是让他指向尾节点，这样就会达成一个循环的作用，他的好处就是在于我们们寻找尾节点的时候就不用遍历了，而是通过找头节点的前一个就能找到尾节点，从而达到时间复杂度为O(1)来完成尾插和尾删！

二、带头双向链表功能实现前的准备

🤎 2.1链表实现所需要的头文件：

#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

💖  这里是害怕有的小伙伴有的头文件并不知道^ _ ^ 。

🤎2.2链表实现的初始化：

LTNode* ListInit() //返回结构体指针
{
    LTNode*guard=(LTNode*)malloc(sizeof(LTNode)); //这里就像定义一个哨兵，也就是头节点，就不用再担心头节点是不是NULL了
    if(guard==NULL) //确保能够正常扩容
    {
        perror("ListNodeInit");
    }
    guard->next=guard; //头节点的下一个先指向自己
    guard->prev=guard; //头节点的上一个也先指向自己
    return guard;
}

🤎2.2链表实现的打印：

void ListNodePrint(LTNode* phead)
{
    assert(phead);   //保证传入的不是空指针
    LTNode* cur =phead->next; //定一个结构体指针进行遍历打印
    printf("guard<=>");  //这里是为了打印效果好看一点
    while(cur!=phead)
    {
        printf("%d<=>",cur->data);
        cur=cur->next;
    }
    printf("\n");
}

🤎2.3定义一个节点为了实现插入：

LTNode*  BuyListNode(LTDataType x)
{
    LTNode* newnode=(LTNode*)malloc(sizeof(ListNode)); //节点申请空间
    if(newnode==NULL)
    {
        perror("BuyListNode");
    }
    newnode->data=x;  //节点所带的值
    newnode->prev=NULL;
    newnode->next=NULL;
    return newnode;
}

🤎2.4判断节点是否为空节点：

bool ListEmpty(LTNode*phead)
{
    assert(phead);
    return phead->next==phead; //如果头和头的下一个指向同一个则返回真，证明只有一个哨兵
}

🤎2.5链表实现后的销毁：

void ListDestroy(LTNode*phead)
{
    LTNode*cur=phead->next; //定义一个结构体指针进行遍历销毁
    while(cur!=phead)
    {
        LTNode*next=cur->next;
        free(cur);
        cur=next;
    }
    free(phead); //最后释放头节点
}

3、链表功能的实现

❤️3.1链表的头插：

void  ListPushFront(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode=BuyListNode(x); //先定义一个节点进行头插
    newnode->next=phead->next;  //这里要考虑顺序问题，不然很容易出错，先让定义的next指向哨兵的下一个，然后哨兵下一个的prev指向我们新的节点
        //然后让我们我们哨兵的next指向新节点，新节点的prev指向哨兵， 这里如果不理解的可以画一下图
       //或者我么先定义一个节点把哨兵的下一个进行保存这里就不用考虑先后顺序了，大家可以试一试
    phead->next->prev=newnode;
    phead->next=newnode;
    newnode->prev=phead;
}

❤️3.2链表的尾插：

void ListPushBack(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode=BuyListNode(x);  //定义一个新节点
    LTNode* tail=phead->prev;  //找到尾节点
    tail->next=newnode;  //然后就是交换结构体里面的next prev指向的位置来实现插入。头插我已经讲述过程了，主要是大家尝试一下画画图
    newnode->prev=tail;
    newnode->next=phead;
    phead->prev=newnode;
}

❤️3.3链表的头删：

void ListPopFront(LTNode*phead)
{
    assert(phead);
    assert(!ListEmpty(phead)); //这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
    LTNode*first=phead->next;  //定义一个first指向哨兵的next
    LTNode* second=first->next; //在定义一个second指向first的next
    phead->next=second;
    second->prev=phead;
    free(first);  //把first删除后进行free
    first=NULL;  //first指针指向空，防止出现野指针
}

❤️3.4链表的尾删：

void ListPopBack(LTNode*phead)
{
    assert(phead);
    assert(!ListEmpty(phead));//这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
    LTNode*tail=phead->prev;
    tail->prev->next=phead;
    phead->prev=tail->prev;
    free(tail);
    tail=NULL;
}

❤️3.5链表的pos位插入：

void ListInsert(LTNode*pos,LTDataType x)
{
    assert(pos); //保证传入的pos位不是空指针
    LTNode*prev=pos->prev; //找到pos位的前一位
    LTNode*newnode=BuyListNode(x);  //定义一个新节点进行插入
    pos->prev=newnode;
    newnode->next=pos;
    prev->next=newnode;
    newnode->prev=prev;
}

❤️3.6链表的pos位删除：

void ListErase(LTNode*pos)
{
    LTNode*prev=pos->prev;//找到pos位的前一个
    LTNode*next=pos->next; //找到pos的后一个
    prev->next=next;
    next->prev=prev;
    free(pos);  //释放pos
}

❤️3.7链表的查找：

LTNode* ListNodeFind(LTNode*phead,LTDataType x)  //查找后返回指针，如果找到返回找的到的结构体指针，没有找到返回空指针
{
    assert(phead);
    LTNode* cur=phead->next;  //定义一个结构体指针进行遍历寻找
    while(cur!=phead)
    {
        if(cur->data==x)
        {
            return cur;  //找到后返回的指针
        }
        cur=cur->next;  
    }
    return NULL;
}

4、带头双向循环链表的源码

💚4.1 List.h

#ifndef List_hpp
#define List_hpp

#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode*next;
    struct ListNode*prev;
    LTDataType data;
}LTNode;
LTNode* ListInit();
LTNode*  BuyListNode(LTDataType x);
void  ListPushBack(LTNode*phead,LTDataType x);
void ListNodePrint(LTNode* phead);
void  ListPushFront(LTNode*phead,LTDataType x);
void ListPopBack(LTNode*phead);
bool ListEmpty(LTNode*phead);
void ListPopFront(LTNode*phead);
size_t ListSize(LTNode*phead);
LTNode* ListNodeFind(LTNode*phead,LTDataType x);
void ListInsert(LTNode*pos,LTDataType x);
void ListErase(LTNode*pos);
void ListDestroy(LTNode*phead);

#endif /* List_hpp */

💚4.2List.c

#include "List.hpp"
LTNode* ListInit()
{
    LTNode*guard=(LTNode*)malloc(sizeof(LTNode)); //这里就像定义一个哨兵，也就是头节点，就不用再担心头节点是不是NULL了
    if(guard==NULL) //确保能够正常扩容
    {
        perror("ListNodeInit");
    }
    guard->next=guard; //头节点的下一个先指向自己
    guard->prev=guard; //头节点的上一个也先指向自己
    return guard;
}
LTNode*  BuyListNode(LTDataType x)
{
    LTNode* newnode=(LTNode*)malloc(sizeof(ListNode)); //节点申请空间
    if(newnode==NULL)
    {
        perror("BuyListNode");
    }
    newnode->data=x;  //节点所带的值
    newnode->prev=NULL;
    newnode->next=NULL;
    return newnode;
}
void ListNodePrint(LTNode* phead)
{
    assert(phead);   //保证传入的不是空指针
    LTNode* cur =phead->next; //定一个结构体指针进行遍历打印
    printf("guard<=>");  //这里是为了打印效果好看一点
    while(cur!=phead)
    {
        printf("%d<=>",cur->data);
        cur=cur->next;
    }
    printf("\n");
}
void ListPushBack(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode=BuyListNode(x);  //定义一个新节点
    LTNode* tail=phead->prev;  //找到尾节点
    tail->next=newnode;  //然后就是交换结构体里面的next prev指向的位置来实现插入。头插我已经讲述过程了，主要是大家尝试一下画画图
    newnode->prev=tail;
    newnode->next=phead;
    phead->prev=newnode;
}
void  ListPushFront(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode=BuyListNode(x); //先定义一个节点进行头插
    newnode->next=phead->next;  //这里要考虑顺序问题，不然很容易出错，先让定义的next指向哨兵的下一个，然后哨兵下一个的prev指向我们新的节点
        //然后让我们我们哨兵的next指向新节点，新节点的prev指向哨兵， 这里如果不理解的可以画一下图
       //或者我么先定义一个节点把哨兵的下一个进行保存这里就不用考虑先后顺序了，大家可以试一试
    phead->next->prev=newnode;
    phead->next=newnode;
    newnode->prev=phead;
}
bool ListEmpty(LTNode*phead)
{
    assert(phead);
    return phead->next==phead; //如果头和头的下一个指向同一个则返回真，证明只有一个哨兵
}
void ListPopBack(LTNode*phead)
{
    assert(phead);
    assert(!ListEmpty(phead));//这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
    LTNode*tail=phead->prev;
    tail->prev->next=phead;
    phead->prev=tail->prev;
    free(tail);
    tail=NULL;
}
void ListPopFront(LTNode*phead)
{
    assert(phead);
    assert(!ListEmpty(phead)); //这里防止只剩下一个哨兵，如果只剩下一个哨兵还进行删除就强制类型报错
    LTNode*first=phead->next;  //定义一个first指向哨兵的next
    LTNode* second=first->next; //在定义一个second指向first的next
    phead->next=second;
    second->prev=phead;
    free(first);  //把first删除后进行free
    first=NULL;  //first指针指向空，防止出现野指针
}
size_t ListSize(LTNode*phead)
{
    assert(phead);
    LTNode*cur=phead->next;
    size_t n=0;
    while(cur!=phead)
    {
        ++n;
        cur=cur->next;
    }
    return n;
}
LTNode* ListNodeFind(LTNode*phead,LTDataType x)  //查找后返回指针，如果找到返回找的到的结构体指针，没有找到返回空指针
{
    assert(phead);
    LTNode* cur=phead->next;  //定义一个结构体指针进行遍历寻找
    while(cur!=phead)
    {
        if(cur->data==x)
        {
            return cur;  //找到后返回的指针
        }
        cur=cur->next;  
    }
    return NULL;
}
void ListInsert(LTNode*pos,LTDataType x)
{
    assert(pos); //保证传入的pos位不是空指针
    LTNode*prev=pos->prev; //找到pos位的前一位
    LTNode*newnode=BuyListNode(x);  //定义一个新节点进行插入
    pos->prev=newnode;
    newnode->next=pos;
    prev->next=newnode;
    newnode->prev=prev;
}
void ListErase(LTNode*pos)
{
    LTNode*prev=pos->prev;//找到pos位的前一个
    LTNode*next=pos->next; //找到pos的后一个
    prev->next=next;
    next->prev=prev;
    free(pos);  //释放pos
}
void ListDestroy(LTNode*phead)
{
    LTNode*cur=phead->next; //定义一个结构体指针进行遍历销毁
    while(cur!=phead)
    {
        LTNode*next=cur->next;
        free(cur);
        cur=next;
    }
    free(phead); //最后释放头节点
}

💚4.3Test.c

#include "List.hpp"
void test1()
{
    LTNode* plist=ListInit();
    ListPushBack(plist,1);
    ListPushBack(plist,2);
    ListPushBack(plist,3);
    ListPushBack(plist,4);
    ListPushBack(plist,5);
    ListPopBack(plist);
    ListPopBack(plist);
    ListNodePrint(plist);
    ListDestroy(plist);
    plist=NULL;
}
void test2()
{
    LTNode* plist=ListInit();
    ListPushFront(plist,1);
    ListPushFront(plist,2);
    ListPushFront(plist,3);
    ListPushFront(plist,4);
    ListPushFront(plist,5);
    ListPopFront(plist);
    ListPopFront(plist);
    size_t ret=ListSize(plist);
    printf("%zu\n",ret);
    ListNodePrint(plist);
    
}
int main()
{
    test1();
    test2();
    return 0;
}

总结：

     对于带头双向循环链表的实现我还是那句话，不要害怕！！！他只是结构体比较复杂，但是代码实现它确比较容易的，它不像顺序表那样要考虑是否要扩容，也不需要像单链表那样要考虑传入是否为空指针，所以他的实现还是比较容易的，而本文对于他的所有实现，我想小马应该写的很详细啦，如果有不懂的可以私信问我或者直接在评论区中问我啦！！

       再者，其实思考一下，双向循环链表pos插入删除时，当我们pos等于phead时，你会发现他就像尾插和尾删，发现就不需要我们写的那么复杂啦，只需要调用一下pos函数，使pos指向phead就行啦，这里我给大家讲一个思路，对于他的实现，大家下去可以尝试一下

  最后的最后，小马码文不易，如果觉得文章有帮助的话，就多多支持小马啦！！！！

相关文章：

  • 【数据结构】栈和队列
  • 硬核Vue3响应式原理解析，为你保驾护航渡过寒冬
  • 轻松掌握 jQuery 基础
  • Python每日一练 03
  • 【计算机毕业设计】Springboot医疗管理系统源码
  • 【2022硬件设计开源盛宴】一年一度的hackaday大赛结束，冠军便携式风力涡轮机，共提交326个电子作品，奖金池15万美元
  • 基于51单片机的智能路灯控制系统proteus仿真原理图PCB
  • 四、ref与DOM-findDomNode-unmountComponentAtNode
  • synchronized关键字
  • StarRocks从入门到精通系列五：导入数据
  • 做了8年前端，细说那些曾经让你浴霸不能的后端
  • 你安全吗？丨秦淮到底是哪种黑客？你猜对了吗？
  • Android App开发中使用Glide加载网络图片讲解及实战（附源码 简单易懂）
  • mysql的监控大屏
  • 【node进阶】深入浅出websocket即时通讯(二)-实现简易的群聊私聊
  • 解决storybook中组件的tailwindcss类不生效问题
  • 零基础学FPGA（六）：FPGA时钟架构（Xilinx为例，完整解读）
  • python--敲击木鱼积累功德小项目（更新版（2））
  • 真趣科技：多业务形态的企业需要灵活可配置的CRM系统
  • 力扣206 - 反转链表【校招面试高频考题】