当前位置： 首页 > ds >正文

【数据结构】双向循环链表的实现

ds 2025/7/21 16:24:34

目录

1 双向循环链表的结构

2 双向链表的实现 

2.1 双向循环链表的节点

 2.2 申请一个节点

2.3双向链表的尾插

 2.4 双向链表的头插

2.5 双向链表的尾删 

2.6 双向链表的头删

 2.7 查找数据的位置

2.8 在指定位置之后插入数据

 2.9 删除指定位置节点

2.10 双向链表的打印 

2.11 销毁链表

3 双向循环链表的完整代码

3.1 LIst.h文件 

3.2 List.c文件

3.3 test.c文件

1 双向循环链表的结构

这是一个带头双向循环链表，第一个节点是链表的头节点，也称为“哨兵位”，哨兵位节点不储存任何有效元素，哨兵位存在的意义是避免遍历循环链表时出现死循环。每一个节点都有指向前一个节点和下一个节点的指针，这意味着双向循环链表既可以从前往后遍历，又可以从后往前遍历。

2 双向链表的实现 

2.1 双向循环链表的节点

在了解了双向循环链表的结构后，已知一个节点由数据、指向前一个节点的指针、指向下一个节点的指针三个部分组成，所以需要把这三个要素放在结构体内，定义一个节点代码如下：

typedef int LTDataType;//方便替换数据类型
//定义双向链表节点
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;

 2.2 申请一个节点

定义了一个节点后，当我们要给链表进行插入节点的操作时，就要去申请一个新的节点，这时就需要利用动态内存开辟，申请一个结构体大小的空间，从而创建一个节点。然后给里面的数据进行赋值，两个指针暂时让其指向自己，代码如下：

//申请一个节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->data = x;node->next = node->prev = node;//申请一个节点，让其自循环return node;
}

有了申请节点的代码后，我们就可以创建双向循环链表了，需要先申请一个头节点，并且进行初始化操作：

//双向链表的初始化
void LTInit(LTNode** pphead)
{//给双向链表单独创建一个哨兵位*pphead = LTBuyNode(-1);
}

这里给头节点的数据随便设置一个值，以后不再更改哨兵位。因为要修改哨兵位的数据，因此调用函数时需要传节点的地址，而一个节点的数据类型是LTNode*，因此传地址后，函数参数就需要用二级指针来接收。

2.3双向链表的尾插

双向链表的尾插就是在链表尾部插入一个新的节点，也可以说是将新节点插入到头节点的前面。这时头节点的前指针就要指向新的节点，新节点的后指针指向头节点，前指针指向最后一个节点，最后一个节点的后指针指向新节点。

代码如下：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// phead(哨兵位) phead->prev(原链表的尾节点) newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

 2.4 双向链表的头插

双向链表的头插就是将新节点插入到头节点的后面，新节点的前指针指向头节点，后指针指向d1，d1的前指针指向新节点，头节点的后指针指向新节点，完成双向链表的头插。

 代码如下：

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

2.5 双向链表的尾删 

双向链表的尾删就是删除最后一个节点，头结点的后指针指向d2，d2的前指针指向头节点。

代码如下：

//双向链表的尾删
void LTPopBack(LTNode* phead)
{//链表不能为空assert(phead&&phead->next!=phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.6 双向链表的头删

双向链表的头删就是删除d1节点，d2的前指针指向头节点，头节点后指针指向d2

代码如下：

//双向链表的头删
void LTPopFront(LTNode* phead)
{//链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

 2.7 查找数据的位置

定义一个临时指针变量pcur，指向头节点的下一个节点，向后遍历，循环条件设为不超过尾节点，如果找到，返回pcur。

代码如下：

//查找数据位置
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.8 在指定位置之后插入数据

在指定pos位置之后插入数据，新节点前指针指向d3，后指针指向头节点，头节点前指针指向新节点，d3后指针指向新节点。

代码实现：

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

 2.9 删除指定位置节点

删除pos节点，pos的前一个节点的后指针指向pos的下一个节点，pos的下一个节点的前指针指向pos的前一个节点，然后释放pos节点

 代码如下：

//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.10 双向链表的打印 

定义一个临时指针变量pcur，指向头节点的下一个节点，遍历链表，打印每个节点的数据

代码如下：

//双向链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.11 销毁链表

链表使用完成后，要进行销毁，将空间还给操作系统：

//销毁链表
void LTDesTory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;
}

3 双向循环链表的完整代码

实现双向循环链表，需要创建一个头文件LIst.h，一个源文件List.c，用来实现双向链表的功能，一个测试文件test.c，用来测试代码。文件结构：

3.1 LIst.h文件 

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;//方便替换数据类型
//定义双向链表节点
typedef struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}LTNode;//双向链表的初始化
void LTInit(LTNode** pphead);
//双向链表的打印
void LTPrint(LTNode* phead);
//插入数据之前，链表必须初始化到只有一个头结点的情况
// 不改变哨兵位的地址，因此传一级指针即可
//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x);
//双向链表的尾删
void LTPopBack(LTNode* phead);
//双向链表的头删
void LTPopFront(LTNode* phead);
//查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos 位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁链表
void LTDesTory(LTNode* phead);

3.2 List.c文件

#include "List.h"//申请一个节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->data = x;node->next = node->prev = node;//申请一个节点，让其自循环return node;
}
//双向链表的初始化
void LTInit(LTNode** pphead)
{//给双向链表单独创建一个哨兵位*pphead = LTBuyNode(-1);
}
//双向链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// phead(哨兵位) phead->prev(原链表的尾节点) newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
//双向链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//双向链表的尾删
void LTPopBack(LTNode* phead)
{//链表不能为空assert(phead&&phead->next!=phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//双向链表的头删
void LTPopFront(LTNode* phead)
{//链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;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* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
//销毁链表
void LTDesTory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;
}

3.3 test.c文件

#include "List.h"void ListTest01()
{//双向链表初始化测试LTNode* plist = NULL;LTInit(&plist);//双向链表尾插测试LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//双向链表头插测试LTPushFront(plist, 5);LTPushFront(plist, 6);LTPushFront(plist, 7);LTPushFront(plist, 8);LTPrint(plist);//双向链表尾删测试//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPrint(plist);//双向链表头删测试LTPopFront(plist);LTPopFront(plist);LTPopFront(plist);LTPopFront(plist);LTPrint(plist);//双向链表pos之后插入数据测试LTNode* find = LTFind(plist, 1);LTInsert(find, 99);LTPrint(plist);//删除pos节点测试LTErase(find);LTPrint(plist);find = NULL;//销毁链表LTDesTory(plist);plist = NULL;
}
int main()
{ListTest01();return 0;
}

以上就是有关双向循环链表的实现的知识，如果这篇文章对你有用，可以点点赞哦，你的支持就是我写下去的动力，后续会不断的分享知识。

http://www.xdnf.cn/news/16041.html

相关文章：

  • 基于机器视觉的迈克耳孙干涉环自动计数系统设计与实现
  • Node.js：函数、路由、全局对象
  • Docker Compose 配置
  • 如何5分钟快速搭建智能问答系统
  • 详解如何解决Mysql主从复制延迟
  • LINUX720 SWAP扩容；新增逻辑卷；逻辑卷扩容；数据库迁移；gdisk
  • Ajax简单介绍及Axios请求方式的别名
  • 复杂度+包装类型+泛型
  • 统计与大数据分析和数字经济：专业选择指南
  • spring-cloud使用
  • ptmalloc(glibc-2.12.1)整体结构
  • Linux:线程控制
  • 基于SpringBoot+MyBatis+MySQL+VUE实现的医疗挂号管理系统（附源码+数据库+毕业论文+答辩PPT+项目部署视频教程+项目所需软件工具）
  • LeetCode 刷题【8. 字符串转换整数 (atoi)， 9. 回文数】
  • 学成在线项目
  • 手推OpenGL相机的正交投影矩阵和透视投影矩阵（附源码）
  • Unity 新旧输入系统对比
  • 开发工具缓存目录
  • Redis通用常见命令（含面试题）
  • [数据库]Neo4j图数据库搭建快速入门
  • 设备健康管理实施案例：中讯烛龙预测性维护系统的实战应用
  • 基于bert-lstm对微博评论的情感分析系统设计与实现
  • 新版 Java SE 集合框架 Map 篇
  • Pycharm的Terminal打开后默认是python环境
  • Kafka 在分布式系统中的关键特性与机制深度解析
  • 基于Pytorch的人脸识别程序
  • 1948. 删除系统中的重复文件夹
  • 定点小数与分数
  • langchain调用本地ollama语言模型和嵌入模型
  • 线程状态线程安全