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

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

news 2025/7/21 16:10:11

目录

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.lryc.cn/news/594467.html

相关文章：

  • MyBatis从浅入深
  • day24——Java高级技术深度解析：单元测试、反射、注解与动态代理
  • 高性能熔断限流实现：Spring Cloud Gateway 在电商系统的实战优化
  • `SearchTransportService` 是 **协调节点与数据节点之间“搜索子请求”通信的运输层**
  • 4种快速创建SpringBoot项目的方法
  • Claude Code 逆向工程分析，探索最新Agent设计
  • JavaScript 中Object、Array 和 String的常用方法
  • 金融工程、金融与经济学知识点
  • 数据结构与算法汇总
  • 连接语言大模型（LLM）服务进行对话
  • GaussDB select into和insert into的用法
  • 机器学习基础：从数据到智能的入门指南
  • python生成密钥
  • Self-Consistency：跨学科一致性的理论与AI推理的可靠性基石
  • An End-to-End Attention-Based Approach for Learning on Graphs NC 2025
  • JAVA面试宝典 -《API设计：RESTful 与 GraphQL 对比实践》
  • 《通信原理》学习笔记——第五章
  • 【1】YOLOv13 AI大模型-可视化图形用户（GUI）界面系统开发
  • Openlayers 面试题及答案180道（121-140）
  • 让不符合要求的任何电脑升级Windows11
  • 【LeetCode数据结构】单链表的应用——环形链表问题详解
  • WireShark抓包分析TCP数据传输过程与内容详解
  • 使用Qt6 QML/C++ 和CMake构建海康威视摄像头应用（代码开源）
  • 【GameMaker】GML v3 的现行提案
  • FreeRTOS任务创建与删除
  • Python 图片爬取入门：从手动下载到自动批量获取
  • Selenium 处理动态网页与等待机制详解
  • 复杂度优先：基于推理链复杂性的提示工程新范式
  • AUTOSAR进阶图解==＞AUTOSAR_SWS_CryptoInterface
  • 【Java学习|黑马笔记|Day18】Stream流|获取、中间方法、终结方法、收集方法及其练习