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

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。

相关文章

springboot循环依赖问题案例代码及解决办法

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖（即BeanA依赖BeanB,而BeanB又依赖BeanA）,会导致Spring的... 目录1. 什么是循环依赖？2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1：使用 @La
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
Python循环缓冲区的应用详解

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库
阅读更多...
Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定
阅读更多...
Java进阶学习之如何开启远程调式

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,：本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx
阅读更多...
国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后，需要到系统环境变量中添加两个变量2. 第3步 “在cmd中
阅读更多...
Java嵌套for循环优化方案分享

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2