【数据结构】带头 + 双向 + 循环链表（增、删、查、改）的实现 _【附源码、图片示例】_ [初阶篇 _ 复习专用]

作者：Dream-Y.ocean

2022 年 9 月 19 日
广东
本文字数：5109 字
阅读完需：约 17 分钟

前情提要

本章节是数据结构的带头+双向+循环链表的相关知识~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦❗

以下内容干货满满，跟上步伐吧~

💡本章重点

链表的概念
带头+双向+循环链表的结构
带头+双向+循环链表的优势
带头+双向+循环链表的实现

🍞一.链表的概念

🥐Ⅰ.什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构
数据元素的逻辑顺序是通过链表中的指针链接次序实现的

❗综上：

链表也符合我们在顺序表中提及的线性表，即链表也是线性表的一种

🥯Ⅱ.总结

✨综上：就是链表的概念啦~

➡️简单来说：链表是逻辑结构上类似于顺序表的连续的结构，但实际物理结构是不一定连续存储的

🔍以上内容可考古上篇：【数据结构】单链表（增、删、查、改）的实现 [初阶篇_ 复习专用]

但今天，我们终点来看看链表的==终极形态==：带头+双向+循环链表

🍞二.带头+双向+循环链表

🥐Ⅰ.结构

逻辑结构

🥐Ⅱ.优势

💡通过上图，我们可知：双向带头循环链表

1️⃣带头：带有头结点（哨兵位），头结点一般不存储值，只存指向下一个（上一个）结点的地址
2️⃣双向：每一个结点既有前驱指针（Prev）又有后驱指针（Next）
3️⃣循环：链表的逻辑结构整体上是循环的

➡️简单来说

带头双向循环链表较单链表的优势在于：

🔴单向与双向

单链表仅仅仅仅只能通过访问后驱指针（Next）从一个方向【由头到尾】去访问每个结点，难以从某个结点去访问回上一个结点
而双向链表因为同时具有前、后驱指针，便可以很灵活地访问任意结点的上一个结点

🟢带头与不带头

若不带头结点，每次对链表执行操作时，都通过第一个结点开始操作，很容易误判链表一&二级指针接收的问题【即是否需要改头指针指向的问题】
若带上头结点，就没有上述的问题出现了，因为头指针永远是指向头结点，头指针的指向不会发生改变，就无需担心上述问题了

关于一级指针or二级指针接收相关问题详解，可点击跳转

🟡循环

链表的循环结构是由双向【前、后驱指针】这个特点形成的

👉综上：

因为带有双向+循环结构，此时的头结点也是可以看作最后一个结点的，因为最后一个结点的next指向的就是head

✨有了以上对链表的概念后，我们便可以实现它啦~

🥐Ⅲ.实现

💡结点： 我们所创建的结点都是从堆区上申请空间的

➡️简单来说： 使用动态开辟在堆区上开辟一个结点的空间

Tips: 关于动态开辟不熟悉的同学可以跳转去🔍【C语言】动态内存管理 [进阶篇_ 复习专用]查看呀

typedef int LTDataType;    typedef struct ListNode{    struct ListNode* next;    struct ListNode* prev;    LTDataType data;    }ListNode;

复制代码

👉由上述我们可知：

结点本质是结构体类型，结构体内包含了数据域、前驱指针、后驱指针域

LTDataType data;用来存储数据
struct ListNode* next;是用来指向下一个结点
struct ListNode* prev;是用来指向上一个结点

✨综上：

链表可以根据存储的数据多少实现随时创建结点【动态开辟】进行链接，不会存在空间的浪费
所以下面我们实现链表的接口

❗此处我们实现的是基础的带头双向循环链表

🍞三.链表插口实现

对于数据结构的接口实现，一般围绕增、删、查、改的内容

💡如下的实现围绕此原码进行：

//创建头结点//头指针指向头结点ListNode* plist = ListInit();

复制代码

🥐Ⅰ.链表初始化

❗特别注意：

与单链表不同，因为带头双向循环链表的头指针指向的是头结点（哨兵位）而非第一个结点，所以需要对头指针进行初始化
但单链表是不需要初始化的，头指针是直接指向第一个结点，即直接指向新创建的结点

1️⃣链表初始化的函数声明：

ListNode* ListInit();

复制代码

2️⃣链表初始化函数的实现：

ListNode* ListInit() {    ListNode* phead = BuyListNode(0);    phead->next = phead;    phead->prev = phead;
    return phead;}

复制代码

🥐Ⅱ.创建新结点

1️⃣创建新结点的函数声明：

ListNode* BuyListNode(LTDataType x)

复制代码

2️⃣创建新结点函数的实现：

ListNode* BuyListNode(LTDataType x){    ListNode* node = (ListNode*)malloc(sizeof(ListNode));    node->next = NULL;    node->prev = NULL;    node->data = x;    return node;}

复制代码

🥐Ⅲ.尾插链表

👉简单来说： 对链表尾部链接一个新的结点

➡️实现： 因为结构的优势，可以直接通过访问头结点（pHead）的Prev找到最后一个结点【就不需要像单链表找尾需要遍历】，将此最后一个结点的next指向新的结点

❗特别注意： 当链表为NULL（空表）的时候，尾插即是在头插

✊图例：

1️⃣尾插的函数声明：

void ListPushBack(ListNode* phead, LTDataType x);

复制代码

2️⃣尾插函数的实现：

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;}

复制代码

🥐Ⅳ.头插链表

👉简单来说： 对链表头部链接一个结点

➡️实现： 直接插入到头结点之后

❗特别注意：

即使是NULL（空表），也可以实现头插
注意插入顺序，如果顺序反了，会丢失后面结点的地址，找不到后面结点

✊图例：

1️⃣头插的函数声明：

void ListPushFront(ListNode* phead, LTDataType x);

复制代码

2️⃣头插函数的实现：

void ListPushFront(ListNode* phead, LTDataType x){    assert(phead);    ListNode* first = phead->next;    ListNode* newnode = BuyListNode(x);
    ////以下代码通用于： 只有一个 头结点的时候，也是可以的    ////体现了结构的优势  
    phead->next = newnode;    newnode->prev = phead;    newnode->next = first;    first->prev = newnode;}

复制代码

🥐Ⅴ.尾删链表

👉简单来说： 对链表删除最后一个结点

➡️实现： 找到尾结点的上一个结点，并将尾结点释放掉，再将上一结点与头结点相链接

❗特别注意：

只有一个头结点的时候，即链表为NULL，不可以进行尾删

✊图例：

1️⃣尾删的函数声明：

void ListPopBack(ListNode* phead);

复制代码

2️⃣尾删函数的实现：

void ListPopBack(ListNode* phead){    assert(phead);
    assert(phead->next != phead);
    ListNode* tail = phead->prev; //找尾    ListNode* tailPrev = tail->prev;
    free(tail);
    tailPrev->next = phead;    phead->prev = tailPrev;}

复制代码

🥐Ⅵ.头删链表

👉简单来说： 对链表删除第一个结点

➡️实现： 记住链表的第二个结点，然后释放头结点，让第二个结点链接头结点

❗特别注意：

只有一个头结点的时候，即链表为NULL，不可以进行头删

✊图例：

1️⃣头删的函数声明：

void ListPopFront(ListNode* phead);

复制代码

2️⃣头删函数的实现：

void ListPopFront(ListNode* phead){    assert(phead);
    assert(phead->next != NULL);
    ListNode* newhead = phead->next->next;    ListNode* del = phead->next;
    free(del);    del = NULL;     //不置空问题也不大，因为出了这个函数 这个参数就销毁了 
    phead->next = newhead;    newhead->prev = phead;
    ListErase(phead->next);}

复制代码

🥐Ⅶ.查找链表结点

👉简单来说： 对链表进行查找所需的结点

➡️实现： 遍历链表表一一比较查找是否有我们想要的结点

没有,则返回NULL
有，则返回当前结点的地址

1️⃣查找链表结点的函数声明：

ListNode* ListFind(ListNode* phead, LTDataType x);

复制代码

2️⃣查找链表结点函数的实现：

ListNode* ListFind(ListNode* phead, LTDataType x){    //遍历一遍去找    assert(phead);
    ListNode* cur = phead->next;    while (cur != phead->prev)    {        if (cur->data = x)        {            return cur;        }        else        {            cur = cur->next;        }    }    return NULL;}

复制代码

🥐Ⅷ.任意位置删除元素

👉简单来说： 对链表的某个位置进行删除

➡️实现： 释放掉需要删除的结点，并将其前后结点链接在一起

💥特别注意： 删除的位置要在顺序表有效个数的范围内

1️⃣任意位置删除元素的函数声明：

void ListErase(ListNode* pos);

复制代码

2️⃣任意位置删除元素函数的实现：

void ListErase(ListNode* pos){    assert(pos);
    ListNode* prev = pos->prev;    ListNode* next = pos->next;
    prev->next = next;    next->prev = prev;
    free(pos);}

复制代码

💡有了任意位置删除元素函数的实现，我们的头删、尾删函数便可以复用这个函数来实现了

🧇1.【复用】头删函数

👉复用任意位置删除函数的头删函数的实现：

void ListPopBack(ListNode* phead){    ListErase(phead->prev);}

复制代码

🧇2.【复用】尾删函数

👉复用任意位置删除函数的尾删函数的实现：

void SeqListPopBack(SeqList* pq){    SeqListErase(pq, pq->size - 1);}

复制代码

🥐Ⅸ.任意位置前插入结点

👉简单来说： 对链表的某个位置前进行插入

➡️实现： 找到要前插的结点位置，将新的结点插入并与前插结点和被前插结点的上个结点链接

💥特别注意： 插入的位置为链表的实际范围内

1️⃣任意位置插入元素的函数声明：

void ListInsert(ListNode* pos, LTDataType x);

复制代码

2️⃣任意位置插入元素函数的实现：

void ListInsert(ListNode* pos, LTDataType x){    assert(pos);
    ListNode* prev = pos->prev;    ListNode* newnode = BuyListNode(x);    prev->next = newnode;    newnode->prev = prev;
    newnode->next = pos;    pos->prev = newnode;}

复制代码

💡有了任意位置插入元素函数的实现，我们的头插、尾插函数便可以复用这个函数来实现了

🧇1.【复用】头插函数

👉复用任意位置插入函数的头插函数的实现：

void ListPushFront(ListNode* phead, LTDataType x){    ListInsert(phead->next, x);}

复制代码

🧇2.【复用】尾插函数

👉复用任意位置插入函数的尾插函数的实现：

❗因为头节点（pHead）的上一个结点就是尾结点，所以可以用头结点的前插，当作尾插

void ListPushBack(ListNode* phead, LTDataType x){    ListInsert(phead, x);}

复制代码

🥐Ⅹ.判断链表是否为 NULL

👉简单来说： 判断链表是否除了头结点还有其它结点

➡️实现： 只需要直接判断头结点的下一个结点是否为其它结点即可

链表为空：返回true
链表为非空：返回false

1️⃣判断链表是否为空的函数声明：

bool ListEmpty(ListNode* phead);

复制代码

2️⃣判断链表是否为空函数的实现：

bool ListEmpty(ListNode* phead){    assert(phead);    return phead->next == phead ? true : false;}

复制代码

🥐Ⅺ.统计链表有效结点个数

👉简单来说： 判断除头结点外的结点个数

➡️实现： 遍历链表统计即可

1️⃣统计链表有效结点个数的函数声明：

int ListSize(ListNode* phead);

复制代码

2️⃣统计链表有效结点个数函数的实现：

int ListSize(ListNode* phead){    assert(phead);    ListNode* cur = phead->next;    int count = 0;
    while (cur != phead)    {        count++;        cur = cur->next;    }    return count;}

复制代码

🥐Ⅻ.打印链表

👉简单来说： 对链表逐个遍历打印

➡️实现： 遍历链表一一打印即可

❗特别注意：

因为不像单链表的结束标记是NULL，因为是循环结构，所以这里的结束标记为返回到头结点就结束

1️⃣打印链表的函数声明：

void ListPrint(ListNode* phead);

复制代码

2️⃣打印链表函数的实现：

void ListPrint(ListNode* phead){    ListNode* cur = phead->next;    while (cur != phead)      {        printf("%d ", cur->data);        cur = cur->next;    }    printf("\n");}

复制代码

🥐XIII.销毁链表

👉简单来说： 对链表进行销毁，释放内存空间

➡️实现： 逐一遍历链表结点，然后逐个释放,最后将头结点也释放即可

1️⃣销毁链表的函数声明：

void ListDestory(ListNode* phead);

复制代码

2️⃣销毁链表函数的实现：

void ListDestory(ListNode* phead){    assert(phead);    ListNode* cur = phead->next;
    while (cur != phead)    {         ListNode* next = cur->next;        free(cur);
        cur = next;    }        free(phead);}

复制代码

🥯XIV.总结

✨综上：就是带头+双向+循环链表接口实现的内容啦~

➡️相信大家对带头+双向+循环链表有不一样的看法了吧🧡

🫓总结

综上，我们基本了解了数据结构中的“带头+双向+循环链表”:lollipop:的知识啦~~

恭喜你的内功又双叒叕得到了提高！！！

感谢你们的阅读:satisfied:

后续还会继续更新:heartbeat:，欢迎持续关注:pushpin:哟~

:dizzy:如果有错误❌，欢迎指正呀:dizzy:

:sparkles:如果觉得收获满满，可以点点赞👍支持一下哟~:sparkles:

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/f285dcab09e31dcb82ce40be8】。未经作者许可，禁止转载。

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

发布

暂无评论

创作场景

【数据结构】带头 + 双向 + 循环链表（增、删、查、改）的实现 _【附源码、图片示例】_ [初阶篇 _ 复习专用]

💡本章重点

🍞一.链表的概念

🥐Ⅰ.什么是链表

🥯Ⅱ.总结

🍞二.带头+双向+循环链表

🥐Ⅰ.结构

🥐Ⅱ.优势

🥐Ⅲ.实现

🍞三.链表插口实现

🥐Ⅰ.链表初始化

🥐Ⅱ.创建新结点

🥐Ⅲ.尾插链表

🥐Ⅳ.头插链表

🥐Ⅴ.尾删链表

🥐Ⅵ.头删链表

🥐Ⅶ.查找链表结点

🥐Ⅷ.任意位置删除元素

🧇1.【复用】头删函数

🧇2.【复用】尾删函数

🥐Ⅸ.任意位置前插入结点

🧇1.【复用】头插函数

🧇2.【复用】尾插函数

🥐Ⅹ.判断链表是否为 NULL

🥐Ⅺ.统计链表有效结点个数

🥐Ⅻ.打印链表

🥐XIII.销毁链表

🥯XIV.总结

🫓总结

Dream-Y.ocean

评论