C语言-链表

07-21 776阅读

文章目录

🎯引言
👓链表
- 1.链表的概念与分类
- - 1.1链表的概念 :
  - 1.2链表的分类:
  - 2.单链表(不带头节点的单向非循环链表)
  - - 2.1概念与结构
    - 2.2单链表的实现
    - 3.双向链表(带头节点的双向循环链表)
    - - 3.1结构
      - 3.2双向链表的实现
      - 4.顺序表和链表的对比
      - 4.1 存储结构
        4.2 内存管理
        4.3 适用场景
        🥇结语
        🎯引言
        
        欢迎来到HanLop博客的C语言数据结构初阶系列。在这个系列中，我们将深入探讨各种基本的数据结构和算法，帮助您打下坚实的编程基础。本次我将为你讲解链表。链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。由于其灵活的内存分配方式，链表在动态数据存储和处理方面有着独特的优势。在本篇文章中，我们将介绍链表的基本概念、链表的创建和操作方法，以及其优缺点。通过一些实际的代码示例，您将更好地掌握链表在C语言中的应用，从而为后续学习其他数据结构打下坚实的基础。
        
        👓链表
        
        1.链表的概念与分类
        
        1.1链表的概念 :
        
        链表是一种动态数据结构，由一系列节点（Node）组成。每个节点包含两部分：数据域（存储数据）和指针域（存储下一个节点的地址）。根据指针域的数量和方向
        
        1.2链表的分类:
        
        链表结构有很多种,如下图(2*2*2种):
        
        1. 带头节点的单向非循环链表
        
        带头节点的单向非循环链表在链表的开头有一个特殊的头节点，该头节点不存储实际数据，只用于指向第一个真正存储数据的节点。
        
        特点：
        
        增加了对链表操作的统一性，尤其是在链表为空或者操作第一个节点时更为方便。
        尾节点指针为NULL，表示链表的结束。
        2. 带头节点的单向循环链表
        
        带头节点的单向循环链表在链表的开头有一个头节点，尾节点的指针指向头节点，形成一个环。
        
        特点：
        
        可以从链表的任何一个节点回到头节点，形成一个闭环。
        常用于需要循环遍历的场景。
        3. 带头节点的双向非循环链表
        
        带头节点的双向非循环链表在链表的开头有一个头节点，每个节点有两个指针，分别指向前一个节点和后一个节点。
        
        特点：
        
        可以从链表的任何一个节点向前或向后遍历。
        尾节点的后指针为NULL，表示链表的结束。
        4.带头节点的双向循环链表
        
        带头节点的双向循环链表在链表的开头有一个头节点，每个节点有两个指针，尾节点的后指针指向头节点，头节点的前指针指向尾节点，形成一个环。
        
        特点：
        
        形成一个双向闭环，可以从链表的任何一个节点双向遍历回到头节点。
        常用于需要双向循环遍历的场景。
        5. 不带头节点的单向非循环链表
        
        不带头节点的单向非循环链表没有特殊的头节点，链表的第一个节点就是存储实际数据的节点。
        
        特点：
        
        节省了一个节点的内存，但在操作第一个节点时需要特殊处理。
        尾节点指针为NULL，表示链表的结束。
        6. 不带头节点的单向循环链表
        
        不带头节点的单向循环链表没有头节点，尾节点的指针指向第一个节点，形成一个环。
        
        特点：
        
        可以从链表的任何一个节点回到第一个节点，形成一个闭环。
        常用于需要循环遍历的场景。
        7. 不带头节点的双向非循环链表
        
        不带头节点的双向非循环链表没有头节点，每个节点有两个指针，分别指向前一个节点和后一个节点。
        
        特点：
        
        可以从链表的任何一个节点向前或向后遍历。
        尾节点的后指针为NULL，表示链表的结束。
        8. 不带头节点的双向循环链表
        
        不带头节点的双向循环链表没有头节点，每个节点有两个指针，尾节点的后指针指向第一个节点，第一个节点的前指针指向尾节点，形成一个环。
        
        特点：
        
        形成一个双向闭环，可以从链表的任何一个节点双向遍历回到第一个节点。
        常用于需要双向循环遍历的场景。
        如此多的种类,我们下面只实现两种,单向链表(不带头节点的单向非循环链表)和双向链表(带头节点的双向循环链表)学会这两种之后其他种类的链表也可以自己去实现
        
        2.单链表(不带头节点的单向非循环链表)
        
        2.1概念与结构
        
        概念:
        
        不带头节点的单链表没有特殊的头节点，链表的第一个节点就是存储实际数据的节点。所有操作均直接作用于链表的第一个节点。
        
        节点:
        
        在链表（特别是单链表）中，节点是链表的基本组成单位。每个节点包含两个主要部分：数据域和指针域。下面是对节点的详细解释。
        
        节点的定义
        
        在C语言中，节点通常使用结构体（struct）来定义。一个典型的单链表节点结构如下：
        
        struct Node { int data; // 数据域，用于存储节点的数据 struct Node* next; // 指针域，用于存储指向下一个节点的指针 };
        
        节点的组成
        
        数据域（data）：
        数据域存储链表中实际的数据。
        数据类型可以根据需求变化，例如int、float、char，甚至是复杂的结构体。
        在上述例子中，数据域的类型是int。
        指针域（next）：
        指针域存储指向下一个节点的指针。
        如果这是链表中的最后一个节点，则指针域存储NULL，表示链表的结束。
        在双向链表中，节点会包含两个指针域，一个指向下一个节点，一个指向前一个节点。
        结构图示:
        
        链表是由一个个节点所构成的,通过指针将每个节点联系起来。
        
        2.2单链表的实现
        
        SList.h源代码:
        
        //SList.h文件中 #pragma once #include #include #include typedef int SLDataTyped; typedef struct SListNode { SLDataTyped val; struct SListNode* next; }SListNode; //链表的打印 void SListPrint(SListNode* phead); //创建新节点 SListNode* SLBuyNode(SLDataTyped x); //头部插入删除/尾部插入删除 void SListPushFront(SListNode** pphead, SLDataTyped x); void SListPushBack(SListNode** pphead, SLDataTyped x); void SListPopBack(SListNode** pphead); void SListPopFront(SListNode** pphead); //查找 SListNode* SListFind(SListNode** pphead, SLDataTyped x); //在指定位置之前插入数据 void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x); //在指定位置之后插入数据 void SListInsertAfter(SListNode* pos, SLDataTyped x); //删除pos节点 void SListErase(SListNode** pphead, SListNode* pos); //删除pos之后的节点 void SListEraseAfter(SListNode* pos); //销毁链表 void SListDestory(SListNode** pphead);
        
        解析:
        
        数据结构定义
        
        typedef int SLDataTyped; typedef struct SListNode { SLDataTyped val; struct SListNode* next; } SListNode;
        
        SLDataTyped：定义链表中存储的数据类型，可以根据需要修改。
        SListNode：定义链表节点结构，包括数据域val和指针域next。
        函数声明及其作用
        
        创建新节点
        
        SListNode* SLBuyNode(SLDataTyped x);
        
        功能：创建一个新节点，并将其值设置为x。
        参数：节点的值。
        返回值：指向新创建节点的指针。
        打印链表
        
        void SListPrint(SListNode* phead);
        
        功能：遍历并打印整个链表。
        参数：链表的头指针。
        返回值：无。
        头部插入节点
        
        void SListPushFront(SListNode** pphead, SLDataTyped x);
        
        功能：在链表头部插入一个新节点。
        参数：链表的头指针的指针，插入节点的值。
        返回值：无。
        尾部插入节点
        
        void SListPushBack(SListNode** pphead, SLDataTyped x);
        
        功能：在链表尾部插入一个新节点。
        参数：链表的头指针的指针，插入节点的值。
        返回值：无。
        尾部删除节点
        
        void SListPopBack(SListNode** pphead);
        
        功能：删除链表尾部的节点。
        参数：链表的头指针的指针。
        返回值：无。
        头部删除节点
        
        void SListPopFront(SListNode** pphead);
        
        功能：删除链表头部的节点。
        参数：链表的头指针的指针。
        返回值：无。
        查找节点
        
        SListNode* SListFind(SListNode** pphead, SLDataTyped x);
        
        功能：在链表中查找值为x的节点。
        参数：链表的头指针的指针，查找的值。
        返回值：指向找到节点的指针，找不到返回NULL。
        在指定位置之前插入节点
        
        void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x);
        
        功能：在指定位置pos之前插入一个值为x的节点。
        参数：链表的头指针的指针，插入位置的节点指针，插入节点的值。
        返回值：无。
        在指定位置之后插入节点
        
        void SListInsertAfter(SListNode* pos, SLDataTyped x);
        
        功能：在指定位置pos之后插入一个值为x的节点。
        参数：插入位置的节点指针，插入节点的值。
        返回值：无。
        删除指定位置的节点
        
        void SListErase(SListNode** pphead, SListNode* pos);
        
        功能：删除链表中指定位置pos的节点。
        参数：链表的头指针的指针，要删除的节点指针。
        返回值：无。
        删除指定位置之后的节点
        
        void SListEraseAfter(SListNode* pos);
        
        功能：删除链表中指定位置pos之后的节点。
        参数：要删除其后节点的节点指针。
        返回值：无。
        销毁链表
        
        void SListDestory(SListNode** pphead);
        
        功能：销毁整个链表，释放所有节点的内存。
        参数：链表的头指针的指针。
        返回值：无。
        SList.c源代码:
        
        //SList.c文件中 #include "SList.h" void SListPrint(SListNode* phead) { //assert(phead); SListNode* pcur = phead; while (pcur) { printf("%d->", pcur->val); pcur = pcur->next; } printf("NULL\n"); } SListNode* SLBuyNode(SLDataTyped x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); newNode->val = x; newNode->next = NULL; return newNode; } void SListPushBack(SListNode** pphead, SLDataTyped x) { assert(pphead); SListNode* newNode = SLBuyNode(x); SListNode* pcur = *pphead; if (*pphead == NULL) { *pphead = newNode; } else { while (pcur->next) { pcur = pcur->next; } pcur->next = newNode; } } void SListPushFront(SListNode** pphead, SLDataTyped x) { assert(pphead); SListNode* newNode = SLBuyNode(x); SListNode* pcur = *pphead; if (*pphead == NULL) { *pphead = newNode; } else { newNode->next = *pphead; *pphead = newNode; } } void SListPopBack(SListNode** pphead) { assert(pphead&&*pphead); SListNode* pcur = *pphead; SListNode* prev = *pphead; if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { while (pcur->next) { prev = pcur; pcur = pcur->next; } free(pcur); pcur = NULL; prev->next = NULL; } } void SListPopFront(SListNode** pphead) { assert(pphead && *pphead); SListNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; } SListNode* SListFind(SListNode** pphead, SLDataTyped x) { assert(pphead && *pphead); SListNode* pcur = *pphead; while (pcur) { if (pcur->val == x) { return pcur; } pcur = pcur->next; } return NULL; } void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x) { assert(pphead&&*pphead); assert(pos); SListNode* pcur = *pphead; SListNode* prev = *pphead; //pos是头节点 if (pos == *pphead) { SListPushFront(pphead, x); } else { SListNode* newNode = SLBuyNode(x); while (pcur != pos) { prev = pcur; pcur = pcur->next; } prev->next = newNode; newNode->next = pos; } } void SListInsertAfter(SListNode* pos, SLDataTyped x) { assert(pos); SListNode* next = pos->next; SListNode* newNode = SLBuyNode(x); newNode->next = pos->next; pos->next = newNode; } void SListErase(SListNode** pphead, SListNode* pos, SLDataTyped x) { assert(pphead && *pphead); assert(pos); SListNode* prev = *pphead; SListNode* pcur = *pphead; //头删 if (pos == *pphead) { SListPopFront(pphead); } else { while (pcur != pos) { prev = pcur; pcur = pcur->next; } prev->next = pcur->next; free(pos); pos = NULL; pcur = NULL; } } void SListEraseAfter(SListNode* pos) { assert(pos&&pos->next); SListNode* next = pos->next; SListNode* Dnext = pos->next->next; pos->next = Dnext; free(next); next = NULL; } void SListDestory(SListNode** pphead) { assert(pphead && *pphead); SListNode* pcur = *pphead; SListNode* next = NULL; while (next) { next = pcur->next; free(pcur); pcur = NULL; } *pphead = NULL; }
        
        代码解析:
        
        打印链表 SListPrint
        
        void SListPrint(SListNode* phead) { SListNode* pcur = phead; while (pcur) { printf("%d -> ", pcur->val); pcur = pcur->next; } printf("NULL\n"); }
        
        功能：遍历链表并打印每个节点的值，以箭头形式连接每个节点。
        实现细节：
        使用一个指针 pcur 初始化为链表的头节点 phead。
        循环遍历链表直到 pcur 为空（即到达链表末尾）。
        打印当前节点的值 pcur->val，并移动到下一个节点 pcur = pcur->next。
        最后打印 "NULL" 表示链表结束。
        创建新节点 SLBuyNode
        
        SListNode* SLBuyNode(SLDataTyped x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (newNode == NULL) { printf("Memory allocation failed\n"); exit(1); } newNode->val = x; newNode->next = NULL; return newNode; }
        
        功能：创建一个新的链表节点并初始化其值和 next 指针。
        实现细节：
        使用 malloc 分配内存以存储新节点。
        检查内存分配是否成功，若失败则输出错误信息并退出程序。
        将新节点的 val 设置为参数 x，next 设置为 NULL，表示该节点为链表的末尾节点。
        返回指向新创建节点的指针。
        头部插入节点 SListPushFront
        
        void SListPushFront(SListNode** pphead, SLDataTyped x) { SListNode* newNode = SLBuyNode(x); // 创建一个新节点 newNode->next = *pphead; // 新节点的 next 指向当前头节点 *pphead = newNode; // 更新头节点指针，使其指向新节点 }
        
        功能：在链表的头部插入一个新节点。
        实现细节：
        创建一个新的节点 newNode 并将其值初始化为 x。
        将新节点的 next 指向当前的头节点 *pphead。
        更新头节点指针 *pphead，使其指向新节点 newNode。
        尾部插入节点 SListPushBack
        
        void SListPushBack(SListNode** pphead, SLDataTyped x) { SListNode* newNode = SLBuyNode(x); // 创建一个新节点 if (*pphead == NULL) { *pphead = newNode; // 若链表为空，直接将新节点设为头节点 } else { SListNode* pcur = *pphead; while (pcur->next) { pcur = pcur->next; // 找到链表的最后一个节点 } pcur->next = newNode; // 将新节点连接到链表的最后 } }
        
        功能：在链表的尾部插入一个新节点。
        实现细节：
        创建一个新的节点 newNode 并将其值初始化为 x。
        检查链表是否为空（即 *pphead == NULL），如果是，直接将新节点设为头节点。
        如果链表不为空，使用 pcur 指针遍历链表直到找到最后一个节点。
        将最后一个节点的 next 指针指向新节点 newNode，完成插入操作。
        头部删除节点 SListPopFront
        
        void SListPopFront(SListNode** pphead) { assert(pphead && *pphead); // 断言链表和头节点都存在 SListNode* del = *pphead; // 记录要删除的节点 *pphead = (*pphead)->next; // 更新头节点指针，使其指向下一个节点 free(del); // 释放被删除的节点的内存 }
        
        功能：删除链表的头部节点。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在。
        创建一个临时指针 del，指向要删除的节点 *pphead。
        更新头节点指针 *pphead，使其指向下一个节点 (*pphead)->next。
        释放被删除节点 del 的内存，防止内存泄漏。
        尾部删除节点 SListPopBack
        
        void SListPopBack(SListNode** pphead) { assert(pphead && *pphead); // 断言链表和头节点都存在 if (*pphead == NULL) { return; // 如果链表为空，直接返回 } SListNode* pcur = *pphead; SListNode* prev = NULL; while (pcur->next) { prev = pcur; pcur = pcur->next; // 找到链表的倒数第二个节点 } if (prev == NULL) { free(*pphead); // 若链表只有一个节点，直接释放头节点 *pphead = NULL; } else { free(pcur); // 释放最后一个节点的内存 prev->next = NULL; // 断开倒数第二个节点与最后一个节点的连接 } }
        
        功能：删除链表的尾部节点。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在。
        如果链表为空（即 *pphead == NULL），直接返回，不进行删除操作。
        使用 pcur 指针和 prev 指针找到链表的倒数第二个节点 prev 和最后一个节点 pcur。
        如果 prev 为 NULL，表示链表只有一个节点，直接释放头节点 *pphead。
        否则，释放最后一个节点 pcur 的内存，并断开 prev->next 指针与 pcur 的连接，完成删除操作。
        查找节点 SListFind
        
        SListNode* SListFind(SListNode** pphead, SLDataTyped x) { assert(pphead && *pphead); // 断言链表和头节点都存在 SListNode* pcur = *pphead; while (pcur) { if (pcur->val == x) { return pcur; // 找到值为 x 的节点，返回该节点指针 } pcur = pcur->next; // 继续遍历下一个节点 } return NULL; // 遍历完链表未找到，返回 NULL }
        
        功能：在链表中查找值为 x 的节点。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在。
        使用 pcur 指针遍历整个链表。
        如果找到节点值等于 x 的节点，返回该节点的指针 pcur。
        如果遍历完整个链表都没有找到值为 x 的节点，返回 NULL。
        在指定位置之前插入节点 SListInsert
        
        void SListInsert(SListNode** pphead, SListNode* pos, SLDataTyped x) { assert(pphead && *pphead); // 断言链表和头节点都存在 assert(pos); // 断言插入位置 pos 存在 SListNode* pcur = *pphead; SListNode* prev = NULL; if (pos == *pphead) { SListPushFront(pphead, x); // 如果插入位置是头节点，则调用头部插入函数 } else { SListNode* newNode = SLBuyNode(x); // 创建新节点 while (pcur != pos) { prev = pcur; pcur = pcur->next; // 找到插入位置的前一个节点 prev 和插入位置节点 pos } prev->next = newNode; // 将新节点插入到 prev 和 pos 之间 newNode->next = pos; } }
        
        功能：在链表中指定位置 pos 之前插入一个新节点。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在，以及插入位置 pos 存在。
        创建 pcur 和 prev 指针，用于遍历链表和记录插入位置的前一个节点。
        如果插入位置 pos 是头节点 *pphead，则调用 SListPushFront 函数在头部插入节点。
        否则，创建新节点 newNode 并找到 pos 的前一个节点 prev。
        将新节点 newNode 插入到 prev 和 pos 之间，完成插入操作。
        在指定位置之后插入节点 SListInsertAfter
        
        void SListInsertAfter(SListNode* pos, SLDataTyped x) { assert(pos); // 断言插入位置 pos 存在 SListNode* newNode = SLBuyNode(x); // 创建新节点 newNode->next = pos->next; // 将新节点的 next 指向 pos 的下一个节点 pos->next = newNode; // 将 pos 的 next 指向新节点，完成插入操作 }
        
        功能：在链表中指定位置 pos 之后插入一个新节点。
        实现细节：
        使用断言 assert 确保插入位置 pos 存在。
        创建新节点 newNode 并将其值初始化为 x。
        将新节点 newNode 的 next 指针指向 pos 的下一个节点 pos->next。
        将 pos 的 next 指针指向新节点 newNode，完成插入操作。
        删除指定节点 SListErase
        
        void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead && *pphead); // 断言链表和头节点都存在 assert(pos); // 断言要删除的位置 pos 存在 SListNode* prev = *pphead; SListNode* pcur = *pphead; if (pos == *pphead) { SListPopFront(pphead); // 如果要删除的位置是头节点，则调用头部删除函数 } else { while (pcur != pos) { prev = pcur; pcur = pcur->next; // 找到要删除位置的前一个节点 prev 和要删除的节点 pos } prev->next = pcur->next; // 将 prev 的 next 指向 pos 的下一个节点，跳过 pos free(pos); // 释放 pos 节点的内存 } }
        
        功能：删除链表中指定位置 pos 的节点。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在，以及要删除的位置 pos 存在。
        创建 prev 和 pcur 指针，用于遍历链表和记录要删除的位置 pos。
        如果要删除的位置 pos 是头节点 *pphead，则调用 SListPopFront 函数删除头部节点。
        否则，找到 pos 的前一个节点 prev 和要删除的节点 pos。
        将 prev 的 next 指针指向 pos 的下一个节点 pcur->next，跳过要删除的节点 pos。
        释放要删除节点 pos 的内存，完成删除操作。
        删除指定节点之后的节点 SListEraseAfter
        
        void SListEraseAfter(SListNode* pos) { assert(pos && pos->next); // 断言插入位置 pos 和 pos 的下一个节点存在 SListNode* next = pos->next; pos->next = next->next; // 将 pos 的 next 指向 pos 的下下一个节点 free(next); // 释放 pos 的下一个节点的内存 }
        
        功能：删除链表中指定位置 pos 的下一个节点。
        实现细节：
        使用断言 assert 确保插入位置 pos 存在，且 pos 的下一个节点 pos->next 存在。
        创建 next 指针指向 pos 的下一个节点。
        将 pos 的 next 指针指向 next 的下一个节点 next->next，跳过 next 节点。
        释放 next 节点的内存，完成删除操作。
        销毁链表 SListDestory
        
        void SListDestory(SListNode** pphead) { assert(pphead && *pphead); // 断言链表和头节点都存在 SListNode* pcur = *pphead; while (pcur) { SListNode* next = pcur->next; // 记录下一个节点的指针 free(pcur); // 释放当前节点的内存 pcur = next; // 移动到下一个节点 } *pphead = NULL; // 将头节点指针设为 NULL，完成销毁操作 }
        
        功能：销毁整个链表并释放所有节点的内存。
        实现细节：
        使用断言 assert 确保链表和头节点 *pphead 存在。
        使用 pcur 指针遍历整个链表，依次释放每个节点的内存。
        在释放当前节点 pcur 内存之前，记录下一个节点的指针 next。
        将 pcur 移动到下一个节点 next，继续循环直到链表所有节点都被释放。
        最后将头节点指针 *pphead 设为 NULL，完成销毁链表的操作。
        3.双向链表(带头节点的双向循环链表)
        
        3.1结构
        
        图示:
        
        3.2双向链表的实现
        
        List.h源代码:
        
        //List.h文件 #pragma once #include #include #include typedef int LTDataType; typedef struct ListNode { LTDataType x; struct ListNode* prev; struct ListNode* next; }ListNode; void ListInit(ListNode** phead); //申请新的节点 ListNode* BuyListNode(LTDataType x); //打印节点 void ListPrint(ListNode* phead); //尾插尾删/头插头删 void ListPushBack(ListNode* phead, LTDataType x); void ListPushFront(ListNode* phead, LTDataType x); void ListPopBack(ListNode* phead); void ListPopFront(ListNode* phead); //查找 ListNode* ListFind(ListNode* phead,LTDataType x); //在pos位置之后插入数据 void ListInsert(ListNode* pos, LTDataType x); //删除pos位置的数据 void ListErase(ListNode* pos); //链表的销毁 void ListDestory(ListNode** pphead);
        
        源码解析:
        
        头文件保护和包含的头文件
        
        #pragma once #include #include #include
        
        功能：使用 #pragma once 实现头文件的单次包含保护，避免多重包含问题。
        头文件：包含了 stdio.h（标准输入输出）、stdlib.h（标准库函数）、assert.h（断言）。
        定义节点结构体和数据类型
        
        typedef int LTDataType; typedef struct ListNode { LTDataType x; struct ListNode* prev; struct ListNode* next; } ListNode;
        
        功能：定义了双向链表的节点结构体 ListNode 和节点值的数据类型 LTDataType。
        结构体成员：
        x：节点的数据成员。
        prev：指向前一个节点的指针。
        next：指向后一个节点的指针。
        1. void ListInit(ListNode** phead);
        
        功能：初始化双向链表。
        参数：指向链表头节点指针的指针 phead。通过修改 phead 的值来更新链表头指针。
        2. ListNode* BuyListNode(LTDataType x);
        
        功能：申请并返回一个新的链表节点。
        参数：节点的数据成员的值 x。
        返回值：指向新节点的指针。
        3. void ListPrint(ListNode* phead);
        
        功能：打印双向链表的所有节点值。
        参数：指向链表头节点的指针 phead。
        4. void ListPushBack(ListNode* phead, LTDataType x);
        
        功能：在链表尾部插入一个新节点。
        参数：指向链表头节点的指针 phead，新节点的数据成员的值 x。
        5. void ListPushFront(ListNode* phead, LTDataType x);
        
        功能：在链表头部插入一个新节点。
        参数：指向链表头节点的指针 phead，新节点的数据成员的值 x。
        6. void ListPopBack(ListNode* phead);
        
        功能：删除链表尾部的节点。
        参数：指向链表头节点的指针 phead。
        7. void ListPopFront(ListNode* phead);
        
        功能：删除链表头部的节点。
        参数：指向链表头节点的指针 phead。
        8. ListNode* ListFind(ListNode* phead, LTDataType x);
        
        功能：查找链表中第一个值为 x 的节点。
        参数：指向链表头节点的指针 phead，要查找的值 x。
        返回值：指向找到的节点的指针，若未找到则返回 NULL。
        9. void ListInsert(ListNode* pos, LTDataType x);
        
        功能：在指定节点 pos 后插入一个新节点。
        参数：指定位置节点的指针 pos，新节点的数据成员的值 x。
        10. void ListErase(ListNode* pos);
        
        功能：删除指定节点 pos。
        参数：指向链表中待删除节点的指针 pos。
        11. void ListDestory(ListNode** pphead);
        
        功能：销毁整个链表及其所有节点。
        参数：指向链表头节点指针的指针 pphead。通过将所有节点释放，并将 *pphead 设置为 NULL 来实现。
        List.c源码
        
        //List.c文件 #include "List.h" void ListInit(ListNode** phead) { assert(phead); *phead = (ListNode*)malloc(sizeof(ListNode)); (*phead)->x = -1; (*phead)->next = *phead; (*phead)->prev = *phead; } ListNode* BuyListNode(LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->x = x; newNode->next = newNode; newNode->prev = newNode; return newNode; } void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newNode = BuyListNode(x); newNode->next = phead; newNode->prev = tail; tail->next = newNode; phead->prev = newNode; } void ListPrint(ListNode* phead) { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->x); pcur = pcur->next; } printf("\n"); } void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newNode = BuyListNode(x); phead->next->prev = newNode; newNode->next = phead->next; newNode->prev = phead; phead->next = newNode; } void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; } void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* del = phead->next; phead->next = del->next; del->next->prev = phead; free(del); del = NULL; } ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); assert(phead->next != phead); ListNode* pcur = phead->next; while (pcur != phead) { if (pcur->x == x) { return pcur; } pcur = pcur->next; } return NULL; } void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newNode = BuyListNode(x); pos->next->prev = newNode; newNode->next = pos->next; newNode->prev = pos; pos->next = newNode; } void ListErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos == NULL; } void ListDestory(ListNode** pphead) { assert(pphead); assert(*pphead != NULL); ListNode* pcur = (*pphead)->next; ListNode* next = pcur->next; while (pcur != *pphead) { free(pcur); pcur = next; next = pcur->next; } free(*pphead); *pphead = NULL; }
        
        源码解析:
        
        1. void ListInit(ListNode** phead)
        
        void ListInit(ListNode** phead) { assert(phead); *phead = (ListNode*)malloc(sizeof(ListNode)); (*phead)->x = -1; (*phead)->next = *phead; (*phead)->prev = *phead; }
        
        功能：初始化双向循环链表。
        
        实现过程：
        
        使用 malloc 分配内存以存储头节点。
        将头节点的数据域 x 初始化为 -1，表示头节点。
        将头节点的 next 和 prev 指针都指向自身，形成一个空链表的循环结构。
        2. ListNode* BuyListNode(LTDataType x)
        
        ListNode* BuyListNode(LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->x = x; newNode->next = newNode; newNode->prev = newNode; return newNode; }
        
        功能：申请并返回一个新的链表节点。
        
        实现过程：
        
        使用 malloc 分配内存以存储新节点。
        将新节点的数据域 x 初始化为参数 x。
        将新节点的 next 和 prev 指针都指向自身，表示新节点单独存在时的循环结构。
        3. void ListPrint(ListNode* phead)
        
        void ListPrint(ListNode* phead) { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->x); pcur = pcur->next; } printf("\n"); }
        
        功能：打印双向循环链表的所有节点值。
        
        实现过程：
        
        从链表的第一个节点开始遍历，直到回到头节点 phead。
        使用 printf 打印每个节点的数据域 x 的值，并在末尾输出换行符。
        4. void ListPushBack(ListNode* phead, LTDataType x)
        
        void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newNode = BuyListNode(x); newNode->next = phead; newNode->prev = tail; tail->next = newNode; phead->prev = newNode; }
        
        功能：在链表尾部插入一个新节点。
        
        实现过程(在实现这些函数时我们都需要画图辅组我们写代码.)：
        
        找到链表尾部节点 tail，即 phead->prev。
        创建一个新节点 newNode，并将其 next 指向头节点 phead，将其 prev 指向 tail。
        更新 tail 和 phead 的 next 和 prev 指针，使新节点插入到尾部。
        图示:
        
        5. void ListPushFront(ListNode* phead, LTDataType x)
        
        void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newNode = BuyListNode(x); phead->next->prev = newNode; newNode->next = phead->next; newNode->prev = phead; phead->next = newNode; }
        
        功能：在链表头部插入一个新节点。
        
        实现过程：
        
        创建一个新节点 newNode。
        将新节点的 next 指向头节点的 next，将新节点的 prev 指向头节点 phead。
        更新头节点 phead 和原头节点的 next 节点的 prev 指针，使新节点插入到头部。
        6. void ListPopBack(ListNode* phead)
        
        void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; }
        
        功能：删除链表尾部的节点。
        
        实现过程：
        
        找到链表尾部节点 del，即 phead->prev。
        更新 del 节点前后节点的 next 和 prev 指针，使尾部节点从链表中删除。
        释放 del 节点的内存。
        7. void ListPopFront(ListNode* phead)
        
        void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* del = phead->next; phead->next = del->next; del->next->prev = phead; free(del); del = NULL; }
        
        功能：删除链表头部的节点。
        
        实现过程：
        
        找到头部节点 del，即 phead->next。
        更新头节点 phead 和原头节点的 next 节点的 prev 指针，使头部节点从链表中删除。
        释放 del 节点的内存。
        8. ListNode* ListFind(ListNode* phead, LTDataType x)
        
        ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); assert(phead->next != phead); ListNode* pcur = phead->next; while (pcur != phead) { if (pcur->x == x) { return pcur; } pcur = pcur->next; } return NULL; }
        
        功能：查找链表中第一个值为 x 的节点。
        
        实现过程：
        
        从链表的第一个节点开始遍历，直到回到头节点 phead。
        比较每个节点的数据域 x 和参数 x，找到匹配的节点则返回其指针，否则返回 NULL。
        9. void ListInsert(ListNode* pos, LTDataType x)
        
        void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newNode = BuyListNode(x); pos->next->prev = newNode; newNode->next = pos->next; newNode->prev = pos; pos->next = newNode; }
        
        功能：在指定节点 pos 后插入一个新节点。
        
        实现过程：
        
        创建一个新节点 newNode。
        将新节点的 next 指向 pos 节点的 next，将新节点的 prev 指向 pos 节点。
        更新 pos 节点和 pos 后面节点的 prev 指针，使新节点插入到指定位置。
        10. void ListErase(ListNode* pos)
        
        void ListErase(ListNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
        
        功能：删除指定节点 pos。
        
        实现过程：
        
        更新 pos 节点前后节点的 next 和 prev 指针，使节点 pos 从链表中删除。
        释放 pos 节点的内存。
        11. void ListDestory(ListNode** pphead)
        
        void ListDestory(ListNode** pphead) { assert(pphead); assert(*pphead != NULL); ListNode* pcur = (*pphead)->next; ListNode* next = pcur->next; while (pcur != *pphead) { free(pcur); pcur = next; next = pcur->next; } free(*pphead); *pphead = NULL; }
        
        功能：销毁整个链表及其所有节点。
        
        实现过程：
        
        从链表的第一个节点开始，逐个释放每个节点的内存，直到回到头节点。
        最后释放头节点的内存，并将 *pphead 置为 NULL。
        4.顺序表和链表的对比
        
        4.1 存储结构
        
        顺序表（数组）：
        存储方式：使用一段连续的内存空间存储元素，通过索引访问元素。
        特点：随机访问速度快，时间复杂度为 O(1)；插入和删除元素时，需要移动大量元素，时间复杂度为 O(n)。
        链表：
        存储方式：使用不连续的内存空间，每个节点存储数据和指向下一个节点的指针。
        特点：插入和删除元素方便，时间复杂度为 O(1)，只需修改指针；随机访问效率较低，需从头节点遍历到目标节点，时间复杂度为 O(n)。
        4.2 内存管理
        
        顺序表：
        内存管理：动态顺序表在实现时通常会预留一定的空间，当元素数量超过当前容量时，会动态扩展内存空间。这通常涉及到重新分配更大的内存块，并将原有数据复制到新的内存中，然后释放旧内存。
        优点：在元素数量不断增加时，仍然可以保持高效的随机访问性能，而且相比静态顺序表更加灵活。
        缺点：动态扩展和内存重新分配可能会导致性能开销，特别是在频繁操作大量数据时。
        链表：
        内存分配：节点动态分配，每个节点独立管理内存。
        优点：插入和删除效率高，不会造成内存碎片。
        缺点：每个节点额外需要存储指针信息，占用更多内存空间；随机访问效率低下。
        4.3 适用场景
        
        顺序表：
        当需要高效的随机访问
        链表：
        当需要频繁插入和删除操作，而不关心随机访问效率时。
        🥇结语
        
        通过本篇文章的学习，您应该已经掌握了链表的基本概念、创建和操作方法，以及链表在C语言中的应用。链表作为一种灵活且高效的线性数据结构，在许多编程场景中都有广泛的应用。希望通过这些知识，您能够更好地理解和运用链表，从而为进一步学习和掌握更复杂的数据结构打下坚实的基础。感谢您阅读HanLop博客，期待在下一篇文章中继续与您探讨更多有趣的数据结构和算法。