【C语言】探索数据结构：单链表和双链表
💡链表的概念和结构
💡链表的分类
💡无头单向非循环链表（单链表）的实现
定义节点结构
单链表的尾部插入
单链表的头部插入
单链表的尾部删除
单链表的头部删除
在指定位置插入前数据
在指定位置之后插入数据
删除结点
销毁链表
完整实现
💡带头双向循环链表的实现
定义节点结构
创建新节点
链表的初始化
双向链表的遍历打印
双向链表的尾插
双向链表的头插
完整实现
💡链表和顺序表（数组）的对比
💡链表的概念和结构
概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
以单链表为例：
可以看出：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的节点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
💡链表的分类
虽然说有8种链表结构，但是现实中主要使用的只有两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了。
💡无头单向非循环链表（单链表）的实现
定义节点结构
- 用 typedef 重定义要保存的数据类型，方便修改，灵活处理
- 节点之间用指针相连，每一个节点都会保存下一个节点的地址，指向下一个节点
//定义链表节点的结构 typedef int SLDataType; typedef struct SListNode { SLDataType data;//要保存的数据 struct SListNode* next; }SLNode;单链表的尾部插入
这里需要注意的是，插入时可能头节点为空，要改变指针，所以要传二级指针
//尾插 void SLPushBack(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* node = SLBuyNode(x); if (*pphead == NULL) { *pphead = node;//改变结构体指针，即指向结构体的指针 return; } //说明链表不为空，找尾 SLNode* pcur = *pphead; while (pcur->next) { pcur = pcur->next; } pcur->next = node;//改变结构体成员，pcur->next通过指针结构体的pcur指针访问结构体的next成员 }单链表的头部插入
//头插 void SLPushFront(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* node = SLBuyNode(x); //新节点跟头节点连起来 node->next = *pphead; //让新的节点称为头节点 *pphead = node; }单链表的尾部删除
删除时因为要释放空间，所以要传递二级指针
注意：
- 可能只有一个节点
- 可能有多个节点
- 不同情况不同处理
//尾删 void SLPopBack(SLNode** pphead) { assert(pphead); //第一个节点不能为空 assert(*pphead); //只有第一个节点的情况 if ((*pphead)->next == NULL) { //直接把头节点删除 free(*pphead); *pphead = NULL; } else { //有多个节点的情况 //找尾节点和尾节点的前一个节点 SLNode* prev = NULL; SLNode* ptail = *pphead; while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } //prev的指针不再指向ptail,而是指向ptail的下一个节点 prev->next = ptail->next; free(ptail); //打印链表的函数里会判断是否为NULL ptail = NULL; } }单链表的头部删除
先保存头节点，然后将原来头节点的下一个节点变成新的头节点，最后释放掉原来的头节点
//头删 void SLPopFront(SLNode** pphead) { assert(*pphead); assert(pphead); SLNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; }在指定位置插入前数据
插入位置：
- 头部位置的插入（需要改变头节点）
- 非链表头部位置的插入
//在指定位置之前插入数据 void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) { assert(pphead); //约定链表不能为空，pos也不能为空 assert(pos); assert(*pphead); SLNode* node = SLBuyNode(x); //pos是头节点，头插 if (pos == *pphead) { node->next = *pphead; *pphead = node; return; } //找pos的前一个节点 SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } // prev->node->pos node->next = pos; prev->next = node; }在指定位置之后插入数据
各种情况处理方法都一样，不需要特殊处理
//在指定位置之后插入数据 void SLInsertAfter(SLNode* pos, SLDataType x) { assert(pos); SLNode* node = SLBuyNode(x); //pos node pos->next node->next = pos->next; pos->next = node; return; }删除结点
- 删除头节点，需要将下一个节点设置为新的头节点
- 删除其他位置的节点，需要将该节点的前一个节点和后一个节点连接起来
//删除pos节点 void SLErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); //如果pos是头节点 if (pos == *pphead) { *pphead = (*pphead)->next; free(pos); return; } SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //prev pos pos->next prev->next = pos->next; free(pos); pos = NULL; }销毁链表
注意：先保存下一个节点的地址，再释放节点
//销毁链表 void SLDesTroy(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* pcur = *pphead; while (pcur->next != NULL) { SLNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }完整实现
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" void SLPrint(SLNode* phead) { //循环打印 SLNode* pcur = phead; while (pcur != NULL) { printf("%d->", pcur->data); pcur = pcur->next; } printf("NULL\n"); } //创建的新节点 SLNode* SLBuyNode(SLDataType x) { SLNode* node = (SLNode*)malloc(sizeof(SLNode)); node->data = x; node->next = NULL; return node; } //尾插 void SLPushBack(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* node = SLBuyNode(x); if (*pphead == NULL) { *pphead = node;//改变结构体指针，即指向结构体的指针 return; } //说明链表不为空，找尾 SLNode* pcur = *pphead; while (pcur->next) { pcur = pcur->next; } pcur->next = node;//改变结构体成员，pcur->next通过指针结构体的pcur指针访问结构体的next成员 } //头插 void SLPushFront(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* node = SLBuyNode(x); //新节点跟头节点连起来 node->next = *pphead; //让新的节点称为头节点 *pphead = node; } //尾删 void SLPopBack(SLNode** pphead) { assert(pphead); //第一个节点不能为空 assert(*pphead); //只有第一个节点的情况 if ((*pphead)->next == NULL) { //直接把头节点删除 free(*pphead); *pphead = NULL; } else { //有多个节点的情况 //找尾节点和尾节点的前一个节点 SLNode* prev = NULL; SLNode* ptail = *pphead; while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } //prev的指针不再指向ptail,而是指向ptail的下一个节点 prev->next = ptail->next; free(ptail); //打印链表的函数里会判断是否为NULL ptail = NULL; } } //头删 void SLPopFront(SLNode** pphead) { assert(*pphead); assert(pphead); SLNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; } //查找第一个为x的节点 SLNode* SLFind(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* pcur = *pphead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } //在指定位置之前插入数据 void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) { assert(pphead); //约定链表不能为空，pos也不能为空 assert(pos); assert(*pphead); SLNode* node = SLBuyNode(x); //pos是头节点，头插 if (pos == *pphead) { node->next = *pphead; *pphead = node; return; } //找pos的前一个节点 SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } // prev->node->pos node->next = pos; prev->next = node; } //在指定位置之后插入数据 void SLInsertAfter(SLNode* pos, SLDataType x) { assert(pos); SLNode* node = SLBuyNode(x); //pos node pos->next node->next = pos->next; pos->next = node; return; } //删除pos节点 void SLErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); //如果pos是头节点 if (pos == *pphead) { *pphead = (*pphead)->next; free(pos); return; } SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //prev pos pos->next prev->next = pos->next; free(pos); pos = NULL; } //删除pos之后节点 void SLEraseAfter(SLNode* pos) { assert(pos&&pos->next); //pos pos->next pos->next->next SLNode* del = pos->next; pos->next = pos->next->next; free(del); del = NULL; } //销毁链表 void SLDesTroy(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* pcur = *pphead; while (pcur->next != NULL) { SLNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }💡带头双向循环链表的实现
带头双向循环链表是双向链表的一种特殊形式，它有以下特点：
- 带头：链表中有一个头节点，它不存储实际数据，只用于标识链表的起始位置。
- 双向：每个节点有两个指针，分别指向前一个节点和后一个节点。
- 循环：链表的最后一个节点指向头节点，形成一个循环。
定义节点结构
// 带头双向链表 typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode;创建新节点
新节点的前驱指针和后驱指针都设置为NULL
//创建新节点 ListNode* SLBuyNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->_data = x; node->_next = NULL; node->_prev = NULL; return node; }链表的初始化
初始化主要是对链表的头--哨兵节点进行操作，它不保存具体的值（可以随便设置），它的存在可以确保链表一定不为空
//初始化 void InitList(ListNode** pHead) { *pHead = SLBuyNode(-1); (*pHead)->_next = (*pHead); (*pHead)->_prev = (*pHead); }双向链表的遍历打印
由于哨兵位不起到保存数据的作用，所以在遍历打印时也会从头节点的下一个节点开始
// 双向链表打印 void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; printf("哨兵位"); while (cur!=pHead) { printf("%d", cur->_data); cur = cur->_next; } printf("\n"); }双向链表的尾插
由于这是一个循环链表，所以尾插实际上就是在头节点的左边插入，下面写了两种插入方法
// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* node = SLBuyNode(x); //方法一 //ListNode* tail = pHead->_prev; //tail->_next = node; //node->_prev = tail; //pHead->_prev = node; //node->_next = pHead; //方法二 node->_prev = pHead->_prev; pHead->_prev->_next = node; node->_next = pHead; pHead->_prev = node; }双向链表的头插
头插是在哨兵位节点和它的下一个节点之间插入
// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* node = SLBuyNode(x); node->_next = pHead->_next; pHead->_next->_prev = node; pHead->_next = node; node->_prev = pHead; }完整实现
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" //创建新节点 ListNode* SLBuyNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->_data = x; node->_next = NULL; node->_prev = NULL; return node; } //初始化 void InitList(ListNode** pHead) { *pHead = SLBuyNode(-1); (*pHead)->_next = (*pHead); (*pHead)->_prev = (*pHead); } // 双向链表打印 void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; printf("哨兵位"); while (cur!=pHead) { printf("%d", cur->_data); cur = cur->_next; } printf("\n"); } // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* node = SLBuyNode(x); //方法一 //ListNode* tail = pHead->_prev; //tail->_next = node; //node->_prev = tail; //pHead->_prev = node; //node->_next = pHead; //方法二 node->_prev = pHead->_prev; pHead->_prev->_next = node; node->_next = pHead; pHead->_prev = node; } // 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->_next != pHead); ListNode* del = pHead->_prev; ListNode* next = pHead->_prev->_prev; pHead->_prev = next; next->_next = pHead; free(del); del = NULL; } // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* node = SLBuyNode(x); node->_next = pHead->_next; pHead->_next->_prev = node; pHead->_next = node; node->_prev = pHead; } // 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead); assert(pHead->_next != pHead); ListNode* del = pHead->_next; ListNode* next = del->_next; pHead->_next = next; next->_prev = pHead; free(del); del = NULL; } // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { if (cur->_data == x) { return cur; } cur = cur->_next; } return NULL; } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* node = SLBuyNode(x); ListNode* prev = pos->_prev; prev->_next = node; node->_prev = prev; node->_next = pos; pos->_prev = node; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* del = pos; ListNode* prev = pos->_prev; prev->_next = pos->_next; pos->_next->_prev = prev; free(del); del = NULL; } void ListDestory(ListNode* pHead) { ListNode* cur = pHead->next; while (cur != pHead) { ListNode* next = cur->next; free(cur); cur = next; } free(pHead); }💡链表和顺序表（数组）的对比
不同点 顺序表 链表 存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续 随机访问 支持O(1) 不支持：O(N) 任意位置插入或者删除元素 可能需要移动元素，效率低，O(N) 只需修改指针指向 插入 动态顺序表，空间不够时需要 扩容 没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁 缓存利用率 高 低 _____________________________________________________________________________
⭐感谢你的阅读，希望本文能够对你有所帮助。如果你喜欢我的内容，记得点赞关注收藏我的博客，我会继续分享更多的内容。⭐
相关阅读：
1、塔式服务器和机架式服务器哪个小?，塔式vs机架式，谁才是真正的空间节省王者？，塔式VS机架式，谁才是数据中心的空间霸主？
2、服务器属于哪个省份?，你的服务器究竟藏在哪个省？揭秘数据背后的地理位置！，你的数据到底藏在哪？揭秘服务器不为人知的真实省份！
3、成都服务器哪个最多?，成都服务器哪家最多？揭秘当地数据中心霸主！，成都哪家数据中心拥有最多的服务器？揭秘行业霸主！
4、服务器放在海里的是哪个?，微软竟把服务器沉入海底？揭秘全球首个海底数据中心！，微软为何将服务器沉入海底？全球首个海底数据中心大揭秘！
5、Vivix Linux，Vivix Linux，这款神秘的操作系统能否挑战Windows和MacOS的霸主地位？，Vivix Linux，这款神秘系统真能撼动Windows和MacOS的统治地位吗？
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理!
部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理!
图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
