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

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。

相关文章

使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
Java深度学习库DJL实现Python的NumPy方式

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
将sqlserver数据迁移到mysql的详细步骤记录

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》：本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据
阅读更多...
Python判断for循环最后一次的6种方法

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for
阅读更多...
Java循环创建对象内存溢出的解决方法

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出（OutOfMemoryError）,所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本（可能导致内存溢出）2.2 修改后的版本问题在
阅读更多...
关于rpc长连接与短连接的思考记录

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短
阅读更多...
Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
Python MySQL如何通过Binlog获取变更记录恢复数据

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志（Binlog）获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2