AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】双向带头循环链表（c语言）（附源码）

2024-11-05 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。

前言

       我们常用的链表有两种：



单向无头不循环链表：也就是我们所说的单链表，它的结构简单，一般是不会用于单独存放数据的。它常被用于实现哈希桶、图的邻接表等。


双向带头循环链表：通常称为双向链表，它的结构较为复杂，实际使用中用于单独存放数据。虽然它的结构比较复杂，但是它的方法执行效率要高于单链表。


接下来，就让我们学习并尝试实现双向带头循环链表。


1.双向带头循环链表的概念和结构定义

双向带头循环链表（双向链表）有三个关键点：


1.双向：不同于单链表，双向链表的节点的指针域附带有两个指针，分别指向其前驱节点和后继节点，这便于我们更灵活地访问链表元素。


2.带头：这里的“头”指的是“哨兵位”，也就是说在创建链表时先创建一个哨兵位的节点位于头部，此节点不存放任何有效数据，只是起到“放哨”的作用。


3.循环：也就是说链表尾部不指向空指针，而是指向头部的节点，形成一个“环”状结构。


而对于单链表，由于不具备这三个特性，所以在运行效率上要低于双向链表。那么我们来看看它的结构定义：

typedef int LTDataType;
 
//双向链表的节点定义
typedef struct ListNode
{
    LTDataType data;//数据域
    struct ListNode* next;//指向前驱节点的指针
    struct ListNode* prev;//指向后继节点的指针
}LTNode;

2.双向带头循环链表的实现

       接下来，我们尝试实现它的一些功能。首先是方法的声明：


2.1 方法声明

//创建新节点
LTNode* LTBuyNode(LTDataType n);
 
//初始化，创建哨兵
void LTInit(LTNode** pphead);
 
//打印链表
void LTPrint(LTNode* phead);
 
//判断链表是否为空
bool LTEmpty(LTNode* phead);
 
//尾插
void LTPushBack(LTNode* phead,LTDataType n);
 
//头插
void LTPushFront(LTNode* phead, LTDataType n);
 
//尾删
void LTPopBack(LTNode* phead);
 
//头删
void LTPopFront(LTNode* phead);
 
//查找
LTNode* LTFind(LTNode* phead, LTDataType n);
 
//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n);
 
//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n);
 
//删除指定节点
void LTErase(LTNode* pos);
 
//销毁链表
void LTDestroy(LTNode** pphead);

2.2 方法实现

2.2.1 创建新节点

       创建新节点的方式于单链表相似，但由于循环的特性，要暂时将其next指针和prev指针指向自己：

//创建新节点
LTNode* LTBuyNode(LTDataType n)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态申请内存
    if (newnode == NULL)//申请失败，退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->next = newnode->prev = newnode;//让两个指针都指向自己
    return newnode;//返回该节点
}

2.2.2 初始化

       初始化时，我们需要创建一个哨兵节点，并且让头指针指向它。由于修改了头指针的值，所以要传入二级指针。

//初始化，创建哨兵
void LTInit(LTNode** pphead)
{
    assert(pphead);//避免传入空指针
    *pphead = LTBuyNode(-1);//创建哨兵节点，传无效数据
}

2.2.3 打印

       对于打印操作，我们从哨兵的next节点开始，按顺序向后遍历打印即可。这里需要注意一下循环的结束条件。

//打印链表
void LTPrint(LTNode* phead)
{
    LTNode* cur = phead->next;//从头节点的下一个节点开始遍历
    while (cur != phead)//由于链表为循环链表，一轮遍历之后还会走到头节点的位置，所以就以头节点为结束标志
    {
        printf("%d ", cur->data);//打印数据
        cur = cur->next;//向后遍历
    }
    printf("\n");
}

2.2.4 判断链表是否为空

       将判空操作单独封装为一个函数，便于其他方法使用。

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
    assert(phead);//防止传空指针
    return phead == phead->next;//后继节点为头节点本身，则说明链表为空，返回true，否则返回false
}

2.2.5 尾插

       与单链表不同，尾插的操作不需要遍历找到链表末尾，头节点的prev指针就是链表的尾节点。



代码如下：

//尾插
void LTPushBack(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(n);//创建新节点
    newnode->next = phead;//新节点的next指向头节点
    newnode->prev = phead->prev;//新节点的prev指向当前的尾节点
    phead->prev->next = newnode;//当前尾节点的next指向新节点
    phead->prev = newnode;//头节点的prev指向新节点
}

2.2.6 头插

       头插的操作过程与尾插十分相似，注意要在头节点的下个节点处插入。



代码如下：

//头插
void LTPushFront(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = phead->next;//新节点的next指向当前的第一个节点
    newnode->prev = phead;//新节点的prev指向头节点
    phead->next->prev = newnode;//当前第一个节点的prev指向新节点
    phead->next = newnode;//头节点的next指向新节点
}

2.2.7 尾删

       尾删操作时，注意针对的是头节点的prev节点。



代码如下：

//尾删
void LTPopBack(LTNode* phead)
{
    assert(phead && !LTEmpty(phead));//注意链表不能为空
    LTNode* del = phead->prev;//要删除的节点
    LTNode* prev = del->prev;//要删除节点的前驱节点
    prev->next = phead;//前驱节点的next指向头节点
    phead->prev = prev;//头节点的prev指向前驱节点
    free(del);//释放del的内存
    del = NULL;//及时制空
}

2.2.8 头删

       头删的操作与尾删相似，针对的是头节点的next节点。



代码如下：

//头删
void LTPopFront(LTNode* phead)
{
    assert(phead && !LTEmpty(phead));
    LTNode* del = phead->next;//要删除的节点
    LTNode* next = del->next;//要删除节点的后继节点
    next->prev = phead;//后继节点的prev指向头节点
    phead->next = next;//头节点的next指向后继节点
    free(del);
    del = NULL;
}

2.2.9 查找

       与单链表相同，查找操作也需要遍历链表，匹配成功则返回该节点；找不到则返回空指针。

//查找
LTNode* LTFind(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == n)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

2.2.10 指定位置之前插入

       进行指定位置插入时，注意确定指定位置的前驱节点和后继节点。

//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n)
{
    assert(pos);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = pos;//新节点的next指向pos
    newnode->prev = pos->prev;//新节点的prev指向pos的前一节点
    pos->prev->next = newnode;//pos的前节点的next指向newnode
    pos->prev = newnode;//pos的prev指向newnode
}

2.2.11 指定位置之后插入

//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n)
{
    assert(pos);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = pos->next;//新节点的next指向pos的后一节点
    newnode->prev = pos;//新节点的prev指向pos
    pos->next->prev = newnode;//pos的后一节点的prev指向newnode
    pos->next = newnode;//pos的next指向newnode
}

2.2.12 删除指定位置节点

//删除指定节点
void LTErase(LTNode* pos)
{
    assert(pos);
    pos->next->prev = pos->prev;//pos的后继节点的prev指向pos的前驱节点
    pos->prev->next = pos->next;//pos的前驱节点的next指向pos的后继节点
    free(pos);
    pos = NULL;
}

2.2.13 销毁链表

       销毁链表时，我们需要遍历链表按照顺序删除全部节点，最后记得要删除头节点。

//销毁链表
void LTDestroy(LTNode** pphead)
{
    assert(pphead);
    if (*pphead == NULL)//链表已经被销毁的情况
    {
        return;
    }
    LTNode* cur = (*pphead)->next;//从第一个节点开始遍历
    while (cur != *pphead)
    {
        LTNode* next = cur->next;//记录后继节点
        free(cur);//释放内存
        cur = next;//使cur指向记录的后继节点
    }
    cur = NULL;
    free(*pphead);//删除头节点
    *pphead = NULL;
}

3.程序全部代码

       程序全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int LTDataType;
 
//双向链表的节点定义
typedef struct ListNode
{
    LTDataType data;//数据域
    struct ListNode* next;//指向前驱节点的指针
    struct ListNode* prev;//指向后继节点的指针
}LTNode;
 
//创建新节点
LTNode* LTBuyNode(LTDataType n);
 
//初始化，创建哨兵
void LTInit(LTNode** pphead);
 
//打印链表
void LTPrint(LTNode* phead);
 
//判断链表是否为空
bool LTEmpty(LTNode* phead);
 
//尾插
void LTPushBack(LTNode* phead,LTDataType n);
 
//头插
void LTPushFront(LTNode* phead, LTDataType n);
 
//尾删
void LTPopBack(LTNode* phead);
 
//头删
void LTPopFront(LTNode* phead);
 
//查找
LTNode* LTFind(LTNode* phead, LTDataType n);
 
//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n);
 
//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n);
 
//删除指定节点
void LTErase(LTNode* pos);
 
//销毁链表
void LTDestroy(LTNode** pphead);
 
//创建新节点
LTNode* LTBuyNode(LTDataType n)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态申请内存
    if (newnode == NULL)//申请失败，退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->next = newnode->prev = newnode;//让两个指针都指向自己
    return newnode;//返回该节点
}
 
//初始化，创建哨兵
void LTInit(LTNode** pphead)
{
    assert(pphead);//避免传入空指针
    *pphead = LTBuyNode(-1);//创建哨兵节点，传无效数据
}
 
//打印链表
void LTPrint(LTNode* phead)
{
    LTNode* cur = phead->next;//从头节点的下一个节点开始遍历
    while (cur != phead)//由于链表为循环链表，一轮遍历之后还会走到头节点的位置，所以就以头节点为结束标志
    {
        printf("%d ", cur->data);//打印数据
        cur = cur->next;//向后遍历
    }
    printf("\n");
}
 
//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
    assert(phead);//防止传空指针
    return phead == phead->next;//后继节点为头节点本身，则说明链表为空，返回true，否则返回false
}
 
//尾插
void LTPushBack(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(n);//创建新节点
    newnode->next = phead;//新节点的next指向头节点
    newnode->prev = phead->prev;//新节点的prev指向当前的尾节点
    phead->prev->next = newnode;//当前尾节点的next指向新节点
    phead->prev = newnode;//头节点的prev指向新节点
}
 
//头插
void LTPushFront(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = phead->next;//新节点的next指向当前的第一个节点
    newnode->prev = phead;//新节点的prev指向头节点
    phead->next->prev = newnode;//当前第一个节点的prev指向新节点
    phead->next = newnode;//头节点的next指向新节点
}
 
//尾删
void LTPopBack(LTNode* phead)
{
    assert(phead && !LTEmpty(phead));//注意链表不能为空
    LTNode* del = phead->prev;//要删除的节点
    LTNode* prev = del->prev;//要删除节点的前驱节点
    prev->next = phead;//前驱节点的next指向头节点
    phead->prev = prev;//头节点的prev指向前驱节点
    free(del);//释放del的内存
    del = NULL;//及时制空
}
 
//头删
void LTPopFront(LTNode* phead)
{
    assert(phead && !LTEmpty(phead));
    LTNode* del = phead->next;//要删除的节点
    LTNode* next = del->next;//要删除节点的后继节点
    next->prev = phead;//后继节点的prev指向头节点
    phead->next = next;//头节点的next指向后继节点
    free(del);
    del = NULL;
}
 
//查找
LTNode* LTFind(LTNode* phead, LTDataType n)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == n)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
 
//指定位置之前插入
void LTInsert(LTNode* pos, LTDataType n)
{
    assert(pos);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = pos;//新节点的next指向pos
    newnode->prev = pos->prev;//新节点的prev指向pos的前一节点
    pos->prev->next = newnode;//pos的前节点的next指向newnode
    pos->prev = newnode;//pos的prev指向newnode
}
 
//指定位置之后插入
void LTInsertAfter(LTNode* pos, LTDataType n)
{
    assert(pos);
    LTNode* newnode = LTBuyNode(n);
    newnode->next = pos->next;//新节点的next指向pos的后一节点
    newnode->prev = pos;//新节点的prev指向pos
    pos->next->prev = newnode;//pos的后一节点的prev指向newnode
    pos->next = newnode;//pos的next指向newnode
}
 
//删除指定节点
void LTErase(LTNode* pos)
{
    assert(pos);
    pos->next->prev = pos->prev;//pos的后继节点的prev指向pos的前驱节点
    pos->prev->next = pos->next;//pos的前驱节点的next指向pos的后继节点
    free(pos);
    pos = NULL;
}
 
//销毁链表
void LTDestroy(LTNode** pphead)
{
    assert(pphead);
    if (*pphead == NULL)//链表已经被销毁的情况
    {
        return;
    }
    LTNode* cur = (*pphead)->next;//从第一个节点开始遍历
    while (cur != *pphead)
    {
        LTNode* next = cur->next;//记录后继节点
        free(cur);//释放内存
        cur = next;//使cur指向记录的后继节点
    }
    cur = NULL;
    free(*pphead);//删除头节点
    *pphead = NULL;
}

总结

       今天我们学习了双向带头循环链表的概念以及功能实现。可以发现，与单链表不同，它的头插、尾插、头删、尾删等操作的时间复杂度都是O(1)，大大提升了运行效率。之后博主回合大家分享栈和队列的内容。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

文章标签：
C语言
关键词：
数据结构链表
数据结构c语言
C语言源码
数据结构源码
数据结构C语言源码
ephemerals__
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
60 4
三三是该溜子
|
2天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
10 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
28天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
54 5
XIAZHI
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念，并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素，以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用，还涉及到了算法逻辑的设计与优化。实验结果显示，学生能够有效掌握并运用这些知识完成指定任务。
XIAZHI
58 4
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
92 16
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
128 7
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
106 8
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
134 8
疯狂的猿
|
1月前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码，可作为课程设计项目参考，代码有详细的注释，另外编译可运行文件也已经打包，windows电脑双击即可运行效果
疯狂的猿
35 1
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
50 0

热门文章

最新文章

  • 1
    【C语言】输入/输出函数详解
  • 2
    【C语言】宏定义详解
  • 3
    C 语言中所有可用的关系运算符
  • 4
    【c语言】运算符汇总（万字解析）
  • 5
    【C语言】结构体详解 -《探索C语言的 “小宇宙” 》
  • 6
    【C语言】enum 关键字详解
  • 7
    C 语言中的数据类型转换：连接不同数据世界的桥梁
  • 8
    【C语言】原码、反码、补码详解 -《码上有道 ! 》
  • 9
    【C语言】深入解析C语言结构体：定义、声明与高级应用实践
  • 10
    【C语言】字符常量详解
  • 1
    数据结构中二叉树，哈希表，顺序表，链表的比较补充
    10
  • 2
    【C语言】深入浅出：C语言链表的全面解析
    269
  • 3
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
    54
  • 4
    数据结构实验之链表
    60
  • 5
    数据结构之购物车系统(链表和栈)
    50
  • 6
    顺序表和链表（2）
    60
  • 7
    【数据结构】手把手教你单链表（c语言）（附源码）
    98
  • 8
    顺序表和链表（1）
    28
  • 9
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    32
  • 10
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
    40

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)