数据结构之带头双向循环链表

Ne0inhk

— 8 min read
数据结构之带头双向循环链表

前言：前面我们实现了顺序表和单链表，这次来实现一个结构更复杂的链表-----带头双向循环链表。不要被它的名字吓到哦，只是结构复杂而已，它的结构更有利于代码的实现。

1 双向循环链表的介绍

有了单链表的基础，要实现这个双向循环带头链表其实并不难。下面我们先来了解一下什么是双向循环带头链表。

在这里插入图片描述

这就是双向循环带头链表的结构图，可以很清晰的看到，这个链表需要两个指针，一个指向后继结点，一个指向前驱节点，其次还需要一个头结点。只是这个头结点并不需要存储有效数据。

2 双向循环链表的实现

2.1 双向循环带头链表的定义

//存储的数据类型typedefint LDataType;//链表的定义typedefstructListNode{ LDataType val;structListNode* next;//指向后继节点structListNode* prev;//指向前驱节点}LTNode;

2.2 双向循环带头链表的接口

//初始化双向循环带头链表‘ LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找 LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

2.2.1 初始化链表

//初始化双向循环带头链表 LTNode*ListInit(){//哨兵位头结点 LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);} phead->next = phead; phead->prev = phead;return phead;}
在这里插入图片描述

2.2.2 创建新节点

//创建新节点 LTNode*BuyListNode(LDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);} newnode->val = x; newnode->prev=newnode->next=NULL;return newnode;}

2.2.3 链表尾插

//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead); LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->val = x;*/ LTNode* newnode =BuyListNode(x); newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode;}
在这里插入图片描述
通过phead->prev就可以找到链表的尾节点，增加的节点newnode->prev 应该链接链表尾节点，链表的尾节点链接newnode,newnode->next应 该链接链表的头结点，链表的头结点的prev保存newnode的地址，使 newnode成为链表新的尾节点。

2.2.4 链表头插

//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead); LTNode* newnode =BuyListNode(x); LTNode* pheadNext = phead->next; phead->next = newnode; newnode->prev = phead; pheadNext->prev = newnode; newnode->next = pheadNext;}
在这里插入图片描述
先创建一个指针指向头结点的后继结点，再让newnode->next保存该 节点的地址，该节点的prev保存newnode的地址，phead->next保存 newnode的地址，newnode->prev保存头结点的地址。

2.2.5 链表尾删

//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev;free(tail);}
在这里插入图片描述
通过phead->prev找到链表尾节点，再通过尾节点的prev找到尾节点 的前驱节点，让该前驱节点的next指向phead,phead->prev指向该前 驱节点，最后释放尾节点。

2.2.6 链表头删

//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* head = phead->next; LTNode* next = head->next; next->prev = phead; phead->next = next;free(head);}
在这里插入图片描述
首先通过phead->next找到链表头结点的后继结点，再通过该后继结点找到下一个节点，使该节点的prev保存头结点的地址，头结点的next保存该节点的地址，最后释放该后继结点。

2.2.7 链表的查找

//查找 LTNode*ListFind(LTNode* phead, LDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{ cur = cur->next;}}returnNULL;}

从头结点的后继结点开始遍历查找，找到了就返回该节点的地址，找不到返回NULL（当再一次遍历到头结点时，说明未找到）。

2.2.8 从pos位置之前插入

//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL); LTNode* newnode =BuyListNode(x); LTNode* posPrev = pos->prev; posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode;}
在这里插入图片描述
首先找到pos位置的前驱节点，再让newnode->prev指向该前驱节 点，该前驱节点的next指向newnode,pos->prev指newnode, newnode->next指向pos。

2.2.9 删除pos位置

//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev;free(pos);}
在这里插入图片描述
找到pos位置的前驱节点和后继结点，让该前驱节点的next指向该后 继结点，该后继结点的prev指向该前驱节点。

2.2.10 链表的打印

//打印voidListPrint(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val); cur = cur->next;}printf("\n");}

从头结点的后继结点开始遍历链表，当节点不是头结点时就打印该节点的值。

2.2.11 销毁链表

//销毁链表voidListDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* tmp = cur; cur = cur->next;free(tmp); tmp =NULL;} cur =NULL; phead =NULL;}

从头结点的后继结点开始销毁，先记录该后继结点的下一个节点，再销毁该后继结点。重复上述操作，直到再一次回到头结点的位置，此时销毁该头结点。

3 完整代码的实现

List.h文件

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LDataType;typedefstructListNode{ LDataType val;structListNode* next;structListNode* prev;}LTNode;//初始化双向循环带头链表‘ LTNode*ListInit();//打印voidListPrint(plist);//尾插voidListPushBack(LTNode* phead, LDataType x);//尾删voidListPopBack(LTNode* phead);//头插voidListPushFront(LTNode* phead, LDataType x);//头删voidListPopFront(LTNode* phead);//查找 LTNode*ListFind(LTNode* phead, LDataType x);//pos位置之前插入voidListInsert(LTNode* pos, LDataType x);//删除pos位置voidListErase(LTNode* pos);//销毁链表voidListDestroy(LTNode* phead);

List.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"//初始化双向循环带头链表 LTNode*ListInit(){//哨兵位头结点 LTNode* phead =(LTNode*)malloc(sizeof(LTNode));if(phead ==NULL){printf("malloc fail\n");exit(-1);} phead->next = phead; phead->prev = phead;return phead;}//打印voidListPrint(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->val); cur = cur->next;}printf("\n");}//销毁链表voidListDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* tmp = cur; cur = cur->next;free(tmp); tmp =NULL;} cur =NULL; phead =NULL;}//创建新节点 LTNode*BuyListNode(LDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);} newnode->val = x;//newnode->prev = newnode->next = NULL;return newnode;}//尾插voidListPushBack(LTNode* phead, LDataType x){assert(phead); LTNode* tail = phead->prev;/*LTNode* newnode = (LTNode*)malloc(sizeof(LDataType)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->val = x;*/ LTNode* newnode =BuyListNode(x); newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode;}//尾删voidListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev;//free(tail); tailPrev->next = phead; phead->prev = tailPrev;free(tail);}//头插voidListPushFront(LTNode* phead, LDataType x){assert(phead); LTNode* newnode =BuyListNode(x); LTNode* pheadNext = phead->next; phead->next = newnode; newnode->prev = phead; pheadNext->prev = newnode; newnode->next = pheadNext;}//头删voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); LTNode* head = phead->next; LTNode* next = head->next; next->prev = phead; phead->next = next;free(head);}//查找 LTNode*ListFind(LTNode* phead, LDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->val == x){return cur;}else{ cur = cur->next;}}returnNULL;}//pos位置之前插入voidListInsert(LTNode* pos, LDataType x){assert(pos !=NULL); LTNode* newnode =BuyListNode(x); LTNode* posPrev = pos->prev; posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode;}//删除pos位置voidListErase(LTNode* pos){assert(pos !=NULL); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev;free(pos);}

test.c文件

#define_CRT_SECURE_NO_WARNINGS#include"List.h"voidListTest1(){ LTNode* plist =ListInit();ListPushBack(plist,1);ListPushBack(plist,2);ListPushBack(plist,3);ListPushBack(plist,4);ListPushBack(plist,5);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPushFront(plist,6);ListPushFront(plist,7);ListPushFront(plist,8);ListPushFront(plist,9);ListPushFront(plist,10);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist); LTNode* pos =ListFind(plist,2);if(NULL!= pos){printf("找到了\n");}else{printf("找不到\n");}ListInsert(pos,10);ListPrint(plist); pos =ListFind(plist,1);ListErase(pos);ListPrint(plist);ListDestroy(plist); plist =NULL;//ListPrint(plist);}intmain(){ListTest1();return0;}

4 顺序表与链表的对比

在这里插入图片描述

Read more

企业级在线文档：ONLYOFFICE 核心优势深度解读与测评体验

企业级在线文档：ONLYOFFICE 核心优势深度解读与测评体验

在当今数字化转型的浪潮中，企业的办公模式正在经历从“单机作业”到“云端协同”的深刻变革。尤其是在混合办公、跨地域协作日益普遍的今天，寻找一款既能打破信息孤岛、提高团队协作效率，又能严格保障企业核心商业数据安全的文档处理引擎，成为了每一个 IT 架构师和企业决策者的核心诉求。 我们在评估过市面上众多协作工具后，最终将目光锁定在了 ONLYOFFICE 上。作为一款开源且功能强大的企业级在线文档套件，ONLYOFFICE 在实际业务场景中展现出了令人惊艳的稳定性和功能深度。今天，我就根据自己在企业内部署和试用 ONLYOFFICE 的第一手经验，从实时协作、数据安全、多设备支持等维度，深度解读它的核心优势，看看它是如何真正为企业降本增效的。 🚀 协同即生产力：极简且强大的实时协作体验 在企业日常运营中，最耗费精力的事情莫过于多部门共同编写同一份项目企划书或合并多张财务报表。传统模式下，文件需要在微信、邮件里丢来丢去，不仅版本极其容易混乱，沟通成本也高得惊人。而 ONLYOFFICE 作为一款企业级在线文档工具，完美地解决了这个痛点。 ONLYOFFICE 提供了两种非常贴合企业

By Ne0inhk
【2026 最新 Linux 零基础入门总结】第一章：认识Linux

【2026 最新 Linux 零基础入门总结】第一章：认识Linux

一、Linux的历史 （1） 起源：Unix 与 GNU 铺垫（1969–1990） * 1969–1970：贝尔实验室 Ken Thompson、Dennis Ritchie 开发 Unix，奠定多用户、多任务、稳定可靠的操作系统范式。 * 1983：Richard Stallman 发起 GNU 计划，目标打造完全自由的类 Unix 系统，陆续开发 GCC、Emacs、Bash 等核心工具，但缺少内核。 * 1987：Andrew Tanenbaum 发布 Minix（教学用微型 Unix），源码开放但不可自由修改/分发，成为 Linus 早期学习与开发的基础。 （2）

By Ne0inhk
【Linux系统编程】（四十二）吃透线程互斥！从原理到实战，手把手教你玩转 Linux 下的互斥锁

【Linux系统编程】（四十二）吃透线程互斥！从原理到实战，手把手教你玩转 Linux 下的互斥锁

目录 前言 一、线程互斥的核心概念：搞懂这些，才算入门 1.1 共享资源与临界资源 1.2 临界区 1.3 互斥的定义 1.4 原子性：互斥的底层要求 二、多线程共享资源的坑：亲眼看看问题出在哪 2.1 问题代码：未加互斥的售票系统 2.2 编译运行与异常结果 2.3 问题根源：三步分析 （1）线程调度的随机性 （2）耗时操作放大了竞争问题 （3）ticket--本身不是原子操作 2.4 解决问题的核心要求 三、Linux 下的互斥量：mutex 的使用全解析 3.1 互斥量的类型与核心接口

By Ne0inhk

Flutter 三方库 at_server_status 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、实时的 @protocol 去中心化身份服务器状态感知与鉴权监控引擎

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 at_server_status 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、透明、实时的 @protocol 去中心化身份服务器状态感知与鉴权监控引擎 在鸿蒙（OpenHarmony）系统的隐私保护应用、去中心化身份管理工具（基于 @protocol 协议）或需要实时监控全球分布式节点健康状况的场景中，如何判定一个 @sign（电子签名标识）背后的 Root 服务器或 Secondary 服务器是否在线、配置是否由于由于由于由于已就绪？at_server_status 为开发者提供了一套工业级的、基于协议栈的状态审计与自检方案。本文将深入实战其在鸿蒙 Web3 身份安全底座中的应用。 前言 什么是 atServer Status？它是 @protocol（一种旨在让用户完全掌控数据的去中心化协议）官方生态的核心组件。

By Ne0inhk