数据结构-双向链表

目录

1.带头双向循环链表：

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

双向链表初始化：

双向链表打印：

开辟节点函数：

双向链表头插：

双向链表尾插：

双向链表头删：

双向链表尾删：

 双向链表查找：

双向链表在pos之前插入：

双向链表在pos位置删除：

 双向链表的销毁：

3.完整代码：

test.c

List.h

List.c

4.测试：​编辑

5.顺序表和链表的区别

1.带头双向循环链表：

前面我们已经知道了链表的结构有8种，我们主要学习下面两种：

前面我们已经学习了无头单向非循环链表，今天我们来学习带头双向循环链表：

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了 

 带头双向循环链表不需要二级指针，因为我们刚开始就为其开辟了一个节点，叫做哨兵位头节点，它是结构体中的指针，用结构体指针就能改变它，而要改变结构体外面的指针才会用二级指针。

双向循环链表顾名思义，除了哨兵位头节点以外，每个节点里面应该有两个指针，下面我们定义一个结构体：

typedef int ListDatatype;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;ListDatatype data;
}LTNode;

prev指向前一个节点，next指向后一个节点。

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

双向链表初始化：

LTNode* InitList()
{LTNode* phead = BuyList(-1);phead->next = phead;phead->prev = phead;return phead;
}

 双向循环链表开始时头和尾都指向自己：

BuyList函数的功能是创建节点，我们在初始化时用它创建哨兵位头节点，因为后面还有多次使用，所以把它封装为函数。

双向链表打印：

void Print(LTNode* phead)
{LTNode*cur = phead->next;printf("guard<->");while (cur != phead){printf("%d<->", cur->data);cur = cur->next;}printf("\n");
}

开辟节点函数：

LTNode* BuyList(ListDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}

双向链表头插：

头插实际是在哨兵位头节点phead的后面插入，保存住head->next的位置，然后把newnode前后分别和head、head->next链接起来就行。

代码如下： 

void ListPushFront(LTNode* phead, ListDatatype x)
{assert(phead);LTNode* newnode = BuyList(x);LTNode* next = phead->next;phead->next = newnode;next->prev = newnode;newnode->next = next;newnode->prev = phead;
}

这段代码神奇的地方在于，即使链表为空，它也能头插，并且不需要判断链表是否为空：

因为就算链表为空，我们有哨兵位头节点存在，就不用担心空指针的问题。 

双向链表尾插：

双向链表相对于单链表的优势就是不用找尾，因为它的phead->prev就是尾，尾插同头插差不多， 把newnode的前后分别和链表的尾和头链接起来即可。

代码如下：

void ListPushBack(LTNode* phead, ListDatatype x)
{assert(phead);LTNode* newnode = BuyList(x);LTNode* tail = phead->prev;tail->next = newnode;phead->prev = newnode;newnode->prev = tail;newnode->next = phead;
}

和头插一样，尾插也不用判断链表为空的情况。

双向链表头删：

头删指的是删除哨兵位头节点后面一个节点，只要将头节点与要删除的节点后面的节点相连接，然后free掉要删除的节点即可。

 代码如下：

void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));LTNode* cur = phead;LTNode* first = cur->next;LTNode* second = first->next;second->prev = phead;phead->next = second;free(first);
}

 删除时要注意不能删除哨兵位头节点，所以要断言一下，链表为空就不能再删了，我们也可以封装一个判断链表是否为空的函数ListEmpty():

bool ListEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

bool类型的返回值是true或者false。 

双向链表尾删：

尾删要保存尾节点的前一个节点，然后把前一个节点和头节点链接起来，free尾节点即可。

代码如下：

void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);
}

 注意：同头删一样，尾删也要判断是否为空链表。

 双向链表查找：

双向循环链表的查找和单链表的查找不同，遍历时从head的下一个节点开始，到head的上一个节点（即尾节点）结束，所以判断条件有所不同，注意区分。找到时，返回该节点位置。

代码如下：

LTNode* ListSearch(LTNode*phead,ListDatatype x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

双向链表在pos之前插入：

保存pos的前一个节点，把newnode的前后分别与pos的前一个节点和pos链接起来即可。

要测试该功能，可以配合查找函数，先找到pos。

代码如下：

void ListInsert(LTNode* pos, ListDatatype x)
{assert(pos);LTNode* newnode = BuyList(x);LTNode* posPrev = pos->prev;newnode->next = pos;newnode->prev = posPrev;posPrev->next = newnode;pos->prev = newnode;
}

这段代码可以直接在头插和尾插中复用，也就是说，我们要实现头插、尾插和任意位置插入，只用这一个函数就可以解决。

头插：

ListInsert(phead->next, x);

 尾插：

ListInsert(phead, x);

双向链表在pos位置删除：

配合查找函数先找到pos位置，然后删除就行。

代码如下：

void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

这段代码也可以同时实现头删、尾删和任意位置删除：

头删：
 

ListErase(phead->next);

 尾删：

ListErase(phead->prev);

 双向链表的销毁：

销毁也是从哨兵位的下一个节点开始，注意每次都要保存要销毁节点的后面一个节点的位置，防止找不到后面的节点，最终要把哨兵位也销毁掉。

代码如下：

void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

 以上就是双向链表的全部功能实现，下面给出完整代码：

3.完整代码：

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//测试
ListTest1()
{LTNode* plist = InitList();Print(plist);//头插ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);Print(plist);//尾插ListPushBack(plist, 5);ListPushBack(plist, 6);ListPushBack(plist, 7);ListPushBack(plist, 8);Print(plist);//头删ListPopFront(plist);ListPopFront(plist);Print(plist);//尾删ListPopBack(plist);ListPopBack(plist);Print(plist);//在pos位置之前插入LTNode* pos = ListSearch(plist, 1);if (pos != NULL)ListInsert(pos, 666);Print(plist);//在pos位置删除pos = ListSearch(plist, 6);if(pos!=NULL)ListErase(pos);Print(plist);
}
int main()
{ListTest1();return 0;
}

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int ListDatatype;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;ListDatatype data;
}LTNode;
//双向链表初始化
LTNode* InitList();
//双向链表打印
void Print(LTNode* phead);
//双向链表头插
void ListPushFront(LTNode* phead, ListDatatype x);
//双向链表尾插
void ListPushBack(LTNode* phead, ListDatatype x);
//双向链表头删
void ListPopFront(LTNode* phead);
//双向链表尾删
void ListPopBack(LTNode* phead);
//双向链表查找
LTNode* ListSearch(LTNode*phead,ListDatatype x);
//在pos位置之前插入
void ListInsert(LTNode*pos, ListDatatype x);
//在pos位置删除
void ListErase(LTNode* pos);
//销毁链表
void ListDestory(LTNode* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//开辟节点函数
LTNode* BuyList(ListDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->prev = NULL;newnode->next = NULL;newnode->data = x;return newnode;
}
//双向链表初始化
LTNode* InitList()
{LTNode* phead = BuyList(-1);phead->next = phead;phead->prev = phead;return phead;
}
//打印函数
void Print(LTNode* phead)
{LTNode*cur = phead->next;printf("guard<->");while (cur != phead){printf("%d<->", cur->data);cur = cur->next;}printf("\n");
}
//双向链表头插
void ListPushFront(LTNode* phead, ListDatatype x)
{assert(phead);LTNode* newnode = BuyList(x);LTNode* next = phead->next;phead->next = newnode;next->prev = newnode;newnode->next = next;newnode->prev = phead;/*ListInsert(phead->next, x);*/
}
//双向链表尾插
void ListPushBack(LTNode* phead, ListDatatype x)
{assert(phead);LTNode* newnode = BuyList(x);LTNode* tail = phead->prev;tail->next = newnode;phead->prev = newnode;newnode->prev = tail;newnode->next = phead;/*ListInsert(phead, x);*/
}
//判断空链表函数
bool ListEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//双向链表头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));LTNode* cur = phead;LTNode* first = cur->next;LTNode* second = first->next;second->prev = phead;phead->next = second;free(first);/*ListErase(phead->next);*/
}
//双向链表尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);/*ListErase(phead->prev);*/
}
//双向链表查找
LTNode* ListSearch(LTNode*phead,ListDatatype x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
//双向链表在pos之前插入
void ListInsert(LTNode* pos, ListDatatype x)
{assert(pos);LTNode* newnode = BuyList(x);LTNode* posPrev = pos->prev;newnode->next = pos;newnode->prev = posPrev;posPrev->next = newnode;pos->prev = newnode;
}
//双向链表在pos位置删除
void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}
//双向链表销毁
void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

4.测试：

5.顺序表和链表的区别

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

总结一下：

下面我们再来补充一些内容：

这里有个问题，在计算机中使用顺序表效率高还是使用链表效率高呢？

答案是：顺序表。

因为在计算机中，由于运行速度不匹配的问题，CPU不会直接和主存交换数据，而是先把数据从主存中取出来放到高速缓存中，然后再进行访问数据，而访问数据会出现两种情况：

1.如果数据在缓存中，就叫做缓存命中，可以直接访问。

2.如果数据不在缓存中，就叫做缓存不命中，这时候需要先把数据加载到缓存中，然后再访问数据。

当缓存不命中时，计算机会把数据加载到缓存中，而加载时会将这个数据后面的数据也一起加载进去（局部性原理），如果是顺序表，因为它的内存空间是连续的，后面的数据会直接命中，这样它的缓存命中率就高；如果是链表，它一旦命中不了，也会加载一段数据，但是这些数据不一定会用，这就造成了浪费，还会导致数据污染，这样它的缓存命中率就低了。

这就是今天关于双向链表的全部内容了，未完待续。。。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

指标体系：洞察变化的原因

指标体系：洞察变化的原因

一、指标概述 指标体系是指根据运营目标&#xff0c;整理出可以正确和准确反映业务运营特点的多个指标&#xff0c;并根据指标间的联系形成有机组合。 指标体系业务意义极强&#xff0c;所有指标体系都是为特定的业务经营目的而设计的。指标体系的设计应服从于这种目的&#x…
阅读更多...
【数据结构】二叉树经典例题---＜你真的掌握二叉树了吗？＞(第一弹)

【数据结构】二叉树经典例题---＜你真的掌握二叉树了吗？＞(第一弹)

一、已知一颗二叉树如下图&#xff0c;试求&#xff1a; (1)该二叉树前序、中序和后序遍历的结果。 (2)该二叉树是否为满二叉树&#xff1f;是否为完全二叉树&#xff1f; (3)将它转换成对应的树或森林。 (4)这颗二叉树的深度为多少? (5)试对该二叉树进行前序线索化。 (6)试对…
阅读更多...
算法之双指针

算法之双指针

双指针算法的作用 双指针算法是一种使用2个变量对线性结构(逻辑线性/物理线性)&#xff0c;进行操作的算法&#xff0c;双指针可以对线性结构进行时间复杂度优化&#xff0c;可以对空间进行记忆。 双指针算法的分类 1.快慢指针 2.滑动窗口 3.左右指针 4.前后指针 双指针OJ题目…
阅读更多...
docker可视化

docker可视化

什么是portainer&#xff1f; portainer就是docker图形化界面的管理工具&#xff0c;提供一个后台面板供我们操作 目前先用portainer(先用这个)&#xff0c;以后还会用到Rancher(CI/CD在用) 1.下载portainer 9000是内网端口&#xff0c;8088是外网访问端口 docker run…
阅读更多...
Linux文件系统(1)

Linux文件系统(1)

Linux文件系统(1) &#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容从系统层面重新认识我们的文件系统 文…
阅读更多...
每日一题(LeetCode)----数组--长度最小的子数组

每日一题(LeetCode)----数组--长度最小的子数组

每日一题(LeetCode)----数组–长度最小的子数组 1.题目&#xff08; 209.长度最小的子数组&#xff09; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &…
阅读更多...
【入门Flink】- 10基于时间的双流联合（join）

【入门Flink】- 10基于时间的双流联合（join）

统计固定时间内两条流数据的匹配情况&#xff0c;需要自定义来实现——可以用窗口&#xff08;window&#xff09;来表示。为了更方便地实现基于时间的合流操作&#xff0c;Flink 的 DataStrema API 提供了内置的 join 算子。 窗口联结&#xff08;Window Join&#xff09; 一…
阅读更多...
JavaScript_动态表格_添加功能

JavaScript_动态表格_添加功能

1、动态表格_添加功能.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>动态表格_添加功能</title><style>table{border: 1px solid;margin: auto;width: 100%;}td,th{text-align: ce…
阅读更多...
SOME/IP 协议介绍（四）RPC协议规范

SOME/IP 协议介绍（四）RPC协议规范

RPC协议规范 本章描述了SOME/IP的RPC协议。 传输协议绑定 为了传输不同传输协议的SOME/IP消息&#xff0c;可以使用多种传输协议。SOME/IP目前支持UDP和TCP。它们的绑定在以下章节中进行了解释&#xff0c;而第[SIP_RPC_450页&#xff0c;第36页]节讨论了选择哪种传输协议。…
阅读更多...
【Go入门】面向对象

【Go入门】面向对象

【Go入门】面向对象 前面两章我们介绍了函数和struct&#xff0c;那你是否想过函数当作struct的字段一样来处理呢&#xff1f;今天我们就讲解一下函数的另一种形态&#xff0c;带有接收者的函数&#xff0c;我们称为method method 现在假设有这么一个场景&#xff0c;你定义…
阅读更多...
Linux驱动开发——PCI设备驱动

Linux驱动开发——PCI设备驱动

目录 一、 PCI协议简介 二、PCI和PCI-e 三、Linux PCI驱动 四、 PCI设备驱动实例 五、 总线类设备驱动开发习题 一、 PCI协议简介 PCI (Peripheral Component Interconnect&#xff0c;外设部件互联) 局部总线是由Intel 公司联合其他几家公司一起开发的一种总线标准&#…
阅读更多...
前端开发引入element plus与windi css

前端开发引入element plus与windi css

背景 前端开发有很多流行框架&#xff0c;像React 、angular、vue等等&#xff0c;本文主要讲vue 给新手用的教程&#xff0c;其实官网已经写的很清楚&#xff0c;这里再啰嗦只是为了给新手提供一个更加简单明了的参考手册。 一、打开element plus官网选则如图所示模块安装命令…
阅读更多...
Nginx缓存基础

Nginx缓存基础

1 nginx缓存的流程 客户端需要访问服务器的数据时&#xff0c;如果都直接向服务器发送请求&#xff0c;服务器接收过多的请求&#xff0c;压力会比较大&#xff0c;也比较耗时&#xff1b;而如果在nginx缓存一定的数据&#xff0c;使客户端向基于nginx的代理服务器发送请求&…
阅读更多...
华为L410上制作内网镜像模板02

华为L410上制作内网镜像模板02

原文链接&#xff1a;华为L410上制作离线安装软件模板02 hello&#xff0c;大家好啊&#xff0c;今天给大家带来第二篇在内网搭建Apache服务器&#xff0c;用于安装完内网操作系统后&#xff0c;在第一次开机时候&#xff0c;为系统安装软件的文章&#xff0c;今天给大家介绍在…
阅读更多...
Linux之基础开发工具gdb调试器的使用（三）

Linux之基础开发工具gdb调试器的使用（三）

文章目录 一、Linux调试器-gdb使用1、安装gdb2、背景3、Debug和release4、区分Debug和release 二、Linux调试器-gdb命令演示1、显示指定行之后的代码&#xff08;自动记录最后一条指令&#xff09;2、断点1、打印断点2、查看断点3、删除断点4、使能&#xff08;禁用/开启&#…
阅读更多...
StartUML的基本使用

StartUML的基本使用

文章目录 简介和安装创建包创建类视图时序图 简介和安装 最近在学习一个项目的时候用到了StartUML来构造项目的类图和时序图 虽然vs2019有类视图&#xff0c;但是也不是很清晰&#xff0c;并没有生成uml图&#xff0c;但是宇宙最智能的IDE IDEA有生成uml图的功能 下面就简单介…
阅读更多...
Flowable 外部表单

Flowable 外部表单

内置表单需要在每个节点中去配置&#xff0c;当如果多个节点使用同一套表单属性就要配置多次比较麻烦&#xff0c;修改的时候也要修改多次&#xff0c;外部表单可以定义一次&#xff0c;然后其它节点都去引用同一个表单属性。 外部表单需要定义一个.form后缀的文件。 外部表单…
阅读更多...
关于值传递和引用传递的问题记录

关于值传递和引用传递的问题记录

目录 1. 问题概述 1.1 测试 1.2 结果 2. ArrayList和Arrays.ArrayList 1. 问题概述 最近忙着写论文很久没更新了&#xff0c;趁现在有时间简单记录一下最近遇到的一个坑。 对于Java中的List<>类型的对象&#xff0c;按我以前理解是引用传递&#xff0c;但有一点要注…
阅读更多...
Excel中使用数据验证、OFFSET实现自动更新式下拉选项

Excel中使用数据验证、OFFSET实现自动更新式下拉选项

在excel工作簿中&#xff0c;有两个Sheet工作表。 Sheet1&#xff1a; Sheet2&#xff08;数据源表&#xff09;&#xff1a; 要实现Sheet1中的“班级”内容&#xff0c;从数据源Sheet2中获取并形成下拉选项&#xff0c;且Sheet2中“班级”内容更新后&#xff0c;Sheet1中“班…
阅读更多...
SMART PLC MODBUSTCP速度测试

SMART PLC MODBUSTCP速度测试

SMART PLC MODBUSTCP通信详细介绍请参看下面文章链接： S7-200SMART PLC ModbusTCP通信（多服务器多从站轮询）_matlab sumilink 多个modbustcp读写_RXXW_Dor的博客-CSDN博客文章浏览阅读6.4k次，点赞5次，收藏10次。MBUS_CLIENT作为MODBUS TCP客户端通过S7-200 SMART CPU上的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023