对于上一篇文中说到的顺序表，我们不难发现，它本身有很多限制
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间
为了解决这些问题，我们给出了新的数据结构——链表。
二、线性表的链式结构——链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
虽然有这么多种链表，但是最常用的只有两种：
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。
2.链表的实现
（1）单链表的接口实现
1.存储结构
typedef int SLTDateType; typedef struct SListNode { SLTDateType data;//数据域 struct SListNode* next;//指针域 }SListNode;
2.初始化与销毁
由于链表的结构是由连接起来的节点组成的，所以我们并不需要对其进行初始化。
链表的每一个节点都是单独malloc出来的，因此我们要销毁这些节点，只能遍历链表，依次释放。将链表释放完毕以后，最好将指向链表头节点的指针置空，防止野指针。
void SListDestroy(SListNode** pplist) { assert(pplist); SListNode* cur = *pplist; while (cur)//遍历并销毁 { SListNode* next = cur->next; free(cur); cur = next; } *pplist = NULL; }
3.插入数据
插入数据也可以分为头插、尾插、在任意位置前插入，在任意位置后插入。但是不管是在哪里插入，都是需要动态申请一个节点的，然后根据插入位置不同链接不同，所以我们把申请节点封装成一个函数
SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc:"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
将需要的数据放入节点内部，然后执行插入操作的时候只需要将新节点链接上链表即可
- 头插
头插就是让新节点做头，新节点的next指向链表原来的头。
void SListPushFront(SListNode** pplist, SLTDateType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pplist; *pplist = newnode; }
- 尾插
在单链表的最后一个节点后面插入一个新节点，我们需要遍历找到单链表的尾结点，然后将新节点链接上去
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; } }
- 在任意位置之前插入
要在pos位置之前插入数据，我们需要找到pos位置之前的节点指针prev，然后在prev的位置之后插入新节点，原理与尾插相同。但是当传入的pos位置为头节点的时候，需要把情况单独拿出来说，传入头节点本质上就是头插，因此直接调动头插函数即可。
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDateType x) { assert(pplist); assert(pos); if (pos == *pplist) { SListPushFront(pplist, x); } else { SListNode* prev = *pplist; while (prev->next != pos)//找pos的前一个节点 { prev = prev->next; assert(prev);//暴力检查pos传错了的情况 } SListNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } }
- 在任意位置之后插入
由于已经传入一个位置pos，并且在pos后面链接，所以原理与尾插相同。
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
4.删除数据
- 头删
头删数据需要改变头节点，所以定义一个del指针存放需要删除的节点，然后改变头节，最后释放del指向的节点。
void SListPopFront(SListNode** pplist) { assert(pplist); assert(*pplist); SListNode* del = *pplist; *pplist = (*pplist)->next; free(del); del = NULL; }
- 尾删
对于一个正常的单链表，删除尾节点，首先需要找到尾，找到尾节点并记录前一个结点，将尾节点释放，然后将尾节点的前一个节点置空，但是对于只有一个元素的节点的情况，需要单独考虑，将该节点的指针指向的next置空，然后释放该节点即可。
void SListPopBack(SListNode** pplist) { assert(pplist); if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { SListNode* tail = *pplist; while (tail->next->next != NULL)//找到尾结点的前一个结点 { tail = tail->next; } free(tail->next); tail->next = NULL; } }
- 在任意位置删除
首先判断要删除的是否为头节点，如果是，直接调用头删函数，如果不是，那么就遍历链表，找到pos指针的前一个节点prev，然后将prev和pos的下一个节点链接起来，然后删除prev即可。
void SListEraseAfter(SListNode** pplist, SListNode* pos) { assert(pos); if (pos == *pplist) { SListPopFront(pplist); } else { SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } SListNode* tmp = prev->next; prev->next = prev->next->next; free(tmp); tmp = NULL; } }
