1.链表
1.1 链表概念及其结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
- 链表结构如图所示：
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2.单链表代码实现
2.1 单链表的定义
我们在了解线性结构最重要的就是明白这个结构是如何定义的，是怎样的一种结构。这里单链表的定义，我们考虑的是我们需要这个结构中包含什么，这里我们需要的是一个数据域和一个指针域，数据域用于存储数据，指针域用于链接每个单链表节点。行，我们来rua一下：
typedef int SLTDateType;//typedef 一下，方便我们更改所需存储的类型 typedef struct SListNode { SLTDateType data;//数据域，用于存储数据 struct SListNode* next;//指针域，用于链接下一个结点 }SLTNode;
2.2 单链表的初始化
单链表一般不直接提供初始化接口，是因为单链表的初始化不需要额外的方法来完成，可以通过其他操作来实现。
一般而言，单链表的初始化可以分为两种方式：
1.首先创建一个空链表，然后逐个插入节点，直到构建完整的链表。
SLTNode* plist = NULL;//后续只需要不断插入新的结点就可以
2.直接在创建链表的过程中完成节点的插入操作，不需要单独的初始化方法。
因此，为了简化接口设计和操作复杂度，单链表通常不提供单独的初始化接口，而是通过其他操作来实现链表的构建和初始化。
2.3 单链表的新增结点
这里就可以看到我们在为一个指针开辟空间后就立马初始化了，和上述第二种初始化的方法相同。
SLTNode* SLTNewNode(SLTDateType x) { SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); //开辟一个链表结点大小的空间 if (node == NULL)//检测是否开辟成功 { perror("malloc fail"); return NULL; } node->data = x; node->next = NULL; return node; }
2.4 单链表的打印
为了方便测试一般我们会使用链表打印接口来查看检测。
void SLTPrint(SLTNode* pa) { SLTNode* cur = pa; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
2.4 单链表的插入
这里涉及到单链表的一个难点，就是这里需要二级指针，我们需要更改一级指针内的元素数据，所以需要用二级指针来更改。就例如我们要改变一个数据类型的值，需要一级指针一样。
2.4.1 头插
在链表第一个结点前插入。
void SLTPushFront(SLTNode** ppa, SLTDateType x) { assert(ppa);//&plist(ppa)不可能为空，所以需要检测 SLTNode* newnode = SLTNewNode(x); newnode->next = *ppa;//新节点的next指针指向链表开头（*ppa） *ppa = newnode;//更新头指针 }
2.4.2 尾插
在链表最后结点后插入
void SLTPushBack(SLTNode** ppa, SLTDateType x) { assert(ppa); SLTNode* newnode = SLTNewNode(x); if (*ppa == NULL) //判断链表是否为空 { *ppa = newnode; } else { //找尾操作，这里单链表我们只能使用遍历来实现，当找到一个节点的next指针指向null时，就代表找到尾了。 SLTNode* tail = *ppa; while (tail->next) { tail = tail->next; } tail->next = newnode; } }
2.4.3 任意位置插入
pos前位置插入，我们知道了尾插，这里就相当于把pos位置当做尾，去找pos位置，然后再用头插的思路完成。
//任意位置插入(pos前插入) void SLTInsertF(SLTNode** ppa, SLTNode* pos, SLTDateType x) { assert(ppa); assert(pos); if (pos == *ppa) { SLTPushFront(ppa, x); } else { SLTNode* tmp = SLTNewNode(x); SLTNode* prev = *ppa; while (prev->next != pos) { prev = prev->next; } prev->next = tmp; tmp->next = pos; } }
pos位置后插入：学习了任意位置插入，我们其实可以把头插和尾插的实现过程改成调用任意位置插入接口
void SLTInsertB(SLTNode** ppa, SLTNode* pos, SLTDateType x) { assert(ppa); if (pos == NULL) { SLTPushBack(ppa, x); } else { SLTNode* newnode = SLTNewNode(x); SLTNode* cur = *ppa; while (cur != pos->next) { cur = cur->next; } pos->next = newnode; newnode->next = cur; } }
2.5 单链表的删除
2.5.1 头删
头删的思路就是把头指针指向下一个结点，然后释放开始的结点。
void SLTPopFront(SLTNode** ppa) { assert(ppa); assert(*ppa); SLTNode* tmp = *ppa; *ppa = tmp->next; free(tmp); tmp = NULL; }
2.5.2 尾删
尾删道理是相通的，找到尾指针，但也要保留尾指针的前一个指针，因为需要在删除尾指针后，把前一个尾指针的next指向空。
void SLTPopBack(SLTNode** ppa) { assert(ppa); assert(*ppa); if ((*ppa)->next == NULL) { free(*ppa); *ppa = NULL; } else { SLTNode* prev = *ppa; SLTNode* tail = prev->next; while (tail->next) { prev = prev->next; tail = tail->next; } prev->next = tail->next; free(tail); tail = NULL; } }
2.5.3 任意位置删除
意思相近与尾删。
2.5.3 任意位置删除 意思相近与尾删。 void SLTEraser(SLTNode** ppa, SLTNode* pos)
2.6 单链表的查找及其修改
链表查找就是对应data，然后遍历返回比较简单，修改的话就是根据返回访问data进行赋值修改
SLTNode* SLTFind(SLTNode* pa, SLTDateType x) { SLTNode* cur = pa; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
