在上一期中，我们说完了顺序表，并且提出顺序表中的问题
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？
今天的链表就会解决这些顺序表中出现的问题。那什么是链表呢？
链表
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
链表如同小火车，一节与一节相关联
注意：
1.链式结构在逻辑上是连续的，但在物理上不一定连续。
2.节点都是从堆上申请的。
3.从堆上申请空间，是按一定策略分配的，申请的空间可能连续，可能不连续。
假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：
链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。
下面就是对无哨兵位单链表实现
无头(无哨兵位)单链表实现
单链表结构
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
使用typedef将int 与结构体重命名更好的使用清晰，定义next指针需要指向下一个结构的地址方便链接。
单链表是只有一个指针指向后面节点，当头部指针向后移动时就找不到前面的节点了，所以在创建单链表时，我们要创建一个结构体指针变量固定在头位置，确保这个单链表完整性
我们在主函数中创建：SLTNode* plist = NULL;
plist要等于链表中的第一个结构体的地址，防止找不到链表的头部。
创建节点
SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
将需要存放的数据传入创建节点函数，使用malloc在堆中创建需要的空间。在这里我们必须对创建的空间进行检测是否创建成功，否则直接将退出程序。
创建出的空间也是结构体，我们需要给data赋需要存储的数据，将next赋值为空，否则将成为野指针。将创建好的空间进行返回即可。
打印链表内容
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
创建一个可以遍历的指针，进行逐一遍历打印即可。
头插
头插在进行过程中，一定会改变plist指向的节点，无论链表是否为空过程都是相同的，所以我们在头插时一定会改变指针plist指向的内容，所以这是我们就得传入plist的地址进行调用修改，这时我们就得使用二级指针进行操作。
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
先将*pphead指向的空间赋给新创建的空间中的next，再使用二级指针将头指针的内容修改为新空间的地址即可。
尾插
在创建尾插函数时，我们就要考虑链表是否为空，当我们在链表为空时进行尾插，就必须改变头指针，所以尾插这个函数应该分情况进行：
void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { //改变的结构体的指针，所以要用二级指针 *pphead = newnode; } SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } //改变的为结构体，所以用一级指针 tail->next = newnode; }
再往后插入就不需要对头指针做动作了。
所以这里我们一定要把问题想周全，要不然程序就会报错甚至直接崩溃。
头删
void SLTPopFront(SLTNode** pphead); { assert(*pphead); SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
头删时我们应该先创建一个临时指针指向需要释放的空间，如果直接释放空间，我们就使链表直接“断裂”，找不到下一个节点地址。
当我们进行头删时，需要判断链表是否为空链表再进行释放。在头删时，头指针的地址就应该指向下一个节点地址，我们应该提前进行标记，在释放完成后将下一个节点地址再次付给头指针即可。
尾删
尾删和尾插都要考虑很多，尾删要考虑两种情况：1.只有一个节点2.有很多节点。当只剩最后一个节点时，我们删除时就要改变头指针，将头指针置空。我们一般使用两个指针，一个指向尾节点，一个指向尾节点前一个节点。当尾节点释放后，我们使用另一个指针将其next置空即可。
void SLTPopBack(SLTNode** pphead) { assert(*pphead == NULL); if ((*pphead)->next = NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next) { tailPrev = tail; tail = tail->next; } free(tail); tailPrev->next = NULL; } }
假设只剩最后一个节点：
在空链表时，我们一定要进行判断assert(*pphead)，防止出错。
查找需要内容具体位置
当我们想要知道我们存储的数据在哪个位置时，我们就需要进行查找，返回其地址即可
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* find = phead; while (find) { if (find->data == x) return find; find = find->next; } printf("没找到\n"); return NULL; }
这里我们依旧使用暴力查找法，进行逐一对比查找！！！
单链表的基本功能我们已经形成，我们已经完成了头插、尾插、头删、尾删。单链表的基本内容和注意事项已经强调。我们其实还可以继续完善单链表，使其功能更加强大，在这里博主就不过多的说明了，其中的原理和注意事项和前面差不多。
现在我将剩下一些功能逐一展现供大家参考：
其他功能
//在pos之前插入x void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos之后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos);
在pos之前插入x：
void SLTNInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && pos); SLTNode* newnode = BuySListNode(x); SLTNode* find = *pphead; SLTNode* finding = NULL; if (*pphead == pos) { newnode->next = *pphead; *pphead = newnode; return; } else while (find != pos) { finding = find; find = find->next; } finding->next = newnode; newnode->next = find; }
在pos之后插入x：
void SLTInsertAfter(SLTNode* pos, SLTDataType x); { assert(pos); SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; }
删除pos位置的数据：
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead&&pos); SLTNode* find = *pphead; SLTNode* finding = NULL; while (find != pos) { finding = find; find = find->next; } if (*pphead == pos) { SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; } else { finding->next = find->next; free(find); find = NULL; } }
删除pos之后的数据：
void SLTErasetAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { printf("后面没有数可以删除\n"); return; } else { pos->next = pos->next->next; free(pos); pos = NULL; } }
以上就是复现无头单链表的全部内容，有兴趣的可以继续打磨添加一些新功能。
本期内容到这里就结束了，觉得博主内容有用的关注一下博主，一健三连是对博主最大的鼓励！再次感谢大家观看！！！
