数据结构——双向链表的实现

news/2025/1/17 21:46:30/

一、双向链表的结构

注意：双向链表又称带头双向循环链表
这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨 的”
“哨兵位”存在的意义： 遍历循环链表避免死循环。
双向链表每个节点储存一个有效数据+前驱指针+后继指针

二、. 双向链表的实现

2.1 创建&初始化

2.2.1  List.h

#pragma once
typedef struct ListNode
{int val;struct ListNode* next;struct  ListNode* prev;}LTNode; //初始化
LTNode* LTInit();

2.2.2  List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
LTNode* LTInit()//哨兵位初始化
{LTNode* head = (LTNode*)malloc(sizeof(LTNode));head->val = -1;head->next = head->prev =head;return head;
}

2.2.3 text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();return 0;
}

代码运行测试：

2.2尾插&头插

分析：

尾插
1.往d3节点的后面插入数据叫做尾插  

 2.往哨兵位head之前插入数据也叫尾插 

 

头插

在哨兵位和头节点之间插入

2.2.1  List.h

//尾插
//1.往d3节点的后面插入数据叫做尾插    2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);

2.2.2  List.c

//创建新节点
LTNode* Listbuynode(int x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->val = x;node->next = node->prev = NULL;return node;
}
void LTPushBack(LTNode* head, int x)
{LTNode* node = Listbuynode(x);//对新节点进行操作node->next = head;node->prev = head->prev;//对原来的尾节点和哨兵位进行操作head->prev->next = node;head->prev = node;
}
void LTPrint(LTNode* head)
{assert(head);LTNode* pcur = head->next;while (pcur != head){printf("%d->", pcur->val);pcur = pcur->next;}printf("\n");
}void LTPushFront(LTNode* head, int x)
{LTNode* node = Listbuynode(x);//对新节点进行操作node->next = head->next;node->prev = head;//对哨兵位和头节点进行操作head->next->prev = node;head->next = node;
}

2.2.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head,4);//4->1->2->3LTPrint(head);return 0;
}

2.3  头删&尾删

2.3.1  List.h

//尾删
void LTPopBack(LTNode* head);//头删
void LTPopFront(LTNode* head);

2.3.2  List.c

void LTPopBack(LTNode* head)
{//链表为空不能删除assert(head);assert(head->next != head);//将尾节点进行保存LTNode* del = head->prev;//连接次尾节点和哨兵位del->prev->next = head;head->prev = del->prev;free(del);del = NULL;}
void LTPopFront(LTNode* head)
{//链表为空不能删除assert(head);assert(head->next != head);//将头节点进行保存LTNode* del = head->next;//连接哨兵位和次头节点head->next = del->next;del->next->prev = head;free(del);del = NULL;
}

2.3.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);LTPrint(head);//4->1->2->3LTPopFront(head);LTPrint(head);//1->2->3LTPopBack(head);LTPrint(head);1->2return 0;
}

2.4  查找数据&在pos节点后插入数据&删除pos节点

2.4.1  List.h


//在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);//查找数据
LTNode* LTFind(LTNode* head, int x);

2.4.2  List.c

void LTInsert(LTNode* pos, int x)
{assert(pos);LTNode* node = Listbuynode(x);//先处理新节点node->prev = pos;node->next = pos->next;//在处理前后节点pos->next = node;node->next->prev = node;
}LTNode* LTFind(LTNode* head, int x)
{assert(head);assert(head->next!=head);LTNode* pcur = head->next;while (pcur != head){if (pcur->val == x){return pcur;}pcur = pcur->next;}return NULL;
}
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.4.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushBack(head, 4);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find = LTFind(head, 4);LTInsert(find, 11);LTPrint(head);//1->2->3->4->11LTErase(find);//1->2->3->11LTPrint(head);return 0;
}

2.5  销毁

若销毁接口用二级指针接受，传哨兵位指针的地址，那么可以改变哨兵位（指针指向）,使哨兵位指向NULL;

若销毁接口用一级指针接受，传一级指针（哨兵位指针），传过去的形参（是指针存储的地址），不能够改变指针的指向，在对形参操作，可以释放哨兵位指向的地址空间（形参的值为空间地址），但是不能改变实参指针的指向（实参依然指向原来被释放的地址空间），需要手动将实参置为NULL.

简而言之，若需要改变一级指针指向，需要传二级指针。

前面都是用一级指针传参，为了保持接口的一致性，我们用一级指针传参

2.5.1  List.h

//销毁
void LTDestroy(LTNode* phead);

2.5.2  List.c

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = pcur->next;while (pcur != phead){free(pcur);pcur = next;next = next->next;}free(phead);phead = NULL;
}

2.5.3  text.c 

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);/*LTPrint(head);LTPopFront(head);*/LTPrint(head);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find = LTFind(head, 4);/*LTInsert(find, 11);*/LTErase(find);LTPrint(head);LTDestroy(head);head = NULL;return 0;
}

2.6  完整代码

2.6.1  List.h

#pragma once
typedef struct ListNode
{int val;struct ListNode* next;struct  ListNode* prev;}LTNode; //初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
//1.往d3节点的后面插入数据叫做尾插    2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);//尾删
void LTPopBack(LTNode* head);//头删
void LTPopFront(LTNode* head);//在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);//查找数据
LTNode* LTFind(LTNode* head, int x);

2.6.2  List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
LTNode* LTInit()//哨兵位初始化
{LTNode* head = (LTNode*)malloc(sizeof(LTNode));head->val = -1;head->next = head->prev =head;return head;
}
//创建新节点
LTNode* Listbuynode(int x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->val = x;node->next = node->prev = NULL;return node;
}
void LTPushBack(LTNode* head, int x)
{LTNode* node = Listbuynode(x);//对新节点进行操作node->next = head;node->prev = head->prev;//对原来的尾节点和哨兵位进行操作head->prev->next = node;head->prev = node;
}
void LTPrint(LTNode* head)
{assert(head);LTNode* pcur = head->next;while (pcur != head){printf("%d->", pcur->val);pcur = pcur->next;}printf("\n");
}void LTPushFront(LTNode* head, int x)
{LTNode* node = Listbuynode(x);//对新节点进行操作node->next = head->next;node->prev = head;//对哨兵位和头节点进行操作head->next->prev = node;head->next = node;
}
void LTPopBack(LTNode* head)
{//链表为空不能删除assert(head);assert(head->next != head);//将尾节点进行保存LTNode* del = head->prev;//连接次尾节点和哨兵位del->prev->next = head;head->prev = del->prev;free(del);del = NULL;}
void LTPopFront(LTNode* head)
{//链表为空不能删除assert(head);assert(head->next != head);//将头节点进行保存LTNode* del = head->next;//连接哨兵位和次头节点head->next = del->next;del->next->prev = head;free(del);del = NULL;
}void LTInsert(LTNode* pos, int x)
{assert(pos);LTNode* node = Listbuynode(x);//先处理新节点node->prev = pos;node->next = pos->next;//在处理前后节点pos->next = node;node->next->prev = node;
}LTNode* LTFind(LTNode* head, int x)
{assert(head);assert(head->next!=head);LTNode* pcur = head->next;while (pcur != head){if (pcur->val == x){return pcur;}pcur = pcur->next;}return NULL;
}
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = pcur->next;while (pcur != phead){free(pcur);pcur = next;next = next->next;}free(phead);phead = NULL;
}

2.6.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{LTNode* head;head=LTInit();LTPushBack(head, 1);LTPushBack(head, 2);LTPushBack(head, 3);LTPushFront(head, 4);/*LTPrint(head);LTPopFront(head);*/LTPrint(head);//LTPopBack(head);//LTPrint(head);//LTPopBack(head);LTNode* find = LTFind(head, 4);/*LTInsert(find, 11);*/LTErase(find);LTPrint(head);LTDestroy(head);head = NULL;return 0;
}

三、顺序表和双向链表的优缺点分析

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


http://www.ppmy.cn/news/1187061.html

相关文章

halcon canny 和opencv c++ canny 实现对比

halcon canny 和opencv c++ canny 实现对比

Opencv和C实现canny边缘检测_opencv边缘增强-CSDN博客 一、canny实现步骤 1、图像必须是单通道的&#xff0c;也就是说必须是灰度图像 2、图像进行高斯滤波&#xff0c;去掉噪点 3、sobel 算子过程的实现&#xff0c;计算x y方向 、梯度&#xff08;用不到&#xff0c;但是…
阅读更多...
day55--动态规划13

day55--动态规划13

300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组 第一题&#xff1a;最长递增子序列 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而…
阅读更多...
腾讯云轻量应用服务器“镜像”怎么选择合适？

腾讯云轻量应用服务器“镜像”怎么选择合适？

腾讯云轻量应用服务器镜像怎么选择&#xff1f;如果是用来搭建网站可以选择宝塔Linux面板腾讯云专享版&#xff0c;镜像系统根据实际使用来选择&#xff0c;腾讯云百科txybk.com来详细说下腾讯云轻量应用服务器镜像的选择方法&#xff1a; 腾讯云轻量应用服务器镜像选择 轻量…
阅读更多...
Linux mv命令：移动文件或改名

Linux mv命令：移动文件或改名

mv 命令&#xff08;move 的缩写&#xff09;&#xff0c;既可以在不同的目录之间移动文件或目录&#xff0c;也可以对文件和目录进行重命名。该命令的基本格式如下&#xff1a; [rootlocalhost ~]# mv 【选项】 源文件 目标文件 -f&#xff1a;强制覆盖&#xff0c;如果目标文…
阅读更多...
部署私有仓库(笔记docker应用)

部署私有仓库(笔记docker应用)

二&#xff1a;部署私有仓库 docker pull daocloud.io/library/registry:latest docker run --restartalways -d -p 5000:5000 daocloud.io/library/registry systemctl stop firewalld systemctl restart docker 宿主机ip端口 curl -I 127.0.0.1:5000 将镜像存放在仓…
阅读更多...
稿C语言基础 -- scanf函数的工作原理

稿C语言基础 -- scanf函数的工作原理

一、前言、基本概念和术语 在C语言中&#xff0c;输入主要是靠标准输入函数&#xff0c;也就是scanf函数来完成的。要正确的调用scanf函数来完成输入&#xff0c;需要了解scanf的工作原理。为了讲清楚原理&#xff0c;我先铺垫一下&#xff0c;介绍几个概念。 &#xff08;1&…
阅读更多...
http1,https,http2,http3总结

http1,https,http2,http3总结

1.HTTP 当我们浏览网页时&#xff0c;地址栏中使用最多的多是https://开头的url&#xff0c;它与我们所学的http协议有什么区别&#xff1f; http协议又叫超文本传输协议&#xff0c;它是应用层中使用最多的协议&#xff0c; http与我们常说的socket有什么区别吗&#xff1f; …
阅读更多...
Egg.js使用MySql数据库

Egg.js使用MySql数据库

最近在接手一个项目&#xff0c;vuenuxtegg&#xff0c;我也是刚开始学习egg.js&#xff0c;所以会将自己踩的坑都记录下来。 安装mysql 使用sequelize连接数据库&#xff0c;首先安装egg-sequelize和mysql2。 npm install --save egg-sequelize mysql2打开package.json文件…
阅读更多...
最新文章

Copyright @ 2022~2023