0
0

手撕双链表

作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
座右铭：松树千年终是朽，槿花一日自为荣。
望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言

    前面我们已经学习了顺序表和单链表，顺序表可以存储动态的数据，但是一旦元素过少，而又要开辟空间，这样就造成空间的浪费，而单链表以节点为单位存储，不支持随机访问，只能从头到尾遍历访问，为了解决上面两个问题，人们发现了双链表，把一个一个元素以链子的形式存储，可以存储相互的地址，那双链表如何实现呢，今天咱们就实现一下--《双链表》。

🌙主体

咱们从三个方面实现双链表，动态管理，头插头删尾插尾删，增删查改。

在程序中为了实现双链表，需要创建头文件List.h ，创建源文件Test.c，List.c。

🌠动态管理

💤初始化动态双链表

既然实现双链表，初始化动态的双链表必不可少，从两个方面实现初始化动态的双链表。

1.首先我们在List.h定义动态的双链表，省得我们再定义节点（双链表）。

//定义数据类型
typedef int LTDataType;
//定义双链表初始化
typedef struct ListNode
{
    //上一个
    struct ListNode* next;
    //下一个
    struct ListNode* prev;
    LTDataType data;
}LTNode;

2.对双链表进行初始化

我们要明白，这里不像单链表一样，形成节点就行，还需要初始化。

💦这里采用malloc开辟空间

💦采用预指令判断空间是否开辟完成（没有开辟空间返回-1）

💦之后就是简单的初始数据

💦记得返回值

//初始化
LTNode* BuyLTNode(LTDataType x)
{
    //开辟空间
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    //判断开辟的空间是否为空
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    //初始化
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

//形成双链表
LTNode* LTInit()
{
    //使头为0
    LTNode* phead = BuyLTNode(0);
    //构成循环
    phead->next = phead;
    phead->prev = phead;

    return phead;
}

💤释放双链表内存

双链表的内存释放与单链表的内存释放有一定的区别，这里我们分开两类，清理与销毁

清理的代码如下：

//清理
void ListClear(LTNode* phead)
{
    //断言
    assert(phead);
    
    //清理全部数据，保留头结点
    LTNode* cur = phead->next;
    
    //循环销毁
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
}

销毁的代码如下：

//销毁
void ListDestory(LTNode** pphead)
{
    //断言
    assert(*pphead);

    //调用清理（函数）
    ListClear(*pphead);
    
    //释放内存
    free(*pphead);
    *pphead = NULL;
}

🌠头插头删尾插尾删

💤打印元素

打印元素就太简单了，直接上代码

//打印数据
void LTPrint(LTNode* phead)
{
    //断言
    assert(phead);

    printf("phead<=>");
    
    LTNode* cur = phead->next;
    //注意循环的结束的语句
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    
    printf("\n");
}

💤尾插（重点）

有了这个图就对指向的改变就轻轻松松

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x)
{
    //断言
    assert(phead);

    LTNode* tail = phead->prev;
    
    //给添加的元素创建节点
    LTNode* newnode = BuyLTNode(x);

    //新开辟的元素下一个节点指向尾
    newnode->prev = tail;
    //尾的上一个节点指向新的元素
    tail->next = newnode;

    //新元素的上一个节点指向头
    newnode->next = phead;
    //头的下一节点指向新的元素节点
    phead->prev = newnode;

    //本质上与尾插相似 （双向链表在pos的前面进行插入）
    //LTInsert(phead, x);
}

💤尾删（重点）

双链表重在画图，希望小伙伴们能看得懂。

//尾删
void LTPopBack(LTNode* phead)
{
    //断言
    assert(phead);
    //防止没有头指向没有元素
    assert(phead->next != phead);

    //找到尾
    LTNode* tail = phead->prev;
    //找到尾前面一个元素
    LTNode* tailPrev = tail->prev;
    
    //释放内存
    free(tail);

    //（把尾的上一个元素）的上一个指针 指向头
    tailPrev->next = phead;
    //头的下一个指针指向尾的前一个元素
    phead->prev = tailPrev;

    // 双向链表删除pos位置的结点(本质上与尾删相似)
    //LTErase(phead->prev);
}

💤头插（重点）

博主在这里采用三种方法，希望大家至少学会一种

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);

    //方法一
    //初始化
    //LTNode* newnode = BuyLTNode(x);
    //newnode->next = phead->next;
    //phead->next->prev = newnode;
    //phead->next = newnode;
    //newnode->prev = phead;

    //方法二
    //初始化
    LTNode* newnode = BuyLTNode(x);
    LTNode* first = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;

    //方法三
    // 双向链表删除pos位置的结点(本质上就是头插)
    //LTInsert(phead->next, x);
}

💤头删（重点）

双链表会自带梢兵位（这个到后期博主会讲）

//头删（重点）
void LTPopFront(LTNode* phead)
{
    //断言
    assert(phead);
    //头指向不能为空
    assert(phead->next != phead);

    //找到梢兵位的节点
    LTNode* first = phead->next;
    //找到头后面一个元素
    LTNode* second = first->next;

    //释放内存
    free(first);

    //梢兵位的节点指向头后面一个元素
    phead->next = second;
    //后面一个元素指向梢兵位的节点
    second->prev = phead;

    //双向链表删除pos位置的结点(本质上和头删一样)
    //LTErase(phead->next);
}

🌠增删查改

💤统计双链表元素个数

这个函数还是比较简单的，注意循环的停止条件。

//统计双链表元素个数
int LTSize(LTNode* phead)
{
    //断言
    assert(phead);

    int size = 0;
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        ++size;
        cur = cur->next;
    }

    return size;
}

💤双向链表在pos的前面进行插入

这里大家就看图理解就行啦

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
    //断言
    assert(pos);

    LTNode* posPrev = pos->prev;
    //为插入的元素开辟空间
    LTNode* newnode = BuyLTNode(x);

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

💤双向链表删除pos位置的结点

这里大家就看图理解就行啦

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
    //断言
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    //释放内存
    free(pos);

    posPrev->next = posNext;
    posNext->prev = posPrev;
}

🌙代码总结

🌠主函数

//包含文件
#include"List.h"

void TestList1()
{
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPushBack(plist, 5);
    LTPrint(plist);

    LTPushFront(plist, 10);
    LTPushBack(plist, 10);

    LTPrint(plist);
}

void TestList2()
{
    LTNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPushBack(plist, 5);
    LTPrint(plist);

    LTPopBack(plist);
    //LTPopFront(plist);
    LTPrint(plist);

    //LTPopFront(plist);
    //LTPopFront(plist);
    //LTPopFront(plist);
    //LTPopFront(plist);
    LTPrint(plist);
}

//void TestList3()
//{
//    LTNode* plist = LTInit();
//    LTPushBack(plist, 1);
//    LTPushBack(plist, 2);
//    LTPushBack(plist, 3);
//    LTPushBack(plist, 4);
//    LTPushBack(plist, 5);
//    LTPrint(plist);
//
//    LTPushFront(plist, 10);
//    LTPushFront(plist, 20);
//    LTPushFront(plist, 30);
//    LTPushFront(plist, 40);
//    LTPrint(plist);
//}
//
//void TestList4()
//{
//    LTNode* plist = LTInit();
//    LTPushBack(plist, 1);
//    LTPushBack(plist, 2);
//    LTPushBack(plist, 3);
//    LTPushBack(plist, 4);
//    LTPushBack(plist, 5);
//    LTPrint(plist);
//
//    LTPopFront(plist);
//    LTPrint(plist);
//
//    LTPopBack(plist);
//    LTPrint(plist);
//}

int main()
{
    TestList1();

    return 0;
}

🌠List.h头文件

//包含头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

//定义数据类型
typedef int LTDataType;
//定义双链表初始化
typedef struct ListNode
{
    //上一个
    struct ListNode* next;
    //下一个
    struct ListNode* prev;
    LTDataType data;
}LTNode;

//初始化
LTNode* BuyLTNode(LTDataType x);

//形成双链表
LTNode* LTInit();

//打印数据
void LTPrint(LTNode* phead);

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x);
//尾删（重点）
void LTPopBack(LTNode* phead);
//头插（重点）
void LTPushFront(LTNode* phead, LTDataType x);
//头删（重点）
void LTPopFront(LTNode* phead);

//统计双链表元素个数
int LTSize(LTNode* phead);
// 双向链表查找（在双链表中不合适）
LTNode* LTFind(LTNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);

//清理
void ListClear(LTNode* phead);
//销毁
void ListDestory(LTNode** pphead);

🌠List.c源文件


//包含文件
#include"List.h"

//初始化
LTNode* BuyLTNode(LTDataType x)
{
    //开辟空间
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    //判断开辟的空间是否为空
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    //初始化
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

//形成双链表
LTNode* LTInit()
{
    //使头为0
    LTNode* phead = BuyLTNode(0);
    //构成循环
    phead->next = phead;
    phead->prev = phead;

    return phead;
}

//打印数据
void LTPrint(LTNode* phead)
{
    //断言
    assert(phead);

    printf("phead<=>");
    
    LTNode* cur = phead->next;
    //注意循环的结束的语句
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
    
    printf("\n");
}

//尾插（重点）
void LTPushBack(LTNode* phead, LTDataType x)
{
    //断言
    assert(phead);

    LTNode* tail = phead->prev;

    //给添加的元素创建节点
    LTNode* newnode = BuyLTNode(x);

    //新开辟的元素下一个节点指向尾
    newnode->prev = tail;
    //尾的上一个节点指向新的元素
    tail->next = newnode;

    //新元素的上一个节点指向头
    newnode->next = phead;
    //头的下一节点指向新的元素节点
    phead->prev = newnode;

    //本质上与尾插相似 （双向链表在pos的前面进行插入）
    //LTInsert(phead, x);
}

//尾删
void LTPopBack(LTNode* phead)
{
    //断言
    assert(phead);
    //防止没有头指向没有元素
    assert(phead->next != phead);

    //找到尾
    LTNode* tail = phead->prev;
    //找到尾前面一个元素
    LTNode* tailPrev = tail->prev;
    
    //释放内存
    free(tail);

    //（把尾的上一个元素）的上一个指针 指向头
    tailPrev->next = phead;
    //头的下一个指针指向尾的前一个元素
    phead->prev = tailPrev;

    // 双向链表删除pos位置的结点(本质上与尾删相似)
    //LTErase(phead->prev);
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);

    //方法一
    //初始化
    //LTNode* newnode = BuyLTNode(x);
    //newnode->next = phead->next;
    //phead->next->prev = newnode;
    //phead->next = newnode;
    //newnode->prev = phead;

    //方法二
    //初始化
    LTNode* newnode = BuyLTNode(x);
    LTNode* first = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;

    //方法三
    // 双向链表删除pos位置的结点(本质上就是头插)
    //LTInsert(phead->next, x);
}

//头删（重点）
void LTPopFront(LTNode* phead)
{
    //断言
    assert(phead);
    //头指向不能为空
    assert(phead->next != phead);

    //找到梢兵位的节点
    LTNode* first = phead->next;
    //找到头后面一个元素
    LTNode* second = first->next;

    //释放内存
    free(first);

    //梢兵位的节点指向头后面一个元素
    phead->next = second;
    //后面一个元素指向梢兵位的节点
    second->prev = phead;

    //双向链表删除pos位置的结点(本质上和头删一样)
    //LTErase(phead->next);
}

//统计双链表元素个数
int LTSize(LTNode* phead)
{
    //断言
    assert(phead);

    int size = 0;
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        ++size;
        cur = cur->next;
    }

    return size;
}

// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
    //断言
    assert(pos);

    LTNode* posPrev = pos->prev;
    //为插入的元素开辟空间
    LTNode* newnode = BuyLTNode(x);

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

// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
    //断言
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    //释放内存
    free(pos);

    posPrev->next = posNext;
    posNext->prev = posPrev;
}

//清理
void ListClear(LTNode* phead)
{
    //断言
    assert(phead);
    
    //清理全部数据，保留头结点
    LTNode* cur = phead->next;
    
    //循环销毁
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
}

//销毁
void ListDestory(LTNode** pphead)
{
    //断言
    assert(*pphead);

    //调用清理（函数）
    ListClear(*pphead);
    
    //释放内存
    free(*pphead);
    *pphead = NULL;
}

🌟结束语

   今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

标签： 数据结构
本文转载自: https://blog.csdn.net/AAlykk/article/details/132776974
版权归原作者 დ旧言~ 所有， 如有侵权，请联系我们删除。
登录后发布评论

“手撕双链表”的评论:

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

泷羽sec-星光不负a-学习打卡-安全见闻(1)

Linux 经典面试八股文

docker 拉取MySQL8.0镜像以及安装

【PowerShell】如何使用Pester进行单元测试？

PyCharm中TensorFlow安装指南及.whl文件使用

移动UI：意见反馈设计的8大要点，让用户和产品畅快沟通。

git | 删除指定 commit

文章导航