【数据结构初阶】千字文章带你征服 “ 双向链表 ”(附源码)

devtools/2024/11/14 19:52:23/

hi，bro！又见面啦

目录

前言：

一、链表的分类

二、双向链表

1、  概念与结构

2、  双向链表的实现

2.1  定义双向链表的结构

2.2  初始化

2.3  尾插

2.4  头插

2.5  打印

2.6  尾删

2.7  头删

2.8  查找

2.9  在pos结点之后插入结点

2.10  删除指定位置结点

2.11  销毁

2.12  销毁2

2.13  初始化2

3、源码

List.h

List.c 

test.c 

三、顺序表和链表的比较

Bye Bye Bye ————————

前言：

前面我们学习了单链表，单链表是链表的一种，今天我们即将要学习的双向链表也是其中之一。我们前面没有具体介绍链表的分类，所以在学习双向链表之前，先了解下链表的分类。

一、链表的分类

链表的结构多样，有下面8种链表结构（2×2×2）： 

链表说明：

何为循环：尾结点的next指针不为NULL

链表结构虽多，我们常用的就两种结构，单链表和双向带头循环链表

  • 无头单向非循环链表（单链表）：结构简单，一般不用来单独存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 带头双向循环链表（双向链表）：结构最复杂，一般用在单独存储数据，实际中使用的链表数据结构，都是带头双向循环链表。虽然这个结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
  • 在带头链表里面，除了头结点（哨兵位），其他结点都存储有效的数据。

二、双向链表

1、  概念与结构

带头双向循环链表

双向链表的结点结构：数据 + 指向后一个结点的指针 + 指向前一个节点的指针 

struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}

头结点的prev指针指向尾结点，尾结点的next指针指向头结点，就这样实现了循环。 

【注意】 带头链表的头结点实际为 哨兵位 ，哨兵位结点不存储任何有效数据，只是在这里放哨占位子的。而前面单链表里面的头结点并不表示真的表示有头结点，而是为了表示方便，这种表述是不规范的。单链表里面的第一个结点并非真的头结点。

2、  双向链表的实现

2.1  定义双向链表的结构

//定义双向链表的结构
typedef int LTDataType ;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2.2  初始化

//创建新结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc file!");exit(1);}newnode->data = x;//等于自身,实现循环newnode->next = newnode->prev = newnode;return newnode;}//初始化
void LTInit(LTNode** pphead)
{//创建新结点*pphead = LTBuyNode(-1);
}

双向链表为空：表示只有一个哨兵位。

2.3  尾插

第一个结点：第一个有效的结点，里面存储有效的数据。

哨兵位：头结点。

//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会发生改变
//如果发生改变，那么phead的改变要影响实参，传二级
//如果不发生改变，那么phead不会影响实参，传一级
//phead指向的结点是哨兵位，不会发生改变，故传一级//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->prevnewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;}

2.4  头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2.5  打印

//打印
void LTPrint(LTNode* phead)
{assert(phead);//从第一个有效的结点开始打印LTNode* pcur = phead->next;while (pcur!=phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.6  尾删

//判空
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;//phead del(phead->prev) prev(del->prev)phead->prev = prev;prev->next = phead;free(del);del = NULL;
}

2.7  头删

//头删
void LTPopFront(LTNode* phead)
{assert(phead);//在头删之前要判空assert(!LTEmpty(phead));LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

2.8  查找

//查找
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;
}

2.9  在pos结点之后插入结点

//在pos结点之后插入数据
void LTInsert(LTNode* phead, LTNode* pos,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(100);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}

2.10  删除指定位置结点

//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos)
{assert(phead);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}

为了保持接口的一致性，优化接口都为一级指针，见下：

2.11  销毁

//销毁
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;
}

2.12  销毁2

//销毁2
void LTDesTroy2(LTNode* phead)  //传一级指针，需要手动将plist置为空
{assert(phead);LTNode* pcur = phead->next;while (pcur!=phead){		LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);phead = NULL;pcur = NULL;}

2.13  初始化2

用返回值的方式实现

//初始化2
LTNode* LTInit2()
{LTNode* phead = LTBuyNode(-1);return phead;
}

3、源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义双向链表的结构
typedef int LTDataType ;
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
void LTInit(LTNode** pphead);//尾插
void LTPushBack(LTNode* phead,LTDataType x);//头插
void LTPushFront(LTNode* phead,LTDataType x);//打印
void LTPrint(LTNode* phead);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead,LTDataType x);//在pos结点之后插入数据
void LTInsert(LTNode* phead,LTNode* pos,LTDataType x);//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos);//销毁
void LTDesTroy(LTNode** pphead);//销毁
void LTDesTroy2(LTNode* phead);//初始化2
LTNode* LTInit2();

List.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"//创建新结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc file!");exit(1);}newnode->data = x;//等于自身,实现循环newnode->next = newnode->prev = newnode;return newnode;}//初始化
void LTInit(LTNode** pphead)
{//创建新结点*pphead = LTBuyNode(-1);
}//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会发生改变
//如果发生改变，那么phead的改变要影响实参，传二级
//如果不发生改变，那么phead不会影响实参，传一级
//phead指向的结点是哨兵位，不会发生改变，故传一级//尾插
void LTPushBack(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->prevnewnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);//从第一个有效的结点开始打印LTNode* pcur = phead->next;while (pcur!=phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//判空
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;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);//在头删之前要判空assert(!LTEmpty(phead));LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;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;
}//在pos结点之后插入数据
void LTInsert(LTNode* phead, LTNode* pos,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(100);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}//删除指定位置结点
void LTErase(LTNode* phead, LTNode* pos)
{assert(phead);//pos->prev pos pos->nextpos->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 LTDesTroy2(LTNode* phead)  //传一级指针，需要手动将plist置为空
{assert(phead);LTNode* pcur = phead->next;while (pcur!=phead){		LTNode* Next = pcur->next;free(pcur);pcur = Next;}free(phead);phead = NULL;pcur = NULL;}//初始化2
LTNode* LTInit2()
{LTNode* phead = LTBuyNode(-1);return phead;
}

test.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"void ListTest01()
{LTNode* plist = NULL;//双向链表头结点不能为空，要初始化LTInit(&plist);LTNode* plist = LTInit2();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPushFront(plist, 6);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos == NULL){printf("没有找到\n");}else{printf("找到了\n");}LTInsert(plist, pos, 100);LTPrint(plist);LTErase(plist,pos);LTPrint(plist);LTDesTroy(&plist);//此时plist为野指针，虽然保存的有地址，但其中的地址已被释放LTDesTroy2(plist);plist = NULL;
}int main()
{ListTest01();return 0;
}

三、顺序表和链表的比较

    不同点顺序表链表（单链表）
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问O（1）O（N）
任意位置插入或者删除数据可能需要搬移元素，效率低只需改变指针指向
插入动态顺序表，空间不够时需要扩容，可能会发生空间浪费没有容量的概念，按需申请释放，不存在空间浪费
应用场景元素高效存储+频繁访问任意位置高效插入和删除

今天双向链表的学习就结束了，休息一下吧。

完——

Bye Bye Bye ————————

Bye Bye Bye_*NSYNC_高音质在线试听_Bye Bye Bye歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由*NSYNC演唱的高清音质无损Bye Bye Byemp3在线听,听Bye Bye Bye,只来酷狗音乐!icon-default.png?t=N7T8https://t4.kugou.com/song.html?id=dzeLrbfCPV2

至此，结束——

我是云边有个稻草人

期待与你的下一次相遇 。。。。。。


http://www.ppmy.cn/devtools/86448.html

相关文章

EEtrade：区块链是什么

EEtrade：区块链是什么

区块链&#xff0c;这个近年来频繁出现在我们视野中的术语&#xff0c;已经从一个技术小众圈的词汇&#xff0c;逐渐演变为全球关注的焦点。从比特币的诞生&#xff0c;到如今在金融、供应链、物联网等领域的广泛应用&#xff0c;区块链技术正在深刻地改变着我们的生活。那么&a…
阅读更多...
循环神经网络LSTM

循环神经网络LSTM

循环神经网络LSTM LSTM模型单元 LSTM与RNN两个神经网络运行方式相同&#xff0c;但单元结构不同 LSTM的单元结构较RNN复杂一些&#xff0c;因此运行时间较长&#xff0c;但性能比较好 如下&#xff0c;就是LSTM神经网络的一个单元 LSTM单元中包含四个交互的层&#xff0c;即…
阅读更多...
R语言 爬取数据+简单清洗

R语言 爬取数据+简单清洗

小小练习。见代码注释 # 加载必要的包 library(rvest) library(dplyr) library(tidyr)# 指定网页URL url <- "https://research.un.org/en/unmembers/scmembers"# 读取网页内容 webpage <- read_html(url)# 提取所有表格节点 table_nodes <- html_nodes(web…
阅读更多...
基于SpringBoot+Vue的漫画网站(带1w+文档)

基于SpringBoot+Vue的漫画网站(带1w+文档)

基于SpringBootVue的漫画网站(带1w文档) 基于SpringBootVue的漫画网站(带1w文档) 在漫画信息管理方面还有许多改进。实际上如今信息化成为一个未来的趋势或者可以说在当前现代化的城市典范中,信息化已经成为主流,开发一个漫画网站一方面的可能会更合乎时宜,另一方面来说也可以提…
阅读更多...
FFmpeg研究

FFmpeg研究

1.FFmpeg介绍 FFmpeg的全称是“Fast Forward Moving Picture Expert Group”&#xff0c;组件由命令行应用程序和函数库两部分组成。通俗概括来说&#xff0c;FFmpeg 是一个免费的开源程序库&#xff0c;一个多媒体音视频处理分析工具软件&#xff0c;且提供命令行方式调用&am…
阅读更多...
面向对象编程：一切皆对象

面向对象编程：一切皆对象

面向对象(OOP)是一种编程范式,它使用对象来设计软件。对象可以包含数据和代码&#xff1a;数据代表对象的状态&#xff0c;而代码代表操作数据的方式。在面向对象编程中&#xff0c;一切皆对象&#xff0c;这意味着将现实世界事务使用类与实例来模拟&#xff0c;如灯&#xff0…
阅读更多...
Cocos Creator2D游戏开发-(1)初始化设置

Cocos Creator2D游戏开发-(1)初始化设置

初心: 做一款微信或者抖音小游戏,然后发布,对于我来说这是一个新的赛道; 写这些文档的原因,记录一下自己学习过程,下次用的时候方便找 cocos creator版本: 3.8.3 当前小游戏飞机大战教程来源于: 抖音: 禅影 chanying001 源码目录: https://www.kdocs.cn/l/caLr6XCbEfPa 创建一个…
阅读更多...
数据结构——双向链表

数据结构——双向链表

目录 一、链表的分类 (1)单向或双向​编辑 &#xff08;2&#xff09;带头或不带头​编辑 &#xff08;3&#xff09;循环或不循环​编辑 &#xff08;4&#xff09;补充 二、实现双向链表 &#xff08;1&#xff09;List.h (2)List.c (3)注意 三、顺序表和链表的比较 四…
阅读更多...
最新文章

Copyright @ 2022~2023