(学习记录)双向带头循环链表

2024-04-13 10:08
文章标签 学习 链表 记录 双向 循环 带头

本文主要是介绍(学习记录)双向带头循环链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 概述
  • 链表结构
  • 尾插
    • 尾插测试
  • 尾删
  • 查找
  • 在pos位置之前插入
  • 头插
  • 优化尾插
  • 在pos位置删除
  • 优化尾删
  • 头删
  • 总结

概述

双向带头循环链表，它首先必须有一个带哨兵位的头结点。哨兵位的prev和next都指向它自己。
哨兵位
假设链表有三个值（1，2，3），如图，则

  1. 哨兵位的next指向1
    哨兵位的prev指向3
  2. 1的next指向2
    1的prev指向哨兵位
  3. 2的next指向3
    2的prev指向1
  4. 3的next指向哨兵位
    3的prev指向2
    图一

这就是一个完整的双向带头循环链表。

链表结构

首先，创建头文件（List.h）, 函数实现文件（List.c）和测试文件（test.c）。

在List.h中：

  1. 将数据类型重命名，方便以后更改类型。
  2. 将结构体重命名，方便书写并简化代码。

如下图可知，结构体所需要的是指向前后的两个指针和所存数据。
在这里插入图片描述
那么，定义一个数据类型用来存放数据，一个prev的结构体指针和一个next的结构体指针。

代码如下：

typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;

尾插

尾插时，所需要的的参数是

  1. 链表的头结点
  2. 想要插入的数据

在List.h中声明尾插函数void ListPushBack(ListNode* phead, LTDataType x);

实现：

  1. 创建新的节点。

在List.h中声明函数ListNode* BuyListNode(LTDataType x);
在List.c中实现函数

ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
  1. 需要断言。因为在带头链表中，最开始就拥有哨兵位。
  2. 不需要找到尾结点。因为在双向循环链表中，尾结点的next指向哨兵位，哨兵位的prev指向尾结点。

如图所示，尾结点（tail）是头节点（phead）的prev。
在这里插入图片描述
插入newnode后,如图：

  1. tail->next 指向 newnode。
  2. newnode->prev 指向tail。
  3. newnode->next指向头节点（phead）。
  4. phead->prev 指向newnode。

在这里插入图片描述
在在List.c中实现函数

void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

时间复杂度为O(1)。

尾插测试

在测试（test.c）中，创建一个头节点（pList）ListNode* pList = NULL;
但这样pList是指向空，无法尾插，所以pList要改为如下图所示的结构。
由于改变的是结构体的指针，要传结构体指针的地址过去。所以要用二级指针。
在这里插入图片描述

List.h声明初始化函数void ListInit(ListNode** pphead);
List.c实现函数

void ListInit(ListNode** pphead)
{*pphead = BuyListNode(0);(*pphead)->next = *pphead;(*pphead)->prev = *pphead;
}

最后在test.c中监视窗口查看结果。

void TestLTNodePushBack()
{ListNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);
}

或者使用打印函数

  1. List.h中声明函数void ListPrint(ListNode* phead);
  2. 由于哨兵位不打印，所以从哨兵位下一个节点开始遍历，遍历到哨兵位结束。

实现代码：

void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;//哨兵位下一个节点while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

尾删

List.h中声明函数void ListPopBack(ListNode* phead);
在这里插入图片描述

如上下两图所示，想要尾删，就需要知道尾结点（tail）的前一个地址（tailPrev）。

  1. 将tailPrev->next指向哨兵位(phead)。
  2. 将pheadprev指向tailPrev。
  3. free尾结点并置为NULL。
  4. 防止只有哨兵位时，将哨兵位free掉

在这里插入图片描述

List.c中代码实现：

void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);//防止链表中只有哨兵位ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;free(tail);tail == NULL;tailPrev->next = phead;phead->prev = tailPrev;
}

查找

List.h中声明函数ListNode* ListFind(ListNode* phead, LTDataType x);

查找函数和打印函数类似，只从哨兵位的下一个节点开始，向后寻找至哨兵位结束。

List.c中代码实现：

ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos位置之前插入

List.h中声明函数void ListInsert(ListNode* pos, LTDataType x);

在这里插入图片描述
如图，假设在pos位置之前插入30，
在这里插入图片描述

  1. posPrev 的next指向新节点
  2. 新节点的prev指向posPrev
  3. pos的prev指向新节点
  4. 新节点的next指向pos

在头尾前插入时，因为是双向带头循环链表，头尾的前后都不为空，所以可以正常插入。

List.c中代码实现：

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;posPrev->next = newnode;newnode->prev = posPrev;pos->prev = newnode;newnode->next = pos;
}

头插

在ListInsert函数中发现，头插时只需要将哨兵位的下一个节点传给ListInsert函数，就可以实现头插。

List.h中声明函数void ListPushFront(ListNode* phead, LTDataType x);

List.c中代码实现：

void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

优化尾插

既然头插可以用ListInsert函数实现，那么尾插也是类似的道理，只需要将头结点传给ListInsert函数,就可以实现尾插

List.c中代码实现：

void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}

在pos位置删除

在这里插入图片描述
如图:

  1. free掉pos
  2. posPrev的next指向posNext
  3. posNext的prev指向posPrev

List.c中代码实现：

void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

优化尾删

同ListInsert一样，ListErase函数也可以实现尾删。只需要将哨兵位的前一个节点，传给ListErase函数，则完成尾删。

List.c中代码实现：

void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->prev);
}

头删

头删也是同理，ListErase函数中传入哨兵位的下一个节点，则完成头删

List.c中代码实现：

void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->next);
}

总结

双向带头循环链表的实现是非常简单，只要实现Insert和Erase这两个函数，其他函数都可以附庸。

List.h

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;void ListInit(ListNode** pphead);ListNode* BuyListNode(LTDataType x);void ListPushBack(ListNode* phead, LTDataType x);void ListPopBack(ListNode* phead);void ListPrint(ListNode* phead);void ListPushFront(ListNode* phead, LTDataType x);void ListPopFront(ListNode* phead);ListNode* ListFind(ListNode* phead, LTDataType x);void ListInsert(ListNode* pos, LTDataType x);void ListErase(ListNode* pos);

List.c

#include"list.h"void ListInit(ListNode** pphead)
{*pphead = BuyListNode(0);(*pphead)->next = *pphead;(*pphead)->prev = *pphead;
}ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);/*ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;*/ListInsert(phead, x);
}void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);/*ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;free(tail);tail = NULL;tailPrev->next = phead;phead->prev = tailPrev;*/ListErase(phead->prev);
}ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;posPrev->next = newnode;newnode->prev = posPrev;pos->prev = newnode;newnode->next = pos;
}void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListErase(phead->next);
}

这篇关于(学习记录)双向带头循环链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/899844。

相关文章

Spring 依赖注入与循环依赖总结

Spring 依赖注入与循环依赖总结

《Spring依赖注入与循环依赖总结》这篇文章给大家介绍Spring依赖注入与循环依赖总结篇,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Spring 三级缓存解决循环依赖1. 创建UserService原始对象2. 将原始对象包装成工
阅读更多...
Unity新手入门学习殿堂级知识详细讲解（图文）

Unity新手入门学习殿堂级知识详细讲解（图文）

《Unity新手入门学习殿堂级知识详细讲解（图文）》Unity是一款跨平台游戏引擎,支持2D/3D及VR/AR开发,核心功能模块包括图形、音频、物理等,通过可视化编辑器与脚本扩展实现开发,项目结构含A... 目录入门概述什么是 UnityUnity引擎基础认知编辑器核心操作Unity 编辑器项目模式分类工程
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
Python学习笔记之getattr和hasattr用法示例详解

Python学习笔记之getattr和hasattr用法示例详解

《Python学习笔记之getattr和hasattr用法示例详解》在Python中,hasattr()、getattr()和setattr()是一组内置函数,用于对对象的属性进行操作和查询,这篇文章... 目录1.getattr用法详解1.1 基本作用1.2 示例1.3 原理2.hasattr用法详解2.
阅读更多...
基于Spring Boot 的小区人脸识别与出入记录管理系统功能

基于Spring Boot 的小区人脸识别与出入记录管理系统功能

《基于SpringBoot的小区人脸识别与出入记录管理系统功能》文章介绍基于SpringBoot框架与百度AI人脸识别API的小区出入管理系统,实现自动识别、记录及查询功能,涵盖技术选型、数据模型... 目录系统功能概述技术栈选择核心依赖配置数据模型设计出入记录实体类出入记录查询表单出入记录 VO 类（用于
阅读更多...
java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)

java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)

《java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)》：本文主要介绍java中pdf模版填充表单踩坑的相关资料,OpenPDF、iText、PDFBox是三... 目录准备Pdf模版方法1：itextpdf7填充表单（1）加入依赖（2）代码（3）遇到的问题方法2：pd
阅读更多...
Zabbix在MySQL性能监控方面的运用及最佳实践记录

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标（连接、查询、资源、复制）,支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤
阅读更多...
在Spring Boot中集成RabbitMQ的实战记录

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者（Producer）配置1. 创建 Spr
阅读更多...
Java中的for循环高级用法

Java中的for循环高级用法

《Java中的for循环高级用法》本文系统解析Java中传统、增强型for循环、StreamAPI及并行流的实现原理与性能差异,并通过大量代码示例展示实际开发中的最佳实践,感兴趣的朋友一起看看吧... 目录前言一、基础篇：传统for循环1.1 标准语法结构1.2 典型应用场景二、进阶篇：增强型for循环2.
阅读更多...
C++链表的虚拟头节点实现细节及注意事项

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,：本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点（Dummy Head）一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2