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

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

2024-11-05 41
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为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语言
数据结构链表C语言
ephemerals__
目录
相关文章
ephemerals__
|
26天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
122 9
龙大吉
|
4天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
25 5
ephemerals__
|
25天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
ephemerals__
|
21天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
65 8
ephemerals__
|
21天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
59 7
疯狂的猿
|
19天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码，可作为课程设计项目参考，代码有详细的注释，另外编译可运行文件也已经打包，windows电脑双击即可运行效果
疯狂的猿
30 1
ephemerals__
|
25天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
82 8
那年春天
|
17天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
22 1
德国都芳最好
|
20天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
71 21
html的七十二变
|
23天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
31 2

热门文章

最新文章

  • 1
    C语言标准库（常用函数）详解（含示例）数学公式：math.h
  • 2
    C语言四舍五入计算方法（包含各种精度）
  • 3
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 4
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 5
    《C语言及程序设计》实践项目——数据的输入
  • 6
    C语言预处理之二-----宏定义那点事儿
  • 7
    C语言库函数大全及应用实例十
  • 8
    四则运算表达式求值程序(C语言版)
  • 9
    C语言及程序设计提高例程-26 实现线性表基本操作的函数
  • 10
    成长之路---C语言笔记（运算符优先级与结合性）
  • 1
    链表遍历，链表查找和统计节点，链表插入新节点，链表删除节点，链表修改指定节点,链表头插法，尾插法总结
    43
  • 2
    剑指offer（牛客）——合并两个排序的链表
    40
  • 3
    剑指offer（牛客）——从尾到头打印链表
    41
  • 4
    每日一题：力扣328. 奇偶链表
    43
  • 5
    数据结构与算法 数组和链表
    42
  • 6
    leetcode代码记录（移除链表元素
    33
  • 7
    单链表的应用
    58
  • 8
    数据结构第二课 -----线性表之单向链表
    55
  • 9
    数据结构第三课 -----线性表之双向链表
    45
  • 10
    链表练习题-2
    51

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月