前言

我们常用的链表有两种：

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

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

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

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语言）（附源码）

前言

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

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

2.1 方法声明

2.2 方法实现

2.2.1 创建新节点

2.2.2 初始化

2.2.3 打印

2.2.4 判断链表是否为空

2.2.5 尾插

2.2.6 头插

2.2.7 尾删

2.2.8 头删

2.2.9 查找

2.2.10 指定位置之前插入

2.2.11 指定位置之后插入

2.2.12 删除指定位置节点

2.2.13 销毁链表

3.程序全部代码

总结

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

前言

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

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

2.1 方法声明

2.2 方法实现

2.2.1 创建新节点

2.2.2 初始化

2.2.3 打印

2.2.4 判断链表是否为空

2.2.5 尾插

2.2.6 头插

2.2.7 尾删

2.2.8 头删

2.2.9 查找

2.2.10 指定位置之前插入

2.2.11 指定位置之后插入

2.2.12 删除指定位置节点

2.2.13 销毁链表

3.程序全部代码

总结

热门文章

最新文章

相关电子书