数据结构（双向链表）

🕗 发布于 2024-09-25 17:13 数据结构 链表

1. 带头双向循环链表

1. 概念与结构

顾名思义就是带有头结点且有一个指向下一个结点的next指针和一个指向前一个结点的prev指针，而且还是循环的，这里的循环就是指前面说的有环的类型；如下图所示：

这里的“带头”跟前面所说的头结点不一样，前面单链表的头结点就是第一个结点，而这里的头结点其实就是“哨兵位结点”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”，这样一来可以保证链表不为空，减少了很多需要判断的条件还有传二级指针的操作；

2. 带头双向循环链表的实现

2.1 创建结点

首先我们看结点有三个元素，一个是存储数据的data类型，一个是指向下一个结点的next指针，另一个是指向前一个结点的prev指针；如下代码所示：
```
//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
```

2.2 动态申请结点

因为这是带头双向循环链表，在我们动态申请该结点的时候需要让他的next指针和prev指针指向它自己，如果不指向它自己就不能称为循环了；代码如下：

//因为是双向带头循环链表，需要循环
//所以让prev指针和next指针都指向自己
ListNode* BuyNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyNode fails!");
exit(1);
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}

2.3 初始化链表

初始化链表的操作是要返回一个头结点也就是哨兵位结点，这里与前面的单链表不同的是这里为了保证接口的一致性只需要传一级指针，如果不设返回值的话那么；代码如下：
```
//因为是双向带头循环链表
//初始化要返回一个头，也叫哨兵位
ListNode* LTInit()
{
//因为头结点不存储值，所以给一个-1代表无效值
ListNode* phead = BuyNode(-1);
return phead;
}
```

2.4 链表的打印

由于头结点没有东西可以打印，那么我们就可以直接创建一个pcur指针指向头结点的下一个结点进行打印，一直循环到pcur->next结点为头结点的时候，因为最后一个结点的next指针是指向头结点的，我们可以通过这个特性来判断循环条件；代码如下：
```
void LTPrint(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
```

2.5 链表的尾插和头插操作的实现

尾插的实现我们首先要看会对哪几个结点会造成影响，第一个新插入的结点newnode，newnode的next指针要指向头结点，因为尾插后newnode就成为了尾结点，尾结点的prev指针要指向原来的尾结点，然后就是下图中的d3结点，d3结点也就是phead->prev，要让它的next指针指向newnode，最后再让phead的prev指针指向尾结点newnode即可；如下图和代码所示：
```
void LTPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
```
头插操作的实现思路：头插的意思不是在phead结点也就是“哨兵位”前面插入，而是在哨兵位后面插入，那么我们先来分析一下会有多少个结点发生变化；首先是1. newnode结点的prev指针和next指针，2. phead的next指针，3.phead的next结点；按照上面的思路来，首先我们要对新的结点的next指针指向phead->next结点，然后newnode->prev指向phead，再来对phead->next->prev指针进行修改让其指向newnode，注意：这里要先修改phead->next->prev指针，而不能直接修改phead->next的指向，因为如果我们先修改phead->next的话就找不到phead->next->prev了；最后再让phead->next = newnode即可；如下图和代码所示：
```
void LTPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyNode(x);

newnode->prev = phead;
newnode->next = phead->next;

phead->next->prev = newnode;
phead->next = newnode;
}
```

2.6 链表的尾删和头删操作实现

尾删操作的实现：我们这里来分析一下尾删受影响的操作有哪些，由于使用phead->prev什么的有点不太好看，那就直接按图下的来讲；首先受影响的有d2，d3和phead，然后再来看如果尾删掉d3的话，我们就需要让d2成为尾结点然后让尾结点的next指针指向头结点phead，然后让头结点的prev指针指向d2；但是我们需要注意操作顺序，如果顺序出错就会找不到其中的某一个结点；那么我们先定义一个Del指向d3，Del的意思其实就是要被删除的结点的意思，然后让Del->prev（也就是d2）->next指针指向Del->next（也就是phead头结点）;然后再直接free掉Del即可；如下图和代码所示：
```
void LTPopBack(ListNode* phead)
{
assert(phead);
assert(!(LTEmpty(phead)));
ListNode* Del = phead->prev;
Del->prev->next = Del->next;

phead->prev = Del->prev;

free(Del);
Del = NULL;
}
```
补充一点：我们在实现尾插和头插操作的时候需要判断一下链表是否为空，而链表为空则意味着链表里只有一个头结点也就是哨兵位，那么只有一个哨兵位结点的时候phead->next和phead->prev就应该是哨兵位结点自己，通过这个条件来写一个判断链表是否为空的代码如下：
```
bool LTEmpty(ListNode* phead)
{
//当链表中只有一个头结点的时候就是空
return phead == phead->next;
}
```
2.7 链表的找到相关结点
找到相关结点的实现：首先让pcur指向头结点（哨兵位结点）的下一个结点，然后循环让pcur一次一次遍历链表，当pcur->data = x(相关结点)的时候就直接返回该节点的地址，如果没有则让pcur接着往前走pcur = pcur->next; 最后结束循环也没找到的时候返回NULL，循环结束的条件就是当pcur走到phead结点的时候停止，因为这意味着已经遍历完链表了pcur回到了链表的头结点；代码如下：
```
ListNode* LTFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
```

2.8 在指定位置插入结点和删除指定位置的结点

在指定位置插入结点实现思路：首先我们来分析有哪几个结点收到影响，新插入的结点、pos结点、pos->next结点，那么我们就先动新插入的结点，因为对新插入结点的操作不会影响到原链表，所以先让新插入结点的prev指向pos结点再让next指向pos->next结点，然后再来处理pos->next结点的prev指针（这里为什么先处理pos->next结点而不是pos结点的原因是如果改了pos->next的指向就找不到pos->next结点了）指向newnode结点，最后再让pos->next指向newnode结点；如下图和代码所示：
```
//在pos位置之后插入节点
void LTInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyNode(x);

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

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

}
```
删除指定位置节点的实现：要删除pos结点，首先我们先要看一下对哪几个结点造成影响，pos->prev结点和pos->next结点；那么我们来看，其实就是让pos->prev结点的next指针指向pos->next,pos->next->prev指针指向pos->prev就行；如下图和代码所示：
```
//删除指定位置节点
void LTErase(ListNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
```
1

3. 带头双向循环链表的.h文件和.cpp文件

3.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;
}ListNode;

//为了保持接口的一致性，优化接口都为一级指针
//初始化
ListNode* LTInit();

//销毁
void LTDesTroy2(ListNode* phead);//传一级，需要手动将plist置为NULL
//打印
void LTPrint(ListNode* phead);

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

//删除
void LTPopBack(ListNode* phead);
void LTPopFront(ListNode* phead);

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

//找到相关的节点
ListNode* LTFind(ListNode* phead, LTDataType x);

//在pos位置之后插入节点
void LTInsert(ListNode* pos, LTDataType x);

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

3.2 List.cpp

#include"List.h"

//因为是双向带头循环链表，需要循环
//所以让prev指针和next指针都指向自己
ListNode* BuyNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyNode fails!");
exit(1);
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}


//因为是双向带头循环链表
//初始化要返回一个头，也叫哨兵位
ListNode* LTInit()
{
//因为头结点不存储值，所以给一个-1代表无效值
ListNode* phead = BuyNode(-1);
return phead;
}

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

void LTPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}

bool LTEmpty(ListNode* phead)
{
//当链表中只有一个头结点的时候就是空
return phead == phead->next;
}

void LTPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyNode(x);

newnode->prev = phead;
newnode->next = phead->next;

phead->next->prev = newnode;
phead->next = newnode;
}

void LTPopBack(ListNode* phead)
{
assert(phead);
assert(!(LTEmpty(phead)));
ListNode* Del = phead->prev;
Del->prev->next = Del->next;

phead->prev = Del->prev;

free(Del);
Del = NULL;
}

void LTPopFront(ListNode* phead)
{
assert(phead);
assert(!(LTEmpty(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* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}

//在pos位置之后插入节点
void LTInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyNode(x);

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

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

}

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

END!

原文地址：https://blog.csdn.net/2301_80475151/article/details/142331061

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

上一篇：[Simpfun游戏云1]搭建MC Java+基岩互通生存游戏服务器
下一篇：qt 模仿简易的软狗实现

PHP 中，将 JSON 数据与二进制数据之间进行相互转化主要涉及两个步骤：
要将 JSON 数据转换为二进制数据，首先需要将 JSON 数据解析成 PHP 数组或对象，然后使用 PHP 的。函数将二进制字符串转换为 PHP 数组或对象，然后将其编码为 JSON 数据。如果你只
阅读更多2024-09-28
JavaEE: 探索网络世界的核心-IP协议
13位分片偏移: 是分片相对于原始IP报文开始处的偏移.其实就是在表示当前分片在原报文中处在哪个位置.实际偏移的字节数是这个值 * 8 得到的.因此,除了最后一个报文之外,其他报文的长度必须是8的整数
阅读更多2024-09-28
数据库常见概念
PostgreSQL 支持联合索引和聚簇索引，联合索引可以加速多列条件的查询，而聚簇索引控制数据在磁盘上的排列。适当地使用这些索引可以提高查询性能。
阅读更多2024-09-28
BEV学习---LSS4-模型训练
LSS训练测试
阅读更多2024-09-28
SpringCloud第六章(服务保护CircuitBreaker) -2024
CircuitBreaker是断路器的意思，由于原来的SpringCoud的hystrix停更，所以springcloud社区推出了的新断路器，用来进行springcloud的服务降级、限流、熔断由于
阅读更多2024-09-28
ubuntu 开启root
【代码】ubuntu 开启root。
阅读更多2024-09-28
MySQL数据查询（基础）
SELECT语句用于从表中查询数据。可以选择特定的列，也可以选择所有列。：使用表示选择所有列。
阅读更多2024-09-28
区块链可投会议CCF C--FC 2025 截止10.8 附录用率
CCF C：2025：2023年 39 full and 2 short papers selected from 182 submissions.
阅读更多2024-09-28
第1章 C语言概述
4.打开项目后，右击"源文件"并选择"添加"的"新建项"6.在"hello_word"文件下编写代码并点击运行。1.打开
阅读更多2024-09-28
Git 与 GUI 工具
当我们对 Git 的提交、分支已经非常熟悉，可以熟练使用命令操作 Git 后，再使用 GUI 工具，就可以更高效。
阅读更多2024-09-28