数据结构之链表（2），双向链表

🕗 发布于 2024-10-04 01:21 链表 数据结构 算法

前言

一、链表的分类详细

二、双向链表

前言

接着上一篇单链表来详细说说链表中什么是带头和不带头，“哨兵位”是什么，什么是单向什么是双向，什么是循环和不循环。然后实现完整的双向链表代码。

❤️感谢支持，点赞关注不迷路❤️

一、链表的分类详细

上一篇已经说过，链表总共分为8中结构，常用的就是单链表和双链表

这里的单链表全称：不带头单向不循环链表。双链表全称：带头双向循环链表

以下是上一篇中提到的8中结构：

注意：因为常用的只有单链表和双链表，将这两种链表结构掌握之后就能够自行实现其他结构的链表。

1.带头和不带：

带头与不带头的区别就是：带头的链表有一个头结点（head），也叫哨兵位。

哨兵位：带头链表的头结点，不存储任何有效元素，仅用于占位，代表链表的头部，功能类似于“放哨”，因此叫哨兵位。

注意：上一篇中的单链表是不带头的，因此不存在头结点的说法，所以上一篇中说的头结点仅仅是为了方便称呼第一个节点的一种不规范叫法，只有带头链表才有头结点的说法。尤其是在链表的分类中。

2.单向和双向

区别：

结构上：单向链表只有一个指向下一个节点的指针。双向链表有一个指向前一个节点的指针和一个指向后一个节点的指针。
功能上：单向链表只能单向访问下一个节点。双向链表可以既可以访问下一个节点也可以访问上一个节点。

3.循环和不循环

区别：不循环链表的尾结点next指针会指向空指针。循环链表的尾结点next指针不为空，可以无限循环的访问下一个节点。

注意：循环链表的尾结点的next指针可以指向链表的第一个节点，或者中间的任一节点，甚至尾结点。这都叫循环链表。

二、双向链表

双向链表全称：带头双向循环链表。

结构图如下：

双向链表的结构声明如下：

typedef int LTDataType;
//定义双链表结构
typedef struct ListNode
{
   LTDataType data;//存储数据
   struct ListNode* next;//指向下一个节点
   struct ListNode* prev;//指向上一个节点
}LTNode;

同样，双向链表的实现也分为三个文件：

List.h：双向链表的头文件，包含各种库函数头文件、链表结构、函数的声明。
List.c：用于实现各种接口（函数）。
test.c：用于测试。

三、双向链表的实现

1.List.h文件

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

typedef int LTDataType;
//定义双链表结构
typedef struct ListNode
{
LTDataType data;//存储数据
struct ListNode* next;//指向下一个节点
struct ListNode* prev;//指向上一个节点
}LTNode;

//初始化
//第一种：传二级指针
//void LTInit(LTNode** pphead);
//第二种：不传参
LTNode* LTInit();

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

//尾插
void LTPushBack(LTNode* phead, LTDataType x);

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

//判空
bool LTEmpty(LTNode* phead);

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

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

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);

//删除指定位置的节点
void LTErase(LTNode* pos);

//销毁
//第一种：传二级指针
//void LTDesTroy(LTNode** pphead);
//第二种：传一级指针，缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead);

2.List.c文件

1.LTBuyNode函数

//申请新节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;

//前后指针全部指向自己，自循环
newnode->next = newnode->prev = newnode;

return newnode;
}

解析：

功能：用于申请新节点。
参数：新节点的需数据x
使用malloc函数申请一个节点空间，判空后将其数据域赋值x。注意，新节点的两个指针都需要指向自己，这样才是一个双向循环链表。
因为该函数只为其他函数服务，因此可以只在 List.c 文件中定义，无需在 List.h 中声明。

2.LTInit函数

//初始化
//第一种：传二级指针
//void LTInit(LTNode** pphead)
//{
//assert(pphead);
//
////创建一个头结点（哨兵位）
//*pphead = LTBuyNode(-1);
//}

//第二种：不传参
LTNode* LTInit()
{
return LTBuyNode(-1); 
}

解析：

该函数有两个版本，第二种为优化后的版本，为的是保持接口的一致性，因为双向链表的其它功能函数都只是传一级指针。为了避免混淆，优化为不传参版本。
功能：初始化为哨兵位（头结点）。
第一种：需要传参版本，传二级指针，因为只有二级指针才能修改一级指针的指向。因此这里使用二级指针进行初始化赋值。-1可以改为任何值，因为哨兵位存储的数据为无效数据。
第二种：不传参版本，直接创建并返回哨兵位的地址。
使用上的区别：第一种需要自己定义一个双向链表类型的空指针，然后使用调用该函数进行传参初始化，注意传参时需&。第二种自己创建一个双向链表类型的空指针并调用该函数进行赋值。

3.LTPrint函数

//打印
void LTPrint(LTNode* phead)
{
assert(phead);

LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}

解析：

功能：打印链表的所有节点数据。
参数：链表的头结点（哨兵位）。
首先断言头结点不能为空，创建一个 pcur 指针指向第一个有效节点，
然后进行循环遍历时，因为该链表是循环链表，因此循环一遍的判定是 pcur 指向的节点不是头结点。循环体里就是打印数据然后让pcur走向下一个节点。打印完后换行即可。

4.LTPushBack函数

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* newnode = LTBuyNode(x);

//首先修改新节点的指针指向
newnode->next = phead;//next指针指向哨兵位
newnode->prev = phead->prev;//prev指针指向尾节点

//再修改旧尾节点和哨兵位
phead->prev->next = newnode;//旧尾节点的next指针指向新尾节点
phead->prev = newnode;//哨兵位后指针指向新尾节点
}

解析：

功能：在链表的尾部插入一个节点
参数：头结点（哨兵位）和需要插入的节点数据
首先断言头结点不为空，申请新节点，然后就需要改变新节点和受影响节点的指针指向。这里需要注意修改的前后顺序，
先修改新节点的指针指向，新节点的 next 指针应该指向头结点，因为是循环链表，原尾结点可以通过头结点找到，即 phead->prev 指向的就是原来的尾结点，将新节点的 prev 指针指向原尾结点。
修改完新节点就需要修改头结点和原尾结点的指针指向，原尾结点依旧可以通过头结点的 prev 指针找到，将其 next 指针指向新节点。最后就是头结点的 prev 指针需要指向新节点。

5.LTPushFront函数

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

LTNode* newnode = LTBuyNode(x);

//首先还是先修改新节点的指向
newnode->next = phead->next;
newnode->prev = phead;

//然后修改旧头结点和哨兵位
phead->next->prev = newnode;
phead->next = newnode;
}

解析：

功能：在第一个有效节点之前插入数据，也就是头结点（哨兵位）之后
参数：头结点（哨兵位）和需插入的节点数据、
首先头插为什么不是在头结点前面插入数据，很简单，头结点的 prev 指针就是指向尾结点的，所以如果在头结点之前插入数据，其实就是尾插。
实现过程，开头还是断言和申请新节点，然后先修改新节点的前后指针指向，原第一个有效节点可以通过头结点的 next 指针找到。修改完新节点后就修改原第一节点的prve指针，使其指向新节点，最后修改头结点的 next 指针也指向新节点。

6.LTEmpty函数

//判空
//只有哨兵位节点说明链表为空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}

解析：

功能：判断链表是不是空链表，也就是判断链表是不是只有头结点（哨兵位）
参数：头结点（哨兵位）
该函数主要为后续删除链表节点时判断链表是否为空链表，实现简单，断言头结点后，直接判断头结点的下一个节点是不是还是头结点即可。

7.LTPopBack函数

//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

//先保存尾结点和倒数第二个节点
LTNode* del = phead->prev;
LTNode* prev = del->prev;

//再修改倒数第二节点和哨兵位节点指向
prev->next = phead;
phead->prev = prev;

//释放尾结点
free(del);
del = NULL;
}

解析：

功能：删除尾结点
参数：头结点（哨兵位）
首先断言判断头结点是否为空指针以及链表是否为空链表，然后创建 del 指针保存尾结点，创建 prev 指针保存倒数第二个节点，避免修改完受影响节点的前后指针指向后找不到尾结点，
然后修改倒数第二个节点的 next 指针指向头结点，以及头结点的 prev 指针指向倒数第二个节点。最后释放尾结点（del），最后释放尾结点 del 即可。

8.LTPopFront函数

//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

//还是先保存第一个有效节点
LTNode* del = phead->next;
del->next->prev = phead;//修改第二个有效节点指向
phead->next = del->next;//修该哨兵位指向

//释放
free(del);
del = NULL;
}

解析：

功能：删除第一个有效节点，也就是头结点（哨兵位）的下一个节点
参数：头结点（哨兵位）
还是先断言判断头结点和链表是否为空，创建 del 指针保存第一个有效节点，然后先通过 del指针找到并修改第二个有效节点的 prev 指针，使其指向头结点，再修改头结点的 next 指针指向第二个节点。最后就可以直接释放第一个节点 del 即可。

9.LTFind函数

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* pcur = phead->next;
//循环遍历
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}

return NULL;
}

解析：

功能：根据指定数据查找对应的节点，然后返回该节点的地址，主要是配合后面两个函数使用
有了上面函数实现的经验，查找函数实现简单，循环遍历，循环链表循环一遍的标志是下一节点为头结点，找到就返回节点的地址，找不到返回空指针。

10.LTInsert函数

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);

LTNode* newnode = LTBuyNode(x);

//先修改新节点朝向
newnode->next = pos->next;
newnode->prev = pos;

//在修改受影响的两个节点朝向，注意顺序
pos->next->prev = newnode;
pos->next = newnode;
}

解析：

功能：在指定位置之后插入数据，这个指定位置需要通过 LTFind 函数指定。
双向链表插入数据其实都差不多，先修改新节点的前后指针，再修改受影响节点的指针。这里不再赘述。

11.LTErase函数

//删除指定位置的节点
void LTErase(LTNode* pos)
{
assert(pos);

//先修改pos的前后节点
pos->next->prev = pos->prev;
pos->prev->next = pos->next;

free(pos);
pos = NULL;
}

解析：

功能：删除指定位置的节点
这个实现更加简单，通过 pos 指针先修改前后节点的指针指向，然后就可以直接释放掉自己。

12.LTDesTroy函数

//销毁
//第一种：传二级指针
//void LTDesTroy(LTNode** pphead)
//{
//assert(pphead && *pphead);
//
//LTNode* pcur = (*pphead)->next;
//while (pcur != *pphead)
//{
//LTNode* Next = pcur->next;
//free(pcur);
//pcur = Next;
//}
//
//free(*pphead);
//*pphead = NULL;
//pcur = NULL;
//}

//第二种：传一级指针，缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead)
{
assert(phead);

LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* Next = pcur->next;
free(pcur);
pcur = Next;
}

free(phead);
phead = pcur = NULL;
}

解析：

销毁函数有两种，第二种为优化后的版本，同样也是为了接口的一致性，避免使用时混淆，因此传一级指针合适，但是带来的缺点就是需要手动将哨兵位置空。
两个版本的函数实现方式大致相同，循环遍历，在释放当前节点之前要先使用 Next 指针保存下一节点的地址。
第一个版本缺点是需要传二级指针，但是不需要手动将哨兵位置空，函数内部就可以实现置空，第二版本优点就是同其他接口一样，只需要传一级指针，缺点就是在调用完该函数后需要手动将哨兵位置空。

四、List.c文件的完整代码

#include "List.h"

//申请新节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;

//前后指针全部指向自己，自循环
newnode->next = newnode->prev = newnode;

return newnode;
}

//初始化
//第一种：传二级指针
//void LTInit(LTNode** pphead)
//{
//assert(pphead);
//
////创建一个头结点（哨兵位）
//*pphead = LTBuyNode(-1);
//}

//第二种：不传参
LTNode* LTInit()
{
return LTBuyNode(-1);
}


//打印
void LTPrint(LTNode* phead)
{
assert(phead);

LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* newnode = LTBuyNode(x);

//首先修改新节点的指针指向
newnode->next = phead;//next指针指向哨兵位
newnode->prev = phead->prev;//prev指针指向尾节点

//再修改旧尾节点和哨兵位
phead->prev->next = newnode;//旧尾节点的next指针指向新尾节点
phead->prev = newnode;//哨兵位后指针指向新尾节点
}

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

LTNode* newnode = LTBuyNode(x);

//首先还是先修改新节点的指向
newnode->next = phead->next;
newnode->prev = phead;

//然后修改旧头结点和哨兵位
phead->next->prev = newnode;
phead->next = newnode;
}

//判空
//只有哨兵位节点说明链表为空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}

//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

//先保存尾结点和倒数第二个节点
LTNode* del = phead->prev;
LTNode* prev = del->prev;

//再修改倒数第二节点和哨兵位节点指向
prev->next = phead;
phead->prev = prev;

//释放尾结点
free(del);
del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

//还是先保存第一个有效节点
LTNode* del = phead->next;
del->next->prev = phead;//修改第二个有效节点指向
phead->next = del->next;//修该哨兵位指向

//释放
free(del);
del = NULL;
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* pcur = phead->next;
//循环遍历
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}

return NULL;
}

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);

LTNode* newnode = LTBuyNode(x);

//先修改新节点朝向
newnode->next = pos->next;
newnode->prev = pos;

//在修改受影响的两个节点朝向，注意顺序
pos->next->prev = newnode;
pos->next = newnode;
}

//删除指定位置的节点
void LTErase(LTNode* pos)
{
assert(pos);

//先修改pos的前后节点
pos->next->prev = pos->prev;
pos->prev->next = pos->next;

free(pos);
pos = NULL;
}

//销毁
//第一种：传二级指针
//void LTDesTroy(LTNode** pphead)
//{
//assert(pphead && *pphead);
//
//LTNode* pcur = (*pphead)->next;
//while (pcur != *pphead)
//{
//LTNode* Next = pcur->next;
//free(pcur);
//pcur = Next;
//}
//
//free(*pphead);
//*pphead = NULL;
//pcur = NULL;
//}

//第二种：传一级指针，缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead)
{
assert(phead);

LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* Next = pcur->next;
free(pcur);
pcur = Next;
}

free(phead);
phead = pcur = NULL;
}

五、使用演示

使用测试文件 test.c 进行演示：

#include "List.h"

void ListTest1()
{
//创建哨兵位（头结点）
LTNode* plist = LTInit();

//尾插4个节点
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
printf("尾插：");
LTPrint(plist);

//头插4个节点
LTPushFront(plist, 11);
LTPushFront(plist, 12);
LTPushFront(plist, 13);
LTPushFront(plist, 14);
printf("头插：");
LTPrint(plist);

//在1后面插入一个数据
LTInsert(LTFind(plist, 1), 66);
printf("在1后面插入66：");
LTPrint(plist);

//尾删
LTPopBack(plist);
printf("尾删：");
LTPrint(plist);

//头删
LTPopFront(plist);
printf("头删：");
LTPrint(plist);

//删除11
LTErase(LTFind(plist, 11));
printf("删除11：");
LTPrint(plist);

//销毁
LTDesTroy(plist);
plist = NULL;//需要手动置空
printf("链表已销毁\n");

}

int main()
{
ListTest1();

return 0;
}

运行结果：

总结

以上就是本文的全部内容，感谢支持。

原文地址：https://blog.csdn.net/x_p96484685433/article/details/142615897

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：22.2 k8s中ksm采集的使用的dns解析
下一篇：OceanBase企业级分布式关系数据库

linux网络编程实战
之前找工作的之后写了一些网络编程的笔记和代码，然后现在放到csdn上保存一下。有几个版本的，看看就好。就是简单的实现一下服务端和客户端之间的交互的，还没有我之前上linux编程课写的代码复杂。
阅读更多2024-10-06
PriorityQueue分析
PriorityQueue：概述、应用场景、源码、堆排序；拓展：JDK里PriorityBlockingQueue和DelayQueue、ScheduledExecutorService、Rocket
阅读更多2024-10-06
CANoe_TestModule截图功能TestReportAddWindowCapture
TestReportAddWindowCapture方法作为CAPL脚本中的一个重要功能，其能够将指定窗口的屏幕截图添加到测试报告中，对于记录和验证界面状态具有重要意义。本文将全面解析TestRepo
阅读更多2024-10-06
数据服务-实时同步(sersync)
1.之前我们通过rsync+定时任务实现定时备份/同步2. 对于NFS我们需要进行实时同步。
阅读更多2024-10-06
unity ps 2d animation 蛇的制作
unity ps 制作小蛇
阅读更多2024-10-06
C语言：预编译过程的剖析
5. _ _STDC_ _ //如果编译器遵循ANSI C，其值为1，否则未定义。在执行编译一个程序的时候，我们如果要将一条语句（一组语句）编译或者放弃是很方便的。1.
阅读更多2024-10-06
游戏中的对象池技术探索（一）
本篇文章我们就来探索一下如何在游戏开发中设计通用对象池，使之易于使用和扩展。
阅读更多2024-10-06
字节跳动收购Oladance耳机：强化音频技术，加速VR/AR生态布局
此次收购，字节跳动不仅获得了Oladance的核心技术，还吸纳了一支经验丰富的团队，补足了自身在音频技术方面的短板。对于字节跳动而言，此次收购具有深远意义。其次，这次收购也是字节跳动AI硬件战略的重要
阅读更多2024-10-06
linux：详解nohup命令
在 UNIX 和类 UNIX 操作系统（如 Linux 和 macOS）中，nohup 意图为后台运行且免疫挂断信号的命令，用于在用户注销（logout）或终端关闭后继续运行相应的进程。
阅读更多2024-10-06
expressjs 中的mysql.createConnection，execute 怎么使用
在 Express.js 应用中使用 MySQL 数据库，你通常会使用mysql或mysql2这样的库来创建和管理数据库连接，并执行查询。然而，并不直接提供execute方法。相反，你可以使用quer
阅读更多2024-10-06

数据结构之链表（2），双向链表

前言

一、链表的分类详细

1.带头和不带：

2.单向和双向

3.循环和不循环

二、双向链表

三、双向链表的实现

1.List.h文件

2.List.c文件

1.LTBuyNode函数

2.LTInit函数

3.LTPrint函数

4.LTPushBack函数

5.LTPushFront函数

6.LTEmpty函数

7.LTPopBack函数

8.LTPopFront函数

9.LTFind函数

10.LTInsert函数

11.LTErase函数

12.LTDesTroy函数

四、List.c文件的完整代码

五、使用演示

总结

相关文章