👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注

---

前景回顾

上期讲解了顺序表，虽然它的尾插和尾删的时间复杂度都是O(1)，但还是存在一些缺陷的，比如中间和头部插入数据效率低下，还会存在一定的空间浪费等。现在我们来看看链表是否能解决顺序表的缺陷。

一、概念

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

二、链表的结构

• 物理结构

1. 物理结构就是数据在内存中实实在在的变化。
2. 我们通常把一小块的内存空间称为结点，而显示中的结点一般都是从堆上申请的。
3. 链表之所以能链接起来，主要是因为上一个结点存储着下一个结点的地址。
4. 然而在平时做题的时候，不可能把图画的这么详细，因此引入了逻辑结构。

• 逻辑结构

逻辑结构是为了方便理解，形象画出来的。(一般分析都画逻辑结构)

三、链表的分类

实际中的链表的结构非常多样，以下情况组合起来就有8种结构：

1. 单向或者双向

2. 带头（哨兵位）或者不带头

带哨兵位的头结点是不存储有意义数据的

3. 循环或者非循环

总结
虽然有这么多的链表结构，但是最常用是以下这两种

• 不带头单向非循环链表
  
• 带头双向循环链表
  

四、链表的实现

4.1 准备工作

为了方便管理，我们可以创建多个文件来实现

1. test.c - 测试代码逻辑 （源文件）
2. SList.c - 动态的实现 （源文件）
3. SList.h - 存放函数的声明 （头文件）
   

4.2 接口

【SList.h】

typedef int SLTDateType;//定义结构体
typedef struct SListNode
{SLTDateType data; struct SListNode* next;//存储下一个结点的地址
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
//单链表在pos之前插入x
void SListInsert(SListNode** plist,SListNode* pos,SLTDateType x);
//单链表删除指定pos结点
void SListErase(SListNode** plist,SListNode* pos);
//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
//结点释放
void SListDestroy(SListNode** plist);

4.3 单链表之动态申请一个节点

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("newnode :: malloc");return NULL;}newnode->next = NULL;newnode->data = x;return newnode;
}

其实这个接口可以不用写，写出来是因为后面的尾插、头插等需要向内存申请空间，然而为了减少代码量，因此就多了这个接口。

4.4 单链表之打印

// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur) //cur != NULL{printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

【笔记总结】

1. 为什么不断言plist结点
   因为空链表是可以打印的。
2. 为什么不直接拿plist遍历
   首先拿plist遍历肯定是没有问题的，但是为了保存头结点，最好还是新建一个结点遍历。
3. cur = cur->next 千万不能写成 cur++
   原因是链表在内存空间上是不连续的。

4.5 单链表之尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);//向内存申请空间SListNode* newnode = BuySListNode(x);//当空链表为空 -- 赋值if (*pplist == NULL){*pplist = newnode;}//不为空 -- 找到尾节点，再链接else{SListNode* tail = *pplist;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

【笔记总结】

1. 为什么要二级指针？
   首先，pplist一开始是指向头结点的，当pplist指向NULL时，尾插时就要改变头结点，如果不是二级指针，即使修改了头结点，尾插后，pplist还是指向NULL（不变）
2. 为什么断言pplist，而不断言*pplist
   不断言*pplist是因为空链表可以尾插
   断言pplist是因为pplist其实存储的是*pplist的地址，即使*pplist == NULL，但pplist绝对不可能为NULL。

4.6 单链表之头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);//向内存申请空间SListNode* newnode = BuySListNode(x);//头插newnode->next = *pplist;*pplist = newnode;}

【常见错误】
头插过程特别容易出错，少部分人可能会写成
*pplist = newnode
newnode->next = *pplist
如果这么写就大错特错了，原因是如果这么写，就找不到原来的头结点了

4.7 单链表之尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist); //空链表不能尾删//如果链表中只有一个结点，直接释放if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{//尾插过程SListNode* prev = NULL;SListNode* tail = *pplist;//找尾结点while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}

【笔记总结】

1. 要断言*pplist，因为空链表是不能尾删。
2. 为什么还要定义prev
   首先，即使找到了尾结点，并把尾结点释放掉，但在尾结点释放之前，并没有把尾结点的前一个结点的next掷为NULL。所以定义prev是为了找到原尾结点的前一个结点。
   

4.8 单链表之头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);//空链表不能头删SListNode* first = *pplist;*pplist = first->next;free(first);
}

【动图展示】

4.9 单链表之查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}}//遍历完还是没找到return NULL;
}

4.10 单链表之在pos之前插入x

//单链表在pos之前插入x
void SListInsert(SListNode** plist, SListNode* pos, SLTDateType x)
{assert(plist);assert(pos);//开个新节点SListNode* newnode = BuySListNode(x);//如果pos指向头结点，相当于头插if (pos == *plist){SListPushFront(plist, x);}else{//找到pos前一个位置SListNode* prev = *plist;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

【动图展示】

4.11 单链表之删除指定pos结点

//单链表删除指定pos结点
void SListErase(SListNode** plist, SListNode* pos)
{assert(plist);assert(pos);//pos指向头结点，相当于头删if (*plist == pos){SListPopFront(plist);}else{//找到pos前一个结点SListNode* prev = *plist;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

【动图展示】

4.12 单链表之在pos位置之后插入x

//单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

注意链接顺序，不要和头插犯同样的错误

【动图展示】

4.13 单链表之删除pos位置之后的结点

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos->next);//之后的结点不能为NULL//记录pos后一个结点SListNode* del = pos->next;//链接pos->next = del->next;//删除释放free(del);
}

【动图展示】

4.14 单链表之结点释放

//结点释放
void SListDestroy(SListNode** plist)
{SListNode* cur = *plist;while (cur){//在释放前记录下一个结点SListNode* next = cur->next;free(cur);cur = next;}*plist = NULL;
}

【动图展示】

五、总结

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低