上一篇中，我们已经了解过了顺序表了，但是，顺序表有哪些不便的地方？
一.顺序表的缺陷问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
头插N个数据时间复杂度：O(N^2)
需要挪动数据，效率低下
解释：因为头插要将原本所有的数都向后移动一位
尾插N个数据时间复杂度：O(N)
所以尽量避免去使用头插。2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对此，我们为了解决上述问题，链表就大大的解决了这些困扰。
正文开始：
链表
介绍
1.链表的概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
可以先简单理解成下图：
物理结构
实实在在数据在内存中的变化
下面的是逻辑结构，为了方便理解，形象化画出来的‘
原理：上一个节点要存下一个节点的地址
我们可以看出它的地址相同的部分知道，它们是一个又一个地连在一起。
后面画图更简便就成了下图：
构造：
typedef int SLTDataType; 为了后面一眼就能看到它的类型的意思
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;解读：struct SListNode* next;通过指针链接起来。
首先，我们先区分下面可能出现的问题吧：
指针类型是什么？
结构体指针
结构体肯定不能嵌套结构体
相当于自己里面一个我自己，这就造成无穷套娃了
但是可以结构体里面嵌套一个结构体指针，只是这个类型是结构体
是结构体
结构体没有执行的概念，函数才讲执行
因为编译的寻找规则：从上面找，
struct SListNode* next
不能：SListNode* next，虽然你在下面自定义了，但编译器只能往上找啊，找不到，就显示错误了。
初始化问题
对比：我们在顺序表时，为什么要进行初始化呢？
因为在顺序表时，我们是实实在在地开辟了一个空间（已经开辟好了的），来供后续使用，因此需要来进行初始化这块空间。
但是在链表中呢？
在链表中，我们是当要使用了，才会链接成新的结点，此时新结点的空间才会开辟使用，这时候就不用额外初始化了。
打印部分：
我们知道顺序表是通过数组历遍打印出来的。
如：
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->sz; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}链表中打印与顺序表不同：
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
//while (cur->next != NULL)
//while(cur != NULL) 这几种都是一样的意思
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
这里可不能使用cur++;
}
printf("NULL\n");
}易错：
链表打印当中(如左图)，想要从1->2，可不能直接cur++。
因为链表的每一个节点都是单独malloc出来的，你只有一次mallooc很多个（如10个），能保证它的空间是连续的才可，而链表不能保证它连续，
有人又说我们让它连续不就好了吗？
你想想这样的话它不就变成了数组了吗？顺序表因此！
要cur指向2做法：就cur=cur->next
解释：cur是一个结构体指针，加->这个符号就是结构体的内容，next是结构体成员
next是下一个节点的地址，赋值后就去到了2的地址位置，依次去到最后位置
注意：
这里while循环是不能：while（cur->next ！=NULL）
这里到了最后一个数据时，为空了，最后一个数据就不能打印了
所以应该是while（cur！=NULL），也可以while（cur），因为0就是假，非0就是真
空就是0.
同时，我们会发现，为什么，链表的打印部分不用断言，顺序表那边需要断言。这与我们之前学到认为指针，基本都需要断言的认知是错误的：
下面给出解释：
答案：
链表：这个指针是指向第一个存有数据的节点
顺序表,指针指向一个结构体，而数据不是存在结构体上面的
如果有数据，则它存在的是这样一个空间上面（下图）
链表（下图）
对于链表为空，那么phead就为空,但，对于顺序表为空，那么这个指针（指向结构体）不能为空，哪怕这个顺序表一个数据都没有，那么这个结构体也是有的，只是你这个a为不为空也不重要，它到底有没有数据，取决于size是不是0，如0就没有数据，所以有没有空间都不是最重要的
因此！！！我们可以得出：！！所以不要看到指针就写断言！！！！要按照具体需求来判断。
创建新结点
因为，下面写道的尾插，尾删，头插，头删，中间位置插，删都用到新结点的内容，为了让后面的代码更简便，我们在这里创建一个独立的函数，后面直接调用就可以了。
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}图解：将x赋值到newnode中，再将newnode的下一个置空
尾插部分：
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}它的过程分析如下：
首先把你要尾插的值放到新的节点；
接着为了后面方便直接找到头节点，所以不使用它本身来找尾。因此重新弄了个tail的指针，开始位置也再*pphead那里
然后，开始正式找尾，以tail的下一个为准，若下一个为空指针，则说明已经找到尾。就跳出循环，把新节点和尾巴连接在一起。若不为空，就把tail跳到tail的下一个，依次判断。
注意易错的点：
链表的连接一定是：上一个节点要存下一个节点的地址
尾插的细节
本质：原尾结点中要存储新的尾结点的地址
while（nur ！=NULL）
{
tail=tail->next;
}
tail=newnode 错误的这样就链接不上去了
(图解析看上面)
正确是tail->next !=NULL
tail->next=newnode尾插的时候要改变的是结构体，要改变结构体就得改变结构体的成员，结构体的成员也是一个指针而已，但是有了结构体的指针已经能够改变它的成员了
另外，我们为什么传的是二级指针呢？
我们先了解：
形参的改变不影响实参
非常实用的理解方式：
改变的是int，使用的就是int的指针
改变的是int*，使用的就是int*的地址，int**指针
可以这样理解：
不改变实参就直接传，改变就传地址而我们现在的，就是要改变结构体指针里面的值，所以要双指针。
现在我们来分析分析：
我们可以看出，形参的改变不影响实参，出去了之后就销毁了。就无法回到mian函数
再看我们 如果这样？
通过使用它的地址，解引用保存了，就可以不被因为销毁，而不能达到目的。
有了以上的认识后，我们可以解释本次的问题了：
头插部分：
传二指针的问题，跟上面一样。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}现在来分析它的过程：
先把原本的头赋值给新头的next。
接着再将plist指向newnode
尾删部分
void SLTPopBack(SLTNode** pphead)
{
// 暴力检查
assert(*pphead);
// 温柔的检查
//if (*pphead == NULL)
// return;
// 1、只有一个节点
// 2、多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 找尾：第一种方法
//SLTNode* prev = NULL;
//SLTNode* tail = *pphead;
//while (tail->next != NULL)
//{
// prev = tail;
// tail = tail->next;
//}
//free(tail);
//tail = NULL;
//prev->next = NULL;
第二种方法：
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}它的过程分析：
先创建一个prev（为NULL），tail（初始在头位置）
接着就是找尾，标志为：tail的下一个是否为0；若是则尾，不是就继续向右移动
最后找到了之后，将tail（即尾巴释放）
除此之外，我们还要释放prev的下一个为空。
为什么呢？有人会问，它不是tail已经为空了吗？
但是，你想一想，你都已经释放掉tail了，你还弄空，还有用吗？这不就相当于下面这种情况了吗？
这就是为什么我们在开始之前，要再定义一个prevx新指针。
释放prev的下一个为空。就成了下面的图解释的那样了。
第二种方法：图解
头删部分
void SLTPopFront(SLTNode** pphead)
{
// 暴力检查
assert(*pphead);
// 温柔的检查
//if (*pphead == NULL)
// return;
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}这部分的原理有了上面的铺垫，也是比较简单的（相对上面的 ）就不具体分析了，给下图，应该能够明白的！
查找部分：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}这一部分没有什么好解释的。
插入任意中间的位置部分
其中又分为两种情况：
1.pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
// 找到pos的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
它的过程分析：
先在原本头位置设定一个prev指针
接着找到pos的前一个位置
然后找到后，就当前prev位置的下一个指针指向newnode
newnode指向pos位置，就完成了中间插。
2.在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next; | 这两步可不能调乱
pos->next = newnode; |
}为什么不能调乱呢？请看下面
如果调乱了，这第一步就不是把2-3的箭头去掉了吗，那后面的地址（next）就找不到了，连不到一起了 。
由代码量就可以看出来，这种方法更加简单
删除任意中间的位置部分
分为两部分
1.pos位置前删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
// 找到pos的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
//pos = NULL;
}
}它的分析过程：
2.pos位置后删除
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
//SLTNode* del = pos->next;
//pos->next = pos->next->next;
//free(del);
//del = NULL;
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}它的分析过程图：
最后一个销毁部分
方法一：
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur=*pphead;
while(cur)
{
SLTNode* temp=cur->next;
free(cur);
cur=temp;
}
*pphead=NULL;
}
方法二：在调用时使用返回方式。
void SLTDestory(SLTNode* phead)
{
SLTNode* cur=phead;
while(cur)
{
SLTNode* temp=cur->next;
free(cur);
cur=temp;
}
它的过程分析：
易错：这里可不能
至此，所有的就已经结束了。
附上所有的代码：
SLT.C
#define _CRT_SECURE_NO_WARNINGS 1
#include "SLT.h"
void SLTPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SListNode* BuySLTNode(SLTDatatype x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SListNode** pphead,SLTDatatype x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
//头插
void SLTPushFront(SListNode** pphead, SLTDatatype x)
{
assert(pphead);
SListNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
//只有一个节点
// 有多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//找尾
else
{
SListNode* tail = *pphead;
SListNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
//头删
void SLTPopFront(SListNode** pphead)
{
assert(pphead);
SListNode* frist = *pphead;
*pphead = frist->next;
free(frist);
frist = NULL;
}
//查找
SListNode* SLTFind(SListNode* phead, SLTDatatype x)
{
SListNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//内插
//在pos之前插
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDatatype x)
{
assert(pos);
assert(pphead);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
//找到pos之前的数字
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//创建一个新的空间
SListNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//pos位置删除
void SLTErase(SListNode** pphead, SListNode* pos)
{
assert(pos);
assert(pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
//找到pos之前的位置
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//pos后面插入
void SLTInsertAfter( SListNode* pos, SLTDatatype x)
{
assert(pos);
SListNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//pos之后删除
void SLTEarseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
void SLTDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur=*pphead;
while(cur)
{
SLTNode* temp=cur->next;
free(cur);
cur=temp;
}
*pphead=NULL;
}
头文件SLT.h
#pragma once
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDatatype;
typedef struct SListNode
{
SLTDatatype data;
struct SListNode* next;
}SListNode;
void SLTPrint(SListNode* phead);
//ͷ
void SLTPushBack(SListNode** phead, SLTDatatype x);
void SLTPushFront(SListNode** pphead, SLTDatatype x);
void SLTPopBack(SListNode** pphead);
void SLTPopFront(SListNode** pphead);
SListNode* SLTFind(SListNode* phead, SLTDatatype x);
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDatatype x);
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTInsertAfter( SListNode* pos, SLTDatatype x);
void SLTEarseAfter(SListNode* pos);
test.c:这一部分只是用做测试，没太大作用。
#define _CRT_SECURE_NO_WARNINGS 1
#include "SLT.h"
Test1()
{
SListNode* s=NULL;
SLTPushBack(&s, 1);
SLTPrint(s);
SLTPushBack(&s, 2);
SLTPrint(s);
SLTPushBack(&s, 3);
SLTPrint(s);
SLTPushBack(&s, 4);
SLTPrint(s);
}
Test2()
{
SListNode* s = NULL;
SLTPushBack(&s, 1);
SLTPushBack(&s, 2);
SLTPushBack(&s, 3);
SLTPushBack(&s, 4);
SLTPrint(s);
SLTPushFront(&s, 5);
SLTPushFront(&s, 6);
SLTPushFront(&s, 7);
SLTPushFront(&s, 8);
SLTPrint(s);
SLTPopBack(&s);
SLTPrint(s);
SLTPopBack(&s);
SLTPrint(s);
SListNode* ret = SLTFind(s, 4);
SLTInsert(&s, ret, 9);
SLTPrint(s);
}
Test3()
{
SListNode* s = NULL;
SLTPushBack(&s, 1);
SLTPushBack(&s, 2);
SLTPushBack(&s, 3);
SLTPushBack(&s, 4);
SLTPrint(s);
SListNode* ret = SLTFind(s, 4);
SLTInsert(&s, ret, 9);
SLTPrint(s);
}
Test4()
{
SListNode* s = NULL;
SLTPushBack(&s, 1);
SLTPushBack(&s, 2);
SLTPushBack(&s, 3);
SLTPushBack(&s, 4);
SLTPrint(s);
SListNode* ret = SLTFind(s, 4);
//SLTErase(&s, ret);
SLTInsertAfter(ret, 6);
SLTPrint(s);
}
int main()
{
Test4();
return 0;
}今次鸡汤：
对未来的真正慷慨，是把一切都献给现在，
你和我！一起奋斗吧！会越来越好的！