💛 前情提要💛

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

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

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

❗以下内容以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: