0
0

学习笔记---更进一步的双向链表专题~~

1. 双向链表的结构🦊

这里的双向链表，准确的说是：带头双向循环链表

这里的“头节点”指的是“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨

的”。

“哨兵位”存在的意义：****遍历循环链表避免死循环。

注意⚠️

双向链表的每一个节点存储一个有效数据+下一个节点的地址+上一个节点的地址

头节点和尾节点有些特殊：头节点指向的上一个节点的地址是尾节点，尾节点指向的下一个节点的地址是头节点

2. 实现双向链表🐝

2.1 要实现的目标🎯

我们需要多个接口帮助我们实现：创建、一系列具体操作、销毁

具体操作包括：头部/尾部插入数据、头部/尾部删除数据、打印出双向链表、指定节点之后插入数据、删除指定节点的数据、查找指定节点

2.2 创建+初始化🦋

2.2.1 List.h

#include<assert.h>
#include<string.h>
#include<stdbool.h>

typedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {
    LTDataType data;
    struct ListNode* prev;
    struct ListNode* next;
}ListNode;

//初始化
ListNode* LTInit();//不用传入参数，直接调用接口返回一个头节点

2.2.2 List.c

#include"List.h"
//初始化
ListNode* LTInit()//不用传入参数，直接调用接口返回一个头节点
{
    //为头节点申请空间
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    //判断开辟是否成功
    if (phead == NULL)
    {
        perror("malloc error!\n");
        return;
    }
    //开辟成功--->初始化头节点
    phead->data = -1;//头节点不存储有效数据，可以任意赋值
    //只有哨兵位的时候，要实现双向链表，不能指向NULL，否则无法双向循环，所以我们指向自己
    phead->prev = phead->next = phead;
    return phead;
}

2.2.3 test.c

#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
}
int main()
{
    ListTest();
    return 0;
}

2.2.4 代码测试运行

2.3 尾插+打印+头插🪼

思路分析

2.3.1 List.h

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);

//打印
void LTPrint(ListNode* phead);

//头插
void LTPushFront(ListNode* phead, LTDataType x);

2.3.2 List.c

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
// 只改变数据，不改变地址

//开辟空间
ListNode* ListBuyNode(LTDataType x)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        perror("malloc error!\n");
        return;
    }
    node->data = x;
    node->next = node->prev = NULL;
    return node;
}

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);//注意哨兵位不能为空
    //申请空间
    ListNode* node = ListBuyNode(x);
    //先处理node的前驱指针和后继指针
    node->prev = phead->prev;
    node->next = phead;
    //再处理之前的尾节点和phead
    phead->prev->next = node;
    phead->prev = node;
}

//打印
void LTPrint(ListNode* phead)
{
    //哨兵位不能改变
    ListNode* cur = phead->next;
    while (cur != phead)//当cur再次指向phead的时候，循环结束
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);//注意哨兵位不能为空
    //申请空间
    ListNode* node = ListBuyNode(x);
    //node插入头节点之后才算头插
    //先处理node的前驱指针和后继指针
    node->prev = phead;
    node->next = phead->next;
    //再处理phead和phead->next
    phead->next->prev = node;
    phead->next = node;
}

2.3.3 test.c

#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    LTPushFront(plist, 5);
    LTPrint(plist);//5 1 2 3 4 
}
int main()
{
    ListTest();
    return 0;
}

2.3.4 代码测试运行

2.4 尾删+头删🐊

2.4.0 思路分析

2.4.1 List.h

//尾删
void LTPopBack(ListNode* phead);

//头删
void LTPopFront(ListNode* phead);

2.4.2 List.c

//尾删
void LTPopBack(ListNode* phead)
{
    //不能为空链表，只有一个哨兵位不能尾删
    assert(phead&&(phead->prev!=phead||phead->next!=phead));
    ListNode* del = phead->prev;//phead->prev就是尾节点
    //先处理del
    del->prev->next = phead;
    //再处理phead
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

//头删
void LTPopFront(ListNode* phead)
{
    //不能为空链表，只有一个哨兵位不能头删
    assert(phead && (phead->prev != phead || phead->next != phead));
    ListNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

2.4.3 test.c

#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    LTPushFront(plist, 5);
    LTPrint(plist);//5 1 2 3 4 
    LTPopBack(plist);
    LTPrint(plist);//5 1 2 3
    LTPopFront(plist);
    LTPrint(plist);//1 2 3
}
int main()
{
    ListTest();
    return 0;
}

2.4.4 代码测试运行

2.5 查找数据+pos节点后插入+删除pos节点🦩

2.5.0 思路分析

2.5.1 List.h

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);

//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);

//删除pos节点
void LTErase(ListNode* pos);

2.5.2 List.c

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur!= phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* node = ListBuyNode(x);
    //node
    node->next = pos->next;
    node->prev = pos;
    //pos
    pos->next = node;
    node->next->prev = node;
}

//删除pos节点
void LTErase(ListNode* pos)
{
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

2.5.3 test.c

#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    LTPushFront(plist, 5);
    LTPrint(plist);//5 1 2 3 4 
    LTPopBack(plist);
    LTPrint(plist);//5 1 2 3
    LTPopFront(plist);
    LTPrint(plist);//1 2 3
    ListNode* find = LTFind(plist, 1);
    /*LTPushAfter(find, 4);*/    
    //LTPrint(plist);//1 4 2 3
    LTErase(find);
    LTPrint(plist);//2 3

}
int main()
{
    ListTest();
    return 0;
}

2.5.4 代码测试运行

2.6 销毁☄️

2.6.0思路分析

一开始的初始化，我们直接调用了接口，返回头节点进行初始化。我们没有考虑一级指针还是二级指针的问题。

那么，最后的销毁又该怎么办？是一级指针？还是二级指针？下面我们一一来尝试

1. 一级指针

2.6.1 List.h
//销毁
void LTDestroy(ListNode* phead);
2.6.2 List.c
//销毁
void LTDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while(cur!=phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    //注意哨兵位还没有释放
    free(phead);
    phead = NULL;
}
2.6.3 test.c
#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    //LTPushFront(plist, 5);
    //LTPrint(plist);//5 1 2 3 4 
    //LTPopBack(plist);
    //LTPrint(plist);//5 1 2 3
    //LTPopFront(plist);
    //LTPrint(plist);//1 2 3
    //ListNode* find = LTFind(plist, 1);
    /*LTPushAfter(find, 4);*/    
    LTPrint(plist);//1 4 2 3
    //LTErase(find);
    //LTPrint(plist);//2 3
    LTDestroy(plist);

}
int main()
{
    ListTest();
    return 0;
}
2.6.4 代码测试运行

一级指针：
phead的改变不影响plist，phead释放之后，plist指向已经释放掉的空间——>把plist置为空

那么置为空之前，还要不要将plist指向的空间再free一次？

我们尝试一下

那么再思考一下：一级指针是会导致phead的改变不影响plist，那么plist是什么没有改变？是指plist保存的值没有被改变还是plist的这块空间的地址没有被释放？

这里报错指的是plist指向无效地址

注意⚠️
如果plist的地址没有被释放，那么直接free（plist）是不会报错的

所以在一级指针的情况下：plist的地址已经被释放了，没有被置为空的可以理解是plist的地址名称

2.6.5 一级指针的改进---test.c

2. 二级指针

2.6.1 List.h
//销毁
//void LTDestroy(ListNode* phead);
void LTDestroy(ListNode** phead);
2.6.2 List.c
//销毁
void LTDestroy(ListNode** phead)
{
    assert(phead && *phead);
    ListNode* cur = (*phead)->next;
    while (cur != *phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(*phead);
    *phead = NULL;
}
2.6.3 test.c
#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    //LTPushFront(plist, 5);
    //LTPrint(plist);//5 1 2 3 4 
    //LTPopBack(plist);
    //LTPrint(plist);//5 1 2 3
    //LTPopFront(plist);
    //LTPrint(plist);//1 2 3
    //ListNode* find = LTFind(plist, 1);
    ///*LTPushAfter(find, 4);*/    
    LTPrint(plist);//1 4 2 3
    //LTErase(find);
    //LTPrint(plist);//2 3
    //LTDestroy(plist);
    //plist = NULL;
    LTDestroy(&plist);
}
int main()
{
    ListTest();
    return 0;
}
2.6.4 代码测试运行

虽然，二级指针不用手动将plist置为空
但是，更推荐一级指针，因为其他接口基本上都是一级指针——>保持接口的一致性

2.7 完整代码💦

2.7.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>

typedef int LTDataType;
//创建双向链表的结构体
typedef struct ListNode {
    LTDataType data;
    struct ListNode* prev;
    struct ListNode* next;
}ListNode;

//初始化
ListNode* LTInit();//不用传入参数，直接调用接口返回一个头节点

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
//尾插
void LTPushBack(ListNode* phead, LTDataType x);

//打印
void LTPrint(ListNode* phead);

//头插
void LTPushFront(ListNode* phead, LTDataType x);

//尾删
void LTPopBack(ListNode* phead);

//头删
void LTPopFront(ListNode* phead);

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x);

//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x);

//删除pos节点
void LTErase(ListNode* pos);

//销毁
void LTDestroy(ListNode* phead);

2.7.2 List.c

#include"List.h"
//初始化
ListNode* LTInit()//不用传入参数，直接调用接口返回一个头节点
{
    //为头节点申请空间
    ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    //判断开辟是否成功
    if (phead == NULL)
    {
        perror("malloc error!\n");
        return;
    }
    //开辟成功--->初始化头节点
    phead->data = -1;//头节点不存储有效数据，可以任意赋值
    //只有哨兵位的时候，要实现双向链表，不能指向NULL，否则无法双向循环，所以我们指向自己
    phead->prev = phead->next = phead;
    return phead;
}

//在双向链表中不会改变哨兵位，所以这里都可以传一级指针
// 只改变数据，不改变地址

//开辟空间
ListNode* ListBuyNode(LTDataType x)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        perror("malloc error!\n");
        return;
    }
    node->data = x;
    node->next = node->prev = NULL;
    return node;
}

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);//注意哨兵位不能为空
    //申请空间
    ListNode* node = ListBuyNode(x);
    //先处理node的前驱指针和后继指针
    node->prev = phead->prev;
    node->next = phead;
    //再处理之前的尾节点和phead
    phead->prev->next = node;
    phead->prev = node;
}

//打印
void LTPrint(ListNode* phead)
{
    //哨兵位不能改变
    ListNode* cur = phead->next;
    while (cur != phead)//当cur再次指向phead的时候，循环结束
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

//头插
void LTPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);//注意哨兵位不能为空
    //申请空间
    ListNode* node = ListBuyNode(x);
    //node插入头节点之后才算头插
    //先处理node的前驱指针和后继指针
    node->prev = phead;
    node->next = phead->next;
    //再处理phead和phead->next
    phead->next->prev = node;
    phead->next = node;
}

//尾删
void LTPopBack(ListNode* phead)
{
    //不能为空链表，只有一个哨兵位不能尾删
    assert(phead&&(phead->prev!=phead||phead->next!=phead));
    ListNode* del = phead->prev;//phead->prev就是尾节点
    //先处理del
    del->prev->next = phead;
    //再处理phead
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

//头删
void LTPopFront(ListNode* phead)
{
    //不能为空链表，只有一个哨兵位不能头删
    assert(phead && (phead->prev != phead || phead->next != phead));
    ListNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

//查找数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//pos节点之后插入
void LTPushAfter(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* node = ListBuyNode(x);
    //node
    node->next = pos->next;
    node->prev = pos;
    //pos
    pos->next = node;
    node->next->prev = node;
}

//删除pos节点
void LTErase(ListNode* pos)
{
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

//销毁
void LTDestroy(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while(cur!=phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    //注意哨兵位还没有释放
    free(phead);
    phead = NULL;
}

2.7.3 test.c

#include"List.h"
void ListTest()
{
    ListNode* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPrint(plist);//1 2 3 4 
    LTPushFront(plist, 5);
    LTPrint(plist);//5 1 2 3 4 
    LTPopBack(plist);
    LTPrint(plist);//5 1 2 3
    LTPopFront(plist);
    LTPrint(plist);//1 2 3
    ListNode* find = LTFind(plist, 1);
    /*LTPushAfter(find, 4);*/    
    //LTPrint(plist);//1 4 2 3
    LTErase(find);
    LTPrint(plist);//2 3
    LTDestroy(plist);
    plist = NULL;
}
int main()
{
    ListTest();
    return 0;
}

3. 顺序表和双向链表的分析🍻

不同点顺序表链表（单链表）存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持O（1）不支持：O（N）任意位置插入或者删除元素看你需要搬移元素，效率低O（N）只需要改变指针指向插入动态顺序表，空间不够的时候需要扩容没有容量的概念应用场景元素高效存储+频繁访问任意位置插入和删除频繁

本次的分享到这里就结束了！！！

PS：小江目前只是个新手小白。欢迎大家在评论区讨论哦！有问题也可以讨论的！

如果对你有帮助的话，记得点****赞👍+收藏⭐️+关注➕

标签： 笔记 链表 双向链表
本文转载自: https://blog.csdn.net/2301_79184587/article/details/134088077
版权归原作者 小江同学～12345 所有， 如有侵权，请联系我们删除。
登录后发布评论

“学习笔记---更进一步的双向链表专题~~”的评论:

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

ISO26262功能安全核心思想及芯片安全设计实例

gitLab配置ssh

iStore实现 SmartDNS + AdGuard Home IP优选+广告屏蔽

Kestra 开源项目实战指南

SpringBoot（9）-Dubbo+Zookeeper

docker镜像源

ray集群部署vllm的折磨

文章导航