【数据结构】双向带头循环链表（笔记总结）

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注

前景回顾

在单链表这篇博客中，我们已经实现了单链表的增删查改。今天这篇博客，我将带领大家实现最后一个常见的链表之双向带头循环链表

目录

  • 前景回顾
  • 一、结构介绍
  • 二、准备工作
  • 三、接口
  • 四、代码实现
      • 4.1 开辟新结点
      • 4.2 初始化哨兵位头结点
      • 4.3 尾插
      • 4.4 打印
      • 4.5 判断链表是否为空
      • 4.6 尾删
      • 4.7 头插
      • 4.8 头删
      • 4.9 在pos前插入x
      • 4.10 删除pos结点
      • 4.11 查找某个节点
      • 4.12 释放
  • 五、总结

一、结构介绍

在这里插入图片描述

如上图所示，双向带头循环链表顾名思义就是有一个哨兵位的头结点，然而这个头结点却不存储有效数据；其次，一个结点存储两个地址，一个地址是存储下一个结点的地址，而另一个地址存储的是上一个结点的地址。

综上，不难可以写出它的结构

typedef int DLDataType;typedef struct DListNode
{DLDataType data;struct DListNode* prev;//指向下一个结点struct DListNode* next;//指向前一个结点
}DTNode;

二、准备工作

为了方便管理，我们可以创建多个文件来实现

test.c – 测试代码逻辑 （源文件）
DList.c – 动态的实现 （源文件）
DList.h – 存放函数的声明 （头文件）
在这里插入图片描述

三、接口

【DList.h】


typedef int DTDataType;typedef struct DListNode
{DTDataType data;struct DListNode* prev;//指向下一个结点struct DListNode* next;//指向前一个结点
}DTNode;//开辟新结点
DTNode* BuyListNode(DTDataType x);
//初始化哨兵位头结点
DTNode* DTInit();
//尾插
void DTPushBack(DTNode* phead, DTDataType x);
//打印
void DTPrint(DTNode* phead);
//尾删
void DTPopBack(DTNode* phead);
//判断链表是否为空
bool DTEmpty(DTNode* phead);
//头插
void DTPushFront(DTNode* phead, DTDataType x);
//头删
void DTPopFront(DTNode* phead);
//在pos之前插入x
void DTInsert(DTNode* pos, DTDataType x);
//删除pos结点
void DTErase(DTNode* pos);
//查找
DTNode* DTFind(DTNode* phead, DTDataType x);
//释放
void DTDestroy(DTNode* phead);

四、代码实现

4.1 开辟新结点

//开辟新结点
DTNode* BuyListNode(DTDataType x)
{DTNode* newnode = (DTNode*)malloc(sizeof(DTNode));if (newnode == NULL){perror("newnode :: malloc");return NULL;}newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}

作用：有这个接口是因为后面的头结点初始化、尾插、头插等都需要开辟新的结点，有这个接口方便代码复用。

4.2 初始化哨兵位头结点

//初始化哨兵位头结点
DTNode* DTInit()
{DTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

【笔记总结】

  1. 哨兵位的头结点是不存放有意义的数据
  2. 由于是循环链表，初始化时应该自己指向自己

4.3 尾插

//尾插
void DTPushBack(DTNode* phead, DTDataType x)
{//哨兵位绝对不可能为空assert(phead);// 1.开辟新结点DTNode* newnode = BuyListNode(x);// 2.找尾DTNode* tail = phead->prev;// 3.链接  head tail newnodetail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

【笔记总结】

  1. 哨兵位的头结点绝对不可能为空，所以加个断言
  2. 双向循环链表找尾不需要向单链表那样遍历，因为头结点的prev就是尾

【动画展示】

在这里插入图片描述

4.4 打印

//打印
void DTPrint(DTNode* phead)
{assert(phead);DTNode* cur = phead->next;while (cur != phead){printf("<=%d=>", cur->data);cur = cur->next;}printf("\n");
}

【笔记总结】

  1. 打印遍历链表时不能从头结点开始。
  2. 遍历结束条件是cur != phead，因为当cur遍历到尾结点，由于是循环链表，下一个结点就是哨兵位的头结点。

4.5 判断链表是否为空

//判断链表是否为空
bool DTEmpty(DTNode* phead)
{assert(phead);return phead->next == phead;
}

【笔记总结】

  1. 当链表只剩下一个哨兵位的头结点，说明链表为空。所以双向链表为空的情况是头结点的next指向本身。

4.6 尾删

//尾删
void DTPopBack(DTNode* phead)
{assert(phead);assert(!DTEmpty(phead));//1.找尾DTNode* tail = phead->prev;//2.记录尾结点的前一个结点DTNode* tailprev = tail->prev;//3.链接 phead  tailprev tailprev->next = phead;phead->prev = tailprev;//4.释放尾结点free(tail);
}

【学习笔记】
尾删要特判原链表是否为空。空链表不能删！！

【动图展示】

在这里插入图片描述

4.7 头插

//头插
void DTPushFront(DTNode* phead, DTDataType x)
{assert(phead);//1.申请新结点DTNode* newnode = BuyListNode(x);//2.链接newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

【学习笔记】

  1. 此处注意链接顺序。不要先让head的next指向newnode，否则后面newnode的next想指向head的next就找不到了
    在这里插入图片描述
  2. 那有没有什办法可以不用注意链接顺序，当然有！提前记录head下一个结点就可以不用注意链接顺序啦
    在这里插入图片描述

4.8 头删

//头删
void DTPopFront(DTNode* phead)
{assert(phead);assert(!DTEmpty(phead));//1.记录哨兵位的下一个结点(即头结点)DTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//2.释放delfree(del);
}

【动图展示】
在这里插入图片描述

4.9 在pos前插入x

//在pos之前插入x
void DTInsert(DTNode* pos, DTDataType x)
{assert(pos);//1.申请新结点DTNode* newnode = BuyListNode(x);//2.记录pos的前一个结点DTNode* posprev = pos->prev;//3.插入 posprev newnode posposprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

【动图展示】
在这里插入图片描述

4.10 删除pos结点

//删除pos结点
void DTErase(DTNode* pos)
{assert(pos);//1.记录pos前一个结点DTNode* posprev = pos->prev;//2.链接posprev->next = pos->next;pos->next->prev = posprev;//3.释放posfree(pos);
}

【动图展示】
在这里插入图片描述

4.11 查找某个节点

//查找
DTNode* DTFind(DTNode* phead, DTDataType x)
{assert(phead);//1.不能从哨兵位开始遍历DTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}//若循环结束，还没找到则返回NULLreturn NULL;
}

详细细节可参考打印

4.12 释放

//释放
void DTDestroy(DTNode* phead)
{DTNode* cur = phead->next;while (cur != phead){//在释放前每次记录cur的下一个结点DTNode* next = cur->next;free(cur);cur = next;}//最后再单独释放pheadfree(phead);
}

五、总结

  1. 相比单链表，需要遍历链表找尾，但是带头双向循环链表可以直接找到尾节点，时间复杂度为O(1)。
  2. 但缺点是：不支持随机访问，缓存命中率相对低。

查看全文

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.dgrt.cn/a/2173729.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章：

在这里插入图片描述

【数据结构】双向带头循环链表（笔记总结）

👦个人主页：Weraphael ✍🏻作者简介：目前学习C和算法 ✈️专栏：数据结构 🐋 希望大家多多支持，咱一起进步！😁 如果文章对你有帮助的话 欢迎 评论💬 点赞&……

编程日记2023/4/3 21:14:25

Centos8中安装Docker

一、基础准备
1.1、Docker Engine 简介 Docker Engine是用来运行和管理容器的核心软件【通常人们会简单地将其命名为 Docker 或 Docker 平台】，其基于 Go 语言编写，并遵从Apache2.0协议开源；Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中，然后……

编程日记2023/4/3 21:14:15

子网划分例题解析-确定一个ip是一个子网中的合法可用地址？

网上有人提问：
以下地址中是合法主机 IP地址的是()？ A 152.178.132.95/27 B 152.179.39.223/26 C 219.72.294.80/25 D 61.139.144.0/22
答案是B
题目解决思路：
1、检查ip地址四段的合法性 ip地址是32位，为方便记录分成四段&am……

编程日记2023/4/3 21:14:02

python开启局域网传输

python开启局域网传输
1.找自己的IP 在命令提示窗口输入：ipconfig <—-找自己的IP地址 2.创建要传输文件的文件夹（只允许在该文件夹下访问传输）
a.复制文件夹路径
b.在命令提示窗口cd打开新创建的文件夹 cd “C:\Users\86151\Desktop……

编程日记2023/4/3 21:13:22

中华好诗词（四）

301、李商隐的《锦瑟》中引用了哪四个典故？（庄周梦蝶、杜鹃啼血、鲛人泣珠、蓝田日暖,良玉生烟）
302、白居易《琵琶行》中写道：“门前冷落车马稀,老大嫁作商人妇.”这句诗化用了哪个成语？.（门前冷落&#……

编程日记2023/4/3 21:12:54

函数重载的一个小问题

源码如下：
#include "iostream"
int MyFunc(int a){ return a;}
float MyFunc(float a){ return a;}
int main(){ MyFunc(1.2); return 0;}
编译错误提示：error C2668: MyFunc : ambiguous call to overloaded function
原因&#xff1a……

编程日记2023/4/3 21:12:38

大腕求职版

一定得选最好的简历模版，用Havard的Model，写就写最牛逼的事，排名直接第一，GPA最少也得3.95，什么CPA啊，CFA，ACCA啊，能敲的都给它敲上；手机24小时开机，震动带响……

编程日记2023/4/3 21:12:38

ASPX页面配置问题

应用程序中的服务器错误。 配置错误
说明: 在处理向该请求提供服务所需的配置文件时出错。请检查下面的特定错误详细信息并适当地修改配置文件。 分析器错误信息: 在应用程序级别之外使用注册为 allowDefinitionMachineToApplication 的节是错误的。如果在 IIS 中没有将虚拟目……

编程日记2023/4/3 21:12:37

使用Visual C++.Net2005托管时的几个问题

由于在Visual Studio 2005中采用了修订版（V2）的设计语言，原本的许多关键字都做了改变。
首先，所有的关键字都去掉了前面的双下划线。例如，原本的__delegate，现在用delegate就ok啦。
另外，个别……

编程日记2023/4/3 21:12:37

智能网络的数据挖掘

智能网络的数据挖掘
1、目前访问网络上的数据的方法（1）基于关键词的搜索或主题-目录式浏览（2）搜索深度网络资源（3）随即选取网络链接2、设计中的困难抽象层面上，原来的搜索方法假定了网页是基于……

编程日记2023/4/3 21:12:36

【Linux基础】常用命令整理

ls命令
-a选项，可以展示隐藏的文件和文件夹-l选项，以列表形式展示内容-h，需要和-l搭配使用，可以展示文件的大小单位ls -lah等同于la -a -l -h
cd命令（change directory）
语法：cd [Linux路径]……

编程日记2023/4/16 14:51:26

客快物流大数据项目（一百一十二）：初识Spring Cloud

文章目录
初识Spring Cloud
一、Spring Cloud简介
二、SpringCloud 基础架构图…

编程日记2023/4/16 14:51:11

C和C++中的struct有什么区别

区别一： C语言中： Struct是用户自定义数据类型（UDT）。 C语言中： Struct是抽象数据类型（ADT），支持成员函数的定义。
区别二：
C中的struct是没有权限设置的&#xff0c……

编程日记2023/4/16 14:50:59

docker的数据卷详解

数据卷 数据卷是宿主机中的一个目录或文件，当容器目录和数据卷目录绑定后，对方修改会立即同步
一个数据卷可以同时被多个容器同时挂载，一个容器也可以被挂载多个数据卷
数据卷作用：容器数据持久化 /外部机器和容器间接通信 /容器……

编程日记2023/4/16 14:50:50

13、Qt生成dll-QLibrary方式使用

Qt创建dll，使用QLibrary类方式调用dll
一、创建项目
1、新建项目->其他项目->Empty qmake Project->Choose 2、输入项目名，选择项目位置，下一步 3、选择MinGW，下一步 4、完成 5、.pro中添加TEMPLATE subdirs&#xff……

编程日记2023/4/16 14:50:38

基于mapreduce 的 minHash 矩阵压缩

Minhash作用： 对大矩阵进行降维处理，在进行计算俩个用户之间的相似度。
比如： 俩个用户手机下载的APP的相似度，在一个矩阵中会有很多很多的用户要比较没俩个用户之间的相似度是一个很大的计算任务 如果首先对这个矩阵降维处理&am……

编程日记2023/4/16 14:50:37

关于hashmap使用迭代器的问题

keySet获得的只是key值的集合，valueSet获得的是value集合，entryset获得的是键值对的集合。 package com.test2.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;public class mapiterator……

编程日记2023/4/16 14:50:37

Hadoop入口FileSystem HDFS操作 本地文件合并到HDFS和HDFS文件合并

Hadoop 文件API的起点是FileSystem类。这是一个与文件系统交互的抽象类。存在不同的具体实现子类来处理HDFS和本地文件系统。
HDFS接口的FileSystem对象：
Configuration conf new Configuration();
FileSystem hdfs FileSystem.get(conf); HDFS直接操作&#x……

编程日记2023/4/16 14:50:36

combiner partitioner

combine是在map端进行的，是在patition之后 partitioner也是在map端进行的 combine 适用在每个map端进行简单的合并，同样也是继承Reduce类。…

编程日记2023/4/16 14:50:35

toString.indexOf(:)和subsTring

package com.test2.test;public class subStirngTest {public static void main(String[] args) {String sb"abcdefgh";String sc"abcd:efgh";int splitIndexsc.indexOf(":");//找到标识符的位置System.out.println(splitIndex);sb.substring(1)……

编程日记2023/4/16 14:50:35

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注