【数据结构入坑指南（三.1）】--《面试必看：单链表与顺序表之争，读懂“不连续”之美背后的算法思想》
🔥@晨非辰Tong：个人主页
💪学习阶段：C语言、数据结构与算法初学者
⏳“人理解迭代，神理解递归。”
引言：学完顺序表，深受其扩容和插入删除低效之苦？
是时候认识单链表了。它用指针串联数据，以“不连续”的物理结构，完美解决了顺序表的痛点。
接下来，让我们一起探索这种更优雅的数据结构。
目录
一、单链表特性全解
1.1 单链表：数据的"一线牵"
--在学习顺序表时，发现有几个缺陷：
- 中间/头部的插入、删除，时间复杂度为O(N)；
- 增容要申请新空间，拷贝数据，释放旧空间，有消耗；
- 增容一般呈两倍增长，会空间浪费；
--由于对上面的思考（改善），引入单链表：
--链表：链表是一种是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序通过链表的指针链接次序实现。
1.2 单链表结构：数据的“小火车”
--链表的逻辑结构是线性的，可想象成一列火车拉着一节一节的车厢：
--对于这种结构，每个车厢都是独立空间，且将车厢称为节点，由两部分组成：存储的数据；下一节点的地址；
-- plist 保存第一个节点的地址（指向第一个节点），通过修改 plist 保存的内容可以实现指向不同的节点。
--注意：需要插入数据时才会申请一块节点大小的空间
--而在堆空间申请空间，节点不一定时整齐排放（物理结构不一定连续），但每个节点都存者下一节点的地址，就通过这种方式进行连接。
二、单链表的实现（初）
2.1 铺垫
--先简单实现以下单链表的打印：
SList.h #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> //链表基本结构_节点结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//存数据 struct SListNode* next;//存储下一节点地址 }SLTNode;//重命名_节点 //或者——> typedef struct SListNode SLTNode; ——————————————————————————————————————————————————————————————————————————————————— //声明_打印函数 void SLTPrint(SLTNode* phead);//phead指向第一个节点，后续通过地址调换节点SList.c #include "SList.h" //定义_打印函数 void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead;//临时赋值 //循环打印 while (pcur != NULL) { printf("%d -> ", pcur->data);//输出数据 pcur = pcur->next;//指向下一节点 } printf("NULL\n"); } //对于循环条件，pcur存储首节点地址，当经过循环内的地址跳转，最终指向NULL结束 ————————————————————————————————————————————————————————————————————————————————— test.c int test01() { //创建链表—>节点之间的链接 SLTNode* node1 = (SLTNode*) malloc(sizeof(SLTNode)); SLTNode* node2 = (SLTNode*) malloc(sizeof(SLTNode)); SLTNode* node3 = (SLTNode*) malloc(sizeof(SLTNode)); SLTNode* node4 = (SLTNode*) malloc(sizeof(SLTNode)); //初始化_赋值链表 //存储数据 node1->data = 1; node2->data = 2; node3->data = 3; node4->data = 4; //链接地址 node1->next = node2;//node存储的是地址 node2->next = node3; node3->next = node4; node4->next = NULL; //打印链表 SLTNode* phead = node1; SLTPrint(phead); } int main() { test01(); return 0; }
2.2 单链表尾插
--在后续进行的头插等都需要申请新的节点空间，先封装函数：
SList.c //定义_申请节点 SLTNode* SLTBuyNode(SLTDataType x) { //申请一个节点大小的空间 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; }--实现尾插
SList.c //定义_尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x)//应用时传地址，二级指针接收 { //申请新节点空间->插入数据 SLTNode* newnode = SLTBuyNode(x);//node->存储着新空间的地址 //链表一开始为空 //pphead->二级指针变量—>存储一级指针变量的地址 if (*pphead == NULL)//解引用(phead本身)判断链表是否为空 { *pphead = newnode;//测试端的指针（phead）指向新空间 } //链表不为空 else { //遍历找到尾节点（空地址），插入新节点 SLTNode* ptail = *pphead;//防止*pphead指向发生变化 while (ptail->next != NULL) { ptail = ptail->next;//向后遍历 } //循环外找到地址为空节点->插入新节点 ptail->next = newnode; } } 首先判断为空，将申请节点作首节点；非空，遍历找到尾节点—>next=NULL，将newnode给next，完成地址链接。
--注意：尾插函数参数是二级指针，进行传址，接收指针（plist）地址。
test.c void test02() { //创建空链表 SLTNode* phead = NULL;//首节点为空 //尾插 SLTPushBack(&phead, 1);//为了使形参的变化影响实参，传地址 SLTPushBack(&phead, 2); SLTPushBack(&phead, 3); SLTPushBack(&phead, 4); SLTPrint(phead); } int main() { test02(); return 0; }
2.3 单链表头插
SList.c //定义_头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //申请节点空间 SLTNode* newnode = SLTBuyNode(x); //*pphead 相当于 phead(存储首节点地址，指向首节点) newnode->next = *pphead;//新节点存储首节点得地址 *pphead = newnode;//指向首节点指针改变指向对象 }--头插的实现很简单，因为头指针*pphead相当于phead（始终指向首节点），先将新节点存上首节点地址，将改变首节点的指向（phead），就完成了插入。
test.c void test02() { SLTNode* phead = NULL;//空链表 SLTPushFront(&phead, 1); SLTPrint(phead); SLTPushFront(&phead, 2); SLTPrint(phead); SLTPushFront(&phead, 3); SLTPrint(phead); SLTPushFront(&phead, 4); SLTPrint(phead); } int main() { test02(); return 0; }
2.4 单链表尾删
SList.c //定义_尾删 void SLTPopBack(SLTNode** pphead) { //链表为空不能删除 assert(pphead && *pphead);//pphead为空—>解引用错误；*pphead为空->首节点为空（链表为空），无法删除 //链表只有一个节点,直接删除 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* prev = NULL; SLTNode* ptail = *pphead; while (ptail->next) { prev = ptail; ptail = ptail->next; } //prev ptail prev->next = NULL; free(ptail); ptail = NULL; } } --prev 指针始终指向 ptail 前一个节点，当 ptail -> next 指向 NULL然后释放，prev指向的节点为尾节点，此时将prev->next置为NULL，完成尾删。
--特殊的是，链表只有一个节点，就要特殊处理。不需要 prev 的指向作用，直接将 ptail 释放置空。
test.c void test02() { //创建空链表 SLTNode* phead = NULL;//phead头指针，指向的首节点为空，代表链表没有节点 //尾插 SLTPushBack(&phead, 1);//为了使形参的变化影响实参，传地址 SLTPushBack(&phead, 2); SLTPushBack(&phead, 3); SLTPushBack(&phead, 4); SLTPrint(phead); //尾删 SLTPopBack(&phead); SLTPrint(phead); SLTPopBack(&phead); SLTPrint(phead); SLTPopBack(&phead); SLTPrint(phead); SLTPopBack(&phead); SLTPrint(phead); } int main() { test02(); return 0; }
回顾：
《数据结构与算法精讲：从数组到顺序表，如何让数据管理变得强大而优雅？》
《从数组到动态顺序表：数据结构与算法如何优化内存管理？》
结语：至此，单链表的基础骨架已然搭建。我们实现了增删，也领略了其“一线牵”的灵活。
然而，这趟旅程远未结束。单链表还有更多形态等待探索：如何更高效地查找？环状链表有何妙用？双链表又如何实现双向奔赴？
掌握基础，方能构筑大厦。下一站，我们将继续深入，解锁单链表的更多潜能。