您的位置:首页 > 教育 > 锐评 > 【数据结构初阶】千字文章带你征服 “ 双向链表 ”(附源码)

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

2024/10/6 12:34:58 来源:https://blog.csdn.net/lrq13965748542/article/details/140793414  浏览:    关键词:【数据结构初阶】千字文章带你征服 “ 双向链表 ”(附源码)

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

至此,结束——

我是云边有个稻草人

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com