【数据结构】速速收藏，一文带你参透双向链表各接口实现

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

目录

🥕前言🥕

🌽一、双向链表概述🌽

1.双向链表概念

2.双向链表结构

🍆二、双向链表接口实现🍆

1.工程文件建立

2.接口实现本文重点

Ⅰ.双向链表初始化

Ⅱ.打印双向链表

Ⅲ.申请新节点

Ⅳ.双向链表尾插

Ⅴ.双向链表尾删

Ⅵ.双向链表头插

Ⅶ.双向链表头删

Ⅷ.双向链表查找

Ⅸ.双向链表给定节点前插

Ⅹ.双向链表给定节点后插

ⅩⅠ.双向链表删除给定节点

ⅩⅡ.双向链表销毁

🍄三、完整接口实现代码🍄

1.List.h

2.List.c

3.test.c

🌶️四、顺序表与链表对比🌶️

1.两者差异

2.存储器层次结构辅图

🥬总结🥬

🛰️博客主页✈️銮同学的干货分享基地

🛰️欢迎关注👍点赞🙌收藏✍️留言

🛰️系列专栏🎈 数据结构

                       🎈【进阶】C语言学习

                       🎈  C语言学习

🛰️代码仓库🎉数据结构仓库

                       🎉VS2022_C语言仓库

        家人们更新不易你们的👍点赞👍和⭐关注⭐真的对我真重要各位路过的友友麻烦多多点赞关注欢迎你们的私信提问感谢你们的转发

        关注我关注我关注我你们将会看到更多的优质内容

🏡🏡 本文重点 🏡🏡

🚅 双向链表 🚃 顺序表与链表对比 🚏🚏

🥕前言🥕

        上节课中我们完整的实现了无头单向链表的各个功能接口但是我们也注意到由于单向链表只保存指向下一节点的指针于是我们在进行前插等操作时还需要遍历链表来找到前一个节点效率不高且步骤繁琐。于是为了克服类似这样的问题我们更多的会使用另一种数据结构即带头双向循环链表本文就将带领各位小伙伴们一起实现带头双向循环链表的各接口功能。

🌽一、双向链表概述🌽

1.双向链表概念

        双向链表也叫双链表是链表的一种它的每个数据节点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

        并且在上节课中我们就说过

  • 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。
  • 带头双向循环链表结构最复杂一般用在单独存储数据。虽然它结构复杂但在实际使用中使用代码实现后优秀的结构会带来很多优势实现反而更加简单。并且在我们的实际中所使用的链表数据结构一般都是带头双向循环链表。

         所以今天我们就主要研究带头双向循环链表的各个接口功能的实现。

2.双向链表结构

🍆二、双向链表接口实现🍆

1.工程文件建立

        我们仍使用模块化开发格式使用 List.h 、List.c 、test.c 三个文件进行代码书写

  • List.h存放函数声明、包含其他头文件、定义宏。
  • List.c书写函数定义书写函数实现。
  • test.c书写程序整体执行逻辑。

        这其中我们的接口实现主要研究的是函数实现文件 List.c 中的内容对 test.c 文件中的内容分不关心。

2.接口实现本文重点

        这里是本文重点中的重点即 List.c 文件中的接口具体实现

Ⅰ.双向链表初始化

  • 双向链表初始化
  • 动态申请首节点并使两个指向直接前置节点与直接后继节点的指针均指向自己形成循环结构。
  • 最后返回初始化完成的头节点。
LNode* LInit()
{
	//哨兵位头节点
	LNode* phead = (LNode*)molloc(sizeof(LNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

Ⅱ.打印双向链表

  • 执行操作前需对传入指针进行非空判断防止对空指针进行操作。 
  • 双向链表的打印方式与单链表相似采用方式均为由头节点开始通过节点指针指向寻找下一节点的方式循环进行遍历打印。
  • 不同点是由于双向循环链表首尾相连形成闭环因此终止循环打印条件将不再是执行至空指针而是执行回到头节点即完成整个循环。
void LPrint(LNode* phead)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

Ⅲ.申请新节点

  • 新节点的申请与单链表基本相同动态申请新节点后再对新节点进行操作。
  • 不同点是双向链表多出一个指向直接前驱节点的指针因此该指针也需要在使用前进行置空操作防止造成野指针错误。
LNode* BuyListNode(LDataType x)
{
    LNode* newnode = (LNode*)malloc(sizeof(LNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

Ⅳ.双向链表尾插

  • 执行操作前应当进行非空判断防止传入空指针。
  • 在进行尾插操作前应当首先找到尾节点采用的方式是通过双向循环链表中头节点的前驱指针指向来找到尾节点。
  • 接着动态申请新节点。
  • 最后执行尾插操作。首先使前面找到的尾节点的后继指针指向新节点并使新节点的前驱指针也指向尾节点接着使头节点的前驱指针指向新节点并使新节点的后继指针指向头节点。
void LPushBack(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* tail = phead->prev;    //找到尾节点
    LNode* newnode = BuyListNode(x);
    //新尾互指
    tail->next = newnode;
    newnode->prev = tail;
    //新头互指
    phead->prev = newnode;
    newnode->next = phead;
}
  • 测试尾插接口功能实现

Ⅴ.双向链表尾删

  • 在双向链表进行尾删时不仅要防止传入空指针同时也要注意避免链表为空只含有哨兵节点的情况发生。
  • 首先找到尾节点及尾节点的前驱节点接着使该前驱节点与头节点跳过尾节点互指最后释放原尾节点并置空即可。
void LPopBack(LNode* phead)
{
    if ((phead == NULL) || (phead->next == phead))    //排除为空的情况
    {
        return;
    }
    LNode* tail = phead->prev;    //找到尾
    LNode* tailprev = tail->prev;    //找到尾的前驱
    tailprev->next = phead;    //尾前驱节点的后继指针指向头
    phead->prev = tail->prev;  //头的前驱指针指向尾的前驱
    free(tail);
    tail = NULL;
}
  • 测试尾删接口功能实现

Ⅵ.双向链表头插

  • 在执行操作前应当对传入指针进行判断防止传入空指针。
  • 在改变指向前应当首先保存哨兵节点的后继节点因为当我们插入新节点后链表结构将会发生改变再想要找到该节点将变得麻烦。
  • 进行插入操作时使哨兵节点的后继指针指向新节点再使新节点的前驱指针指向哨兵节点接着使用同样的操作使新节点与哨兵节点的原后继节点互指。
void LPushFront(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* newnode = BuyListNode(x);
    LNode* next = phead->next;    //保存哨兵节点的后继节点
    phead->next = newnode;    //哨兵点的后继指针指向新节点
    newnode->prev = phead;    //新节点的前驱指针指向哨兵节点
    newnode->next = next;    //新节点的后继指针指向哨兵节点的原后继节点
    next->prev = newnode;    //哨兵节点的原后继节点前驱指针指向新节点
}
  • 测试头插接口功能实现

Ⅶ.双向链表头删

  • 首先进行非空判断并排除链表为空只含有哨兵节点的情况。
  • 开始进行头删操作前找到并保存头节点防止改变指向后链表结构发生变化难以找到原本的头节点以便于最后进行释放。
  • 并且应当找到并保存原头节点的后继节点防止防止改变指向后链表结构发生变化而难以找到。
  • 具体操作便是使哨兵节点与头节点的后继节点跳过头节点互指再将要删除的头节点释放并置空即可。
void LPopFront(LNode* phead)
{
    if ((phead == NULL) || (phead->next == phead))    //排除为空的情况
    {
        return;
    }
    LNode* next = phead->next;    //保存头节点便于释放
    LNode* nextNext = next->next;    //保存头节点的后继节点
    phead->next = nextNext;
    nextNext->prev = phead;
    free(next);
    next = NULL;
}
  • 测试头删接口功能实现

Ⅷ.双向链表查找

  • 执行操作前需进行非空判断防止对空指针进行操作。
  • 查找逻辑很简单遍历整个链表直至链表完整循环一遍若比对存在匹配元素返回该节点否则返回空。
LNode* LFind(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}
  • 测试查找接口功能实现

Ⅸ.双向链表给定节点前插

  • 执行操作前需进行非空判断防止对空指针进行操作。
  • 执行逻辑很简单将数据存入通过动态申请的来的新节点中后找到目标节点使目标节点的前驱节点与新节点互指再使新节点与目标节点互指接即可。
void LInsert(LNode* pos, LDataType x)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->prev;
    LNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}
  • 测试前插接口功能实现

Ⅹ.双向链表给定节点后插

  • 执行操作前需进行非空判断防止对空指针进行操作。
  • 执行逻辑与前插高度类似不同的是使目标节点的后继节点与新节点互指再使新节点与目标节点互指。
void LInsertBack(LNode* pos, LDataType x)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->next;
    LNode* newnode = BuyListNode(x);
    posPrev->prev = newnode;
    newnode->next = posPrev;
    newnode->prev = pos;
    pos->next = newnode;
}
  • 测试后插接口功能实现

ⅩⅠ.双向链表删除给定节点

  • 执行操作前需进行非空判断防止操作空指针。
void LErase(LNode* pos)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->prev;
    LNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
    pos = NULL;
}
  • 测试删除接口功能实现

ⅩⅡ.双向链表销毁

  • 若哨兵节点为空即表示链表内没有有效数据节点则无需进行销毁、释放与置空操作。
  • 含有有效节点则遍历所有节点将每一个节点均进行释放特别注意所有数据节点释放完毕之后不要忘记释放哨兵节点。
void LDestroy(LNode* phead)
{
    if(phead==NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead);
    {
        LNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
    phead = NULL;
}

🍄三、完整接口实现代码🍄

1.List.h

#pragma once

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

//自定数据类型LDataType
typedef int LDataType;

//双向链表节点结构
typedef struct ListNode
{
	LDataType data;
	struct LNode* next;
	struct LNode* prev;
}LNode;

LNode* LInit();    //初始化双向循环链表
void LPrint(LNode* phead);    //打印双向循环链表
LNode* BuyListNode(LDataType x);//双向循环链表新节点申请
void LPushBack(LNode* phead, LDataType x);    //双向循环链表尾插
void LPopBack(LNode* phead);    //双向循环链表尾删
void LPushFront(LNode* phead, LDataType x);    //双向循环链表头插
void LPopFront(LNode* phead);    //双向循环链表头删
LNode* LFind(LNode* phead, LDataType x);    //双向循环链表查找
void LInsertFront(LNode* pos, LDataType x);    //双向循环链表给定节点前插
void LInsertBack(LNode* pos, LDataType x);    //双向循环链表给定节点后插
void LErase(LNode* pos);    //双向循环链表给定节点删除
void LDestroy(LNode* phead);    //双向循环链表的销毁

2.List.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

//初始化双向循环链表初始化
LNode* LInit()
{
	//哨兵位头节点
	LNode* phead = (LNode*)malloc(sizeof(LNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//打印双向循环链表
void LPrint(LNode* phead)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

//双向循环链表申请新节点
LNode* BuyListNode(LDataType x)
{
    LNode* newnode = (LNode*)malloc(sizeof(LNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

//双向循环链表尾插
void LPushBack(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* tail = phead->prev;    //找到尾节点
    LNode* newnode = BuyListNode(x);
    //新尾互指
    tail->next = newnode;
    newnode->prev = tail;
    //新头互指
    phead->prev = newnode;
    newnode->next = phead;
}

//双向循环链表尾删
void LPopBack(LNode* phead)
{
    if ((phead == NULL) || (phead->next == phead))    //排除为空的情况
    {
        return;
    }
    LNode* tail = phead->prev;    //找到尾
    LNode* tailprev = tail->prev;    //找到尾的前驱
    tailprev->next = phead;    //尾前驱节点的后继指针指向头
    phead->prev = tail->prev;  //头的前驱指针指向尾的前驱
    free(tail);
    tail = NULL;
}

//双向循环链表头插
void LPushFront(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* newnode = BuyListNode(x);
    LNode* next = phead->next;    //保存哨兵节点的后继节点
    phead->next = newnode;    //哨兵点的后继指针指向新节点
    newnode->prev = phead;    //新节点的前驱指针指向哨兵节点
    newnode->next = next;    //新节点的后继指针指向哨兵节点的原后继节点
    next->prev = newnode;    //哨兵节点的原后继节点前驱指针指向新节点
}

//双向循环链表头删
void LPopFront(LNode* phead)
{
    if ((phead == NULL) || (phead->next == phead))    //排除为空的情况
    {
        return;
    }
    LNode* next = phead->next;    //保存头节点便于释放
    LNode* nextNext = next->next;    //保存头节点的后继节点
    phead->next = nextNext;
    nextNext->prev = phead;
    free(next);
    next = NULL;
}

//双向循环链表查找
LNode* LFind(LNode* phead, LDataType x)
{
    if (phead == NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

//双向循环链表给定节点前插
void LInsert(LNode* pos, LDataType x)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->prev;
    LNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

//双向循环链表给定节点前插
void LInsertFront(LNode* pos, LDataType x)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->prev;
    LNode* newnode = BuyListNode(x);
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

//双向循环链表给定节点后插
void LInsertBack(LNode* pos, LDataType x)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->next;
    LNode* newnode = BuyListNode(x);
    posPrev->prev = newnode;
    newnode->next = posPrev;
    newnode->prev = pos;
    pos->next = newnode;
}

//双向循环链表给定节点删除
void LErase(LNode* pos)
{
    if (pos == NULL)
    {
        return;
    }
    LNode* posPrev = pos->prev;
    LNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
    pos = NULL;
}

//双向循环链表销毁
void LDestroy(LNode* phead)
{
    if(phead==NULL)
    {
        return;
    }
    LNode* cur = phead->next;
    while (cur != phead);
    {
        LNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
    phead = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

void LTest()
{
	LNode* plist = LInit();
	//双向循环链表尾插
	LPushBack(plist, 1);
	LPushBack(plist, 2);
	LPushBack(plist, 3);
	LPushBack(plist, 4);
	LPrint(plist);    //打印链表
	LNode* ret = LFind(plist, 3);
	LErase(ret);
	LPrint(plist);    //打印链表
}

int main()
{
	LTest();

	return 0;
}

//双向循环链表尾插与尾删
//LNode* plist = LInit();
双向循环链表尾插
//LPushBack(plist, 1);
//LPushBack(plist, 2);
//LPushBack(plist, 3);
//LPushBack(plist, 4);
//LPrint(plist);    //打印链表
双向循环链表尾删
//LPopBack(plist);
//LPopBack(plist);
//LPopBack(plist);
//LPrint(plist);    //打印链表

//双向循环链表头插与头删
//LNode* plist = LInit();
//双向循环链表头插
//LPushFront(plist, 1);
//LPushFront(plist, 2);
//LPushFront(plist, 3);
//LPushFront(plist, 4);
//LPrint(plist);    //打印链表
双向循环链表头删
//LPopFront(plist);
//LPopFront(plist);
//LPopFront(plist);
//LPrint(plist);    //打印链表

//双向循环链表查找
//LNode* plist = LInit();
//双向循环链表尾插
//LPushBack(plist, 1);
//LPushBack(plist, 2);
//LPushBack(plist, 3);
//LPushBack(plist, 4);
//LPrint(plist);    //打印链表
//LNode* ret = LFind(plist, 3);

//双向循环链表给定位置前插
//LNode* plist = LInit();
双向循环链表尾插
//LPushBack(plist, 1);
//LPushBack(plist, 2);
//LPushBack(plist, 3);
//LPushBack(plist, 4);
//LPrint(plist);    //打印链表
//LNode* ret = LFind(plist, 3);
//LInsertFront(ret, 5);
//LPrint(plist);    //打印链表

//双向循环链表给定位置后插
//LNode* plist = LInit();
双向循环链表尾插
//LPushBack(plist, 1);
//LPushBack(plist, 2);
//LPushBack(plist, 3);
//LPushBack(plist, 4);
//LPrint(plist);    //打印链表
//LNode* ret = LFind(plist, 3);
//LInsertBack(ret, 5);
//LPrint(plist);    //打印链表

//双向循环链表给定节点删除
//LNode* plist = LInit();
双向循环链表尾插
//LPushBack(plist, 1);
//LPushBack(plist, 2);
//LPushBack(plist, 3);
//LPushBack(plist, 4);
//LPrint(plist);    //打印链表
//LNode* ret = LFind(plist, 3);
//LErase(ret);
//LPrint(plist);    //打印链表

🌶️四、顺序表与链表对比🌶️

1.两者差异

不同点顺序表链   表
连续性物理上一定连续逻辑上一定连续
是否支持随机访问是否
任意位置节点修改可能需要搬移元素效率低只需改变指针指向效率高
插入方式动态顺序表使用时需扩容无容量概念
应用场景数据高效存储+频繁访问节点及数据修改频繁
缓存利用率高低

2.存储器层次结构部分差异成因辅图

🥬总结🥬

        至此我们关于带头双向循环链表乃至链表全部内容的学习和讲解就到此为止喽~不知道各位小伙伴们掌握了多少呢希望各位小伙伴们下去以后多加练习夯实基础牢固掌握链表与顺序表的相关接口实现与使用为后面的 C++ 高阶数据结构学习打好坚实的基础

        🔥🔥相信自己拥有无限的潜力只要你有一刻渴望成长它就会支撑着你开花结果🔥🔥

        更新不易辛苦各位小伙伴们动动小手👍三连走一走💕💕 ~ ~ ~  你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【JavaWeb】HTML零基础入门

下一篇：【OpenCV】 Octave | 角点检测 | SIFT/SURF算法

“【数据结构】速速收藏，一文带你参透双向链表各接口实现” 的相关文章

JS学习笔记1年前 (2023-02-02)
【面试】vue组件style中scoped的作用是什么？什么是scoped穿透？1年前 (2023-02-02)
车载网络 - BootLoader - CAN/CANFD刷写过程1年前 (2023-02-02)
字符串不可变1年前 (2023-02-02)
这6款混合开发框架，比原生更香吗？1年前 (2023-02-02)
[Android开发学iOS系列] TableView展现一个list1年前 (2023-02-02)
学习笔记——Spring底层IOC实现；Spring依赖注入数值问题；Spring依赖注入方式1年前 (2023-02-02)
PowerShell 美化（oh-my-posh）1年前 (2023-02-02)
基于K8s的DevOps平台实践（三）1年前 (2023-02-02)
基于STM32单片机的智能家居毕设_基于stm32的智能家居1年前 (2023-02-02)

阿里云国际版