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

简介: 本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为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),大大提升了运行效率。之后博主回合大家分享栈和队列的内容。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

相关文章
|
28天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
27天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
22天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
67 8
|
22天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
63 7
|
20天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码,可作为课程设计项目参考,代码有详细的注释,另外编译可运行文件也已经打包,windows电脑双击即可运行效果
30 1
|
27天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
89 8
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
58 2
|
7月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1