前言
上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是O(N)效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那就很有可能会出现扩大了用不完导致空间浪费的现象。这些问题该如何解决呢？那就需要用到今天分享给大家的另一种线性结构链表。
1 链表
1.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
注意：
- 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
- 现实中的结点一般都是从堆上申请出来的
- 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.2.1 单向或者双向
1.2.2 带头或者不带头
1.2.3 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.2.4 无头单向非循环链表
1.2.5 带头双向循环链表
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2 链表的实现
2.1 结构
typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//数据域 struct SListNode* next;//指针域 }SLTNode;
2.2 结点的创建
我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。
SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; return newnode; }
2.3 尾插
我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。
void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
2.4 头插
要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表phead的值，然后将newnode的地址存放在phead中，形成新的链表。无论一开始有没有节点，头插都是相同的。
void SLTPushFront(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; }
2.5 尾删
在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。
void SLTPopBack(SLNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
2.6 头删
头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pphead就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。
void SLTPopFront(SLNode** pphead) { assert(pphead); assert(*pphead); SLNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); }
2.7 查找
循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。
SLNode* SLTFind(SLNode* phead, SLNDataType x) { SLNode* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL; }
2.8 在pos位置之前插入数据
在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) { assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { SLTPushFront(pphead, x); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLNode* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } }
2.9 删除pos位置
有可能删除的是头节点，所以要传递二级指针。
void SLTErase(SLNode** pphead, SLNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { SLTPopFront(pphead); } else { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
2.10 在pos位置之后插入数据
这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。
void SLTInsertAfter(SLNode* pos, SLNDataType x) { assert(pos); SLNode* newnode = CreateNode(x); newnode->next = pos->next; pos->next = newnode; }
2.11 删除pos位置之后的数据
void SLTEraseAfter(SLNode* pos) { assert(pos); assert(pos->next); SLNode* tmp = pos->next; pos->next = pos->next->next; free(tmp); tmp = NULL; }
2.12 打印数据
void SLTPrint(SLNode* phead) { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); }
2.13 销毁数据
void SLTDestroy(SLNode** pphead) { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
