1. 顺序表的缺陷
我们学习过顺序表之后，我们发现顺序表其实有 三大缺陷：
空间不够了需要增容，增容是要付出代价的。因为 realloc 有原地扩容和异地扩容。原地扩容时代价很低。但是异地扩容不仅需要拷贝数据，还要释放旧空间。
为避免频繁扩容，空间满了基本都是扩2倍，可能就会导致一定的空间浪费。因为倍数为2时，扩容的幅度会越来越大。
顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高。
那么我们是否能改善这些缺陷？比如：
- 按需申请释放。
- 不要挪动数据。
我们今天学习的链表就能改进上面两个缺陷，那么接下来我们就去学习它~
2. 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针链接次序实现的。
链表相较于顺序表的优点：顺序表要求 逻辑结构和物理结构上连续(通过下标访问) ；而链表只要求在逻辑结构上连续，物理结构上可以不连续(通过指针串联，它们之间并不连续)。
而逻辑结构就是指数据在逻辑上是如何存储的，就是一种形象但并不存在的易理解的结构。就比如链表的每个节点串联在一起，就像火车一样，比如这样：
其实这就非常形象了，车厢之间是无序的，因为每次不能保证链接到同样的车厢，车厢之间的位置可以改变。
而 链表 既然是数据结构，那么一定就要存储数据，并且需要有能力找到链表的下一个位置。那么它的结构到底长什么样？
我们可以先看一下某个链表的结构示意图：
我们把每两个小方块组成的大方块称为一个 节点 。我们的 n1、n2、n3、n4 则是每个节点的地址。它们指向 节点 。节点 之间使用箭头串联。
但是链表的 节点 之间真的有箭头吗？其实并没有。
它是我们的 逻辑结构 示意图，为了让我们更加容易理解，实际上通过箭头我们也可以知道，这可能和指针有关系。链表的 节点 分为两部分。一部分为 数据 ，一部分为 指针 ，而这个指针就是我们 下一个节点的地址 。所以从实际上来说，链表节点的第二部分是地址，它们之间没有箭头，包括 n1、n2、n3、n4 四个指针变量。
我们也可以画出它们的 物理结构 示意图：
(注：这里存储的地址数据我们不需要在意，我们只要观察它们之间的关系即可。)
逻辑结构中每个节点相互链接，像用箭头串联，和链条一样；物理结构每个节点的 指针域 存放下一个节点的地址，最后一个节点的 指针域 存放空指针代表链表结束，通过指针之间建立起链接关系。
从理解层面来说，逻辑结构更加容易让我们进行学习~
链表就是通过指针的链接次序来依次找到每一个节点，已对数据进行管理的。这就是链表结构为什么物理结构上非连续，但是能找到数据的原因。
3. 链表的分类
但是链表可不止一种，上面只是举个例子，实际上链表的结构非常多样，以下为链表的各种结构：
单向或双向
带头或不带头
循环或非循环
但是我们常用的链表主要是单链表和带头双向循环链表，一个结构最简单，一个结构最复杂。
下面简单介绍一下两个链表的特性：
无头单向非循环链表：也就是我们俗称的单链表。其结构简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶、栈的链式结构等。因为单链表本身有缺陷，所以为常见的考核点之一。
带头双向循环链表：结构最复杂，一般用来单独存储数据。实际使用的链表，大多都是带头双向循环链表。虽然这种链表结构最复杂，但是其实有很多优势，并且在一定程度上对单链表的缺陷做出了一定的纠正。
而我们本篇博客就是对结构最简单的 单链表 进行讲解并实现。
4. 单链表的实现
4.1 结构设计
单链表和顺序表的结构略有不同，单链表的主结构其实为一个节点。
一个节点由两部分组成：data和next。data为我们存储数据的地方。而next则为下一个节点的地址。
为了之后我们写数据结构更加方便，于是将结构typedef一下：
typedef struct SListNode { int data; struct SListNode* next; }SLTNode;
上面我们设计的是不带哨兵位的单链表。这种结构设计相对于带哨兵位的链表的缺点就是设计接口函数时需要考虑链表是否为空的情况。
可能有小伙伴不了解什么是哨兵位，下面就介绍一下。
哨兵位也叫哨兵节点，哑节点。该节点并不存储任何数据，只是为了方便操作而引入这个节点。起一个站岗放哨的作用。所以形象的叫它哨兵位。如果一个链表有哨兵位，那么链表的第一个元素应该是链表第二个节点对应的元素。
那么这时就说明链表永不为空，这就可以避免边界问题的处理，简化代码与减少代码出错的可能性。
由于笔试面试考察中，不带头的单链表考察的最多，且实现不带头单向非循环链表需要把控的细节更多，以此增加我们的代码能力。
4.2 接口总览
实现一个单向无头非循环链表，总共需要以下接口：
// 创建新节点 SLTNode* BuyListNode(SLTDateType x); // 打印 void SListPrint(SLTNode* phead); // 尾插 void SListPushBack(SLTNode** pphead, SLTDateType x); // 头插 void SListPushFront(SLTNode** pphead, SLTDateType x); // 尾删 void SListPopBack(SLTNode** pphead); // 头删 void SListPopFront(SLTNode** pphead); // 查找 SLTNode* SListFind(SLTNode* phead, SLTDateType x); // 在pos位置之前插入一个节点 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 在pos位置之后插入一个节点 void SListInsertAfter(SLTNode* pos, SLTDateType x); // 在指定位置删除一个节点 void SListErase(SLTNode** pphead, SLTNode* pos); // 删除指定pos位置后的一个节点 void SListEraseAfter(SLTNode** pphead, SLTNode* pos); // 销毁 void SListDestory(SLTNode** pphead);
我们发现绝大多数接口的参数都为二级指针，这是为什么？
我们先了解一下，我们平时单链表的测试用例：
void TestList() { SLTNode* plist = NULL; }
链表的一开始是空的。所以我们插入数据时，需要让plist指向我们新节点。就相当于改变plist的指向。plist是一级指针，那么要改变plist就要传它的地址&plist，为二级指针，所以也需要用二级指针来接收该参数。
(注：虽然链表不为空后，只需要改变结构即可，这时一级指针是没问题的。但是在C语言中，对于同一个接口来说，参数还能不一样吗？难道再封装一个函数？那时不可能的，所以我们索性都用二级指针。)
就好比当我们要改变一个int类型的变量时a，我们需要传它的地址&a，那么函数的形参就应该用int* 接收；对于指针也是这样，一个int* 的指针变量p，它也是变量，我们需要改变这个值，就应该传它的地址&p，那么函数参数就应该那int* * 接收。
而对于一些接口就不需要传二级指针，就拿 打印 来说吧，因为我并不需要改变plist，我只需要通过结构体指针访问结构内的next成员，并迭代到下一个节点，然后打印出数据就可以，所以不需要传二级指针。
补充：
当然，对于带哨兵位的单链表，直接传plist是没问题的。因为此时链表带头，我们只需要改变哨兵位和节点之间的链接关系就可以，说白了就是改变结构、
而且对于我们上面的单链表也可以传一级指针plist，然后用返回值接收，比如尾插就是：SLTNode* plist = SListPushBack(plist, 1); 但是这样使用，当调用次数很多是不是很怪？一大排的返回值接收，会不会显得代码冗余不简洁？
所以对于我们上面的结构，还是传二级指针比较好~
可能大家现在对这些操作还不是很理解，没关系，我们慢慢来，我们只要搞清楚，这里为什么这么传参就ok~
4.3 创建新节点
我们插入数据，都需要创建节点。因为链表是按需分配的，创建即用。如果使用局部变量的话，那么在函数调用结束后节点就销毁了，那么肯定就需要使用动态内存开辟新的节点：
// 创建新节点 SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); // 内存申请失败，说明几乎没有空间了，直接退出程序 } newnode->data = x; newnode->next = NULL; return newnode; }
创建一个节点，节点的next默认为NULL，这样对于尾插时，也就不需要将新节点置空了~
此接口大多被实现插入的接口函数所复用，而我们只需要创建节点将节点地址返回即可。
4.4 尾插
从尾部插入数据，需要分两种情况考虑：链表为空、链表有节点。
如果链表为空，那么就需要创建节点，并且将创建的节点赋给原链表；如果链表不为空，则需要找到链表的尾部，然后将新节点到尾部的后面链接就可以了，这时也不需要刻意的将新节点的 next 置空，因为我们创建的节点的 next 本身就为空。
至于如何创建新节点，就调用之前的BuyListNode就可以了。
// 尾删 void SListPushBack(SLTNode** pphead, SLTDateType x) { // 建立新节点 SLTNode* newnode = BuyListNode(x); // 链表没有节点，给新节点 if (*pphead == NULL) { *pphead = newnode; } else { // 找到尾结点 SLTNode* tail = *pphead; while (tail->next != NULL) // tail->next为空，说明此时为尾结点 { tail = tail->next; } // 尾结点链接新节点 tail->next = newnode; } }
4.5 头插
对于头插来说，就不需要像尾插一样考虑链表是否为空。
我们直接创建新节点，并且将新节点的 next链接为原来的头，然后将头变为新节点，就可以了。因为就头插来说，如果链表为空，那么头部也为空，所以为什么可以直接链接就是这个原因。
// 头删 void SListPushFront(SLTNode** pphead, SLTDateType x) { SLTNode* newnode = BuyListNode(x); newnode->next = *pphead; // 新节点链接之前plist的地址 *pphead = newnode; // 头指针更改为newnode }
看接口的实现，我们也能看出就单链表来说，对于头部的操作还是十分便捷的，包括下面的头删~
4.6 尾删
对于单链表来说，尾删也是比较麻烦的一部分。
尾删需要判断链表是否为空，并且需要将链表中 节点数 为单个节点和多个节点的情况分开讨论。
如果是单个节点删除，那么只需要释放节点，将节点置空。
如果是两个及以上节点删除，尾删需要将删除元素的前一个链接为空指针，需要删除尾结点，而完成这两个步骤的方法就是遍历单链表，通过条件来求出这两个位置。找到这两个位置后，释放尾结点，将尾结点的前一个位置的next置空。
// 尾删 void SListPopBack(SLTNode** pphead) { // 暴力处理 一个节点 assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else// 两个及以上节点 { SLTNode* prev = NULL; // 记录上一个节点的地址 SLTNode* tail = *pphead; // 尾结点 while (tail->next)// 当值为空指针，被隐式转换为0，结束循环 { prev = tail; tail = tail->next; } free(tail);// 释放尾结点空间 tail = NULL; // 其实这里置空也没有意义，tail是局部变量，函数结束就自动销毁了，反正也找不到~也不会使用到 // 将前一个节点的next置空 prev->next = NULL; } }
4.7 头删
头删，相对于尾删就简单不少了。
对于空链表，直接断言判断就可以。
对于1个及以上节点，那么就是释放头结点，并且头结点的next设定为头。
一定要注意处理的方式，千万不要将头结点释放了，还在使用头结点的next。我们可以先拷贝newpphead为头结点的next，然后释放pphead，再将给上新的头。
// 头删 void SListPopFront(SLTNode** pphead) { // 处理空链表 assert(*pphead); // 处理1个及以上节点 SLTNode* newpphead = (*pphead)->next; free(*pphead); *pphead = newpphead; }
4.8 查找
对于查找来说，相对比较简单。查找链表中某个元素是否存在，只需要遍历链表，查看里面是否有这个值。如果找到了，返回这个节点的地址；没找到，返回空指针。
当然对于空链表也可以查找，只不过就是找不到而返回空指针罢了，千万不要直接断言哦。
// 查找 SLTNode* SListFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } else { cur = cur->next; } } return NULL; // 没找到 }
通过这个 查找函数 我们也可以推测出，为什么定义链表时只需要定义一个指针，而对于顺序表却要定义一个结构的原因：
因为对于链表来说，我只需要一个指针就可以遍历链表，因为我的节点之间互相串联链接。
但是对于顺序表得定义结构，否则我们不知道它有多少个元素，容量有多大。
4.9 在pos位置之前插入节点
要在pos位置之前插入节点，那么肯定就要找到 pos 之前的位置，于是，遍历链表肯定少不了。
其他的就是链表链接的基本操作，但是这里和之前的头插、尾插不同，因为需要考虑前后节点的链接。
所以我们需要将pos之前的位置也就是 posPrev 的 next 链接为新节点，将新节点的 next 链接为 pos 位置。
你以为这就完了？这里需要另外考虑一个问题：
如果我插入的位置是头部，那么该如何插入？
那么肯定是用头插的方式解决啦，这个问题相对简单，但是这个情况容易被忽略。
// 在pos位置之前插入节点 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuyListNode(x); // 头插情况特殊处理 if (*pphead == pos) { newnode->next = *pphead; // newnode链接头 *pphead = newnode; // 头变为newnode } // 其他位置插入 else { // 找到pos前一个位置 SLTNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = newnode; // 将pos前一个位置链接到newnode newnode->next = pos; // newnode连接到pos } }
