👉链表的引入👈
在上一篇博客中，我们已经讲到了顺序表。那现在再来总结一下顺序表的相关问题。
顺序表的问题及思考
问题：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。
👉链表👈
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。
物理结构：内存中实际的存储结构。
逻辑结构：想象出来的存储结构。
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构:
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
👉单向链表的实现👈
链表和顺序表一样，都要实现增删查改的功能。链表需要实现的函数接口有：申请节点、打印链表、销毁链表、头插数据、尾插数据、尾删数据、头删数据、查找数据、在pos位置之前插入数据、在pos位置之后插入数据、删除pos位置的数据和删除pos位置之后的数据。由于要实现的函数接口比较多，所以我们还是需要采取三个模块的方式来写代码。SList.h源文件里面是头文件的包含、结构体的声明、类型的重命名以及函数接口的声明。SList.c源文件里面是函数接口的实现。Test.c源文件用来测试我们实现的函数接口是否正确。
现在来看一下每个模块的代码。
SList.h
#pragma once #include<stdio.h> #include<assert.h> #include <stdlib.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; // 申请节点 SLTNode* BuySLTNode(SLTDataType x); // 打印链表 void SListPrint(SLTNode* phead); // 销毁链表 void SListDestory(SLTNode** pphead); // 头插数据 void SListPushFront(SLTNode** pphead, SLTDataType x); // 尾插数据 void SListPushBack(SLTNode** pphead, SLTDataType x); // 尾删数据 void SListPopBack(SLTNode** pphead); // 头删数据 void SListPopFront(SLTNode** pphead); // 查找数据 SLTNode* SListFind(SLTNode* phead, SLTDataType x); // 在pos位置之前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在pos位置之后插入 void SListInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos位置的数据 void SListErase(SLTNode** pphead, SLTNode* pos); // 删除pos位置后面的数据 void SListEraseAfter(SLTNode* pos);
链表与顺序表的函数接口大多数是相同的，与顺序表不同的是，链表没有初始化的函数接口。那为什么链表不需要初始化呢？是因为我们只需要拿一个SLTNode*指针就能管理整个链表。
还有一点就是，除了打印链表和查找数据的函数接口的参数是一级指针，其它的函数接口的参数都是二级指针。这又是为什么呢？其实是因为打印链表和查找数据的函数不需要改变头节点，而其它函数有可能要改变头节点。这个知识点在接下来的内容将会跟大家讲解。
SList.c
#include "SList.h" // 申请节点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } // 打印链表 void SListPrint(SLTNode* phead) { //assert(phead); SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } // 销毁链表 void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; } // 头插数据 void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; } // 尾插数据 void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuySLTNode(x); // 链表为空 if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点 SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode; } } // 尾删数据 void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead);// 判断是否为空链表 // 只有一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; SLTNode* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; //SLTNode* tail = *pphead; //while (tail->next->next) //{ // tail = tail->next; //} //free(tail->next); //tail->next = NULL; } } // 头删数据 void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); // 判断是否为空链表 SLTNode* newHead = (*pphead)->next; // 新的头节点 free(*pphead); // 释放旧的头节点 *pphead = newHead; } // 查找数据 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; // 循环遍历链表 while (cur) { if (cur->data == x) { return cur; // 找到了 } cur = cur->next; // 继续往后找 } return NULL; // 没找到 } // 在pos位置之前插入 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); // 头插 if (*pphead == pos) { SListPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev); // 暴力检查，如果prev为空，那么就说明pos不在链表中，参数pos传错了 } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } } // 在pos位置之后插入 void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; } // 删除pos位置的数据 void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); // 头删数据 if (*pphead == pos) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev); // 暴力检查，如果prev为空，那么就说明pos不在链表中，参数pos传错了 } prev->next = pos->next; free(pos); } } // 删除pos位置后面的数据 void SListEraseAfter(SLTNode* pos) { assert(pos); // pos位置执行NULL if (pos->next == NULL) { return; } else { SLTNode* next = pos->next; pos->next = next->next; free(next); } }
以上就是SList.c源文件实现的函数接口，大家可以先看一下，在下面再来详细讲解每一个函数接口的实现。
申请节点
用来存储数据的节点是在插入数据时，一个一个地向堆区申请空间的。如果申请节点失败，那就直接结束程序，没有必要继续往下执行代码了。如果申请节点成功，那么newnode->data = x, newnode->next = NULL，最后将newnode的值返回。
// 申请节点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
打印链表
打印链表就是利用while循环将整个链表的数据打印出来。因为每个节点都存储着数据和下一个节点的地址，所以我们可以通过该地址找到下一个节点，依次类推就能遍历整个链表了。所以需要定义一个指针SLTNode* cur = head，当cur = NULL时，遍历链表结束。
// 打印链表 void SListPrint(SLTNode* phead) { //assert(phead); //不需要断言phead SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
销毁链表
可以发现销毁链表函数的参数是二级指针SLTNode** pphead，即头指针SLTNode* plist的地址，该地址是不可能为空指针NULL的，所以要对pphead进行断言。销毁链表后，plist的值要置为NULL。如果函数的参数是一级指针SLNode* phead的话，将无法将plist的值置为NULL。因为形参只是实参的一份临时拷贝，对形参的修改不会影响实参。
如果还是不能理解的话，请看下面的例子：
#include <stdio.h> //交换x、y的值 void Swap1(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } //交换px、py的值 void Swap2(int** ppx, int** ppy) { int* tmp = *ppx; *ppx = *ppy; *ppy = tmp; } int main() { int x = 10; int y = 20; int* px = &x; int* py = &y; printf("x:%d y:%d\n", x, y); Swap1(&x, &y); printf("x:%d y:%d\n", x, y); printf("px:%p py:%p\n", px, py); Swap2(&px, &py); printf("px:%p py:%p\n", px, py); return 0; }
从上面的例子可以看出，如果想要改变int类型变量的值，函数的参数就要设置为int*；如果要改变int*类型变量的值，函数的参数就要设置为int**。因为插入和删除数据都有可能影响头节点，所以要传二级指针SLTNode** pphead。只有传二级指针SLTNode** pphead，才能够改变头指针SLTNode* plist的值。
// 销毁链表 void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
