链表的引入
对于顺序表存在一些缺陷：
- 中间/头部的插入删除，时间复杂度为O(N) 。头部插入需要挪动后面的元素
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间
对于链表而言，能够避免上述问题的出现。头部插入数据不需要挪动大量的数据，按需申请释放空间，不会造成空间的浪费。
链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
现实中 数据结构中（箭头实际上并不存在，这里只是形象化）:
链表的种类有很多
以下情况组合起来就有8种链表结构：
单向或者双向 ：
带头或者不带头：
循环或者非循环：
面对这么多种类的链表，我们该如何选择？虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
话不多说，直接进入我们单链表的实现：
单链表的接口我们需要实现：
- 打印销毁
- 头插尾插创建新结点(由于后面会频繁使用，故将其封装成函数)
- 尾删头删查找
- 在pos之前插入、在pos之后插入
- 删除pos、删除pos之后的位置
我们还是老样子，通过三个部分组成：
**SList.h:**包括头文件的引用，结构体的声明定义，接口函数的声明。
**SList.c:**对SList.h中接口函数进行实现。
**test.c:**主函数进行测试：通过void TestSList()函数对SList.c的函数进行调用，测试有没有错误。
注意：对于一些问题的所在，我已经通过注释进行相关说明。注释才是精髓。
SList.h
#define _CRT_SECURE_NO_WARNINGS #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SLTNode* next; }SLTNode; //打印 void SListPrint(SLTNode* phead); //创建新结点 SLTNode* BuySLTNode(SLTDataType x); //销毁 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* pphead,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);
SList.c
#define _CRT_SECURE_NO_WARNINGS #include "SList.h" //打印 void SListPrint(SLTNode* phead) { //phead不需要断言。因为phead有可能有空，没有数据 //而顺序表的结构体不可能为空，所以要进行断言 SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } //创建新结点 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("mail fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; } //销毁 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); //空,改变的是SListNode*,需要二级指针 //非空。尾插要改变的是结构体SListNode，只需要结构体的指针 if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } //尾删——有无结点。需要找前一个 void SListPopBack(SLTNode** pphead) { assert(pphead); SLTNode* tail = *pphead; SLTNode* prev = NULL; assert(*pphead != NULL); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { while (tail->next != NULL) { prev = tail; tail = tail->next; } prev->next = NULL; free(tail); tail = NULL; /*while (tail->next->next!=NULL) { tail = tail->next; } free(tail->next); tail->next = NULL;*/ } } //头删 void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); /*if (*pphead == NULL) { return; }*/ SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; } //查找 SLTNode* SListFind(SLTNode* pphead, SLTDataType x) { assert(pphead); SLTNode* cur = pphead; 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 (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySLTNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; assert(prev); } 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 (pos == *pphead) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; //检查pos不是链表中的结点 assert(prev); } prev->next = pos->next; free(pos); } } //删除pos后面位置 void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SLTNode* next = pos->next; pos->next = next->next; free(next); } }
test.c
#define _CRT_SECURE_NO_WARNINGS #include "SList.h" //头插、头删 void TestSList1() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListDestory(&plist); } //尾插、尾删 void TestSList2() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListDestory(&plist); } //查找、在pos之前插入 void TestSList3() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 3); if (pos) { //修改 pos->data *= 10; printf("找到了\n"); } else { printf("找不到\n"); } pos = SListFind(plist, 1); if (pos) { SListInsert(&plist, pos, 10); } SListPrint(plist); SListDestory(&plist); } //删除pos位置、删除pos后面的位置 void TestSList4() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 3); if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 1); if (pos) { SListErase(&plist, pos); } SListPrint(plist); } int main() { //TestSList1(); //TestSList2(); //TestSList3(); TestSList4(); return 0; }
以上就是单链表的相关操作，我们不难发现，单链表的优势在于头插头删
而对于一些操作：如尾插尾删而言，我们都需要去找前一个位置，这是比较麻烦的。单链表我们就先介绍到这里了。
这里同时也有一个问题存在：
删除当前位置我们需要去找前一个位置，这效率是比较低的，我们如何改进这个问题❓
找pos位置删除，而就是不找前一个位置（即要求是O（1））：替换法删除，把pos的值和下一个节点的值进行交换，再把pos进行释放掉。但是有一个缺陷：pos不能是尾节点。尾节点没有下一项。
那如果在pos位置之前插入，要求为O（1）呢：
