数据结构|链表

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

单链表的形式就像一条铁链环环相扣

它与顺序表最大的不同是，单链表的数据存储是在不连续的空间，存储的数据里面含有下一个数据的地址，我们访问下一个数据，只要访问这个数据的地址，然后通过地址找到接下来的数据。

顺序表的创建

我们这样写就写死了，我们利用一个typedef来灵活书写数据的类型

后面我们利用SLTDatetype就可以代替int

之后，我们要修改数据类型，只需要改typedef后面的int

我们先写一个单链表的打印函数

单链表也是可以打印的，只不过我们打印出来的是空的

我们先在主函数创建一个结构体

那么我们的打印函数就可以设计成

利用一个while循环来就行多次打印，如果phead为空指针我们就不打印
如果单链表为空，我们就打印一个空指针

数据的添加有头加，尾加，在某个位置加

数据的删除有头删，尾删，删某个位置数据

数据的头加

我们插入数据前需要申请空间，利用malloc申请一个结构体大小的空间

申请后我们将数据赋给申请节点的data

将里面的指针暂时置空，如果后面有数据再连接起来

我们不确定后面是否还有数据，所以我们将node->next的值与传入的函数相连接

我们链表的头就等于我们头插数据申请的地址
我们为什么要使用二级指针进行操作？
我们知道，形参是实参的临时拷贝，如果改变里面的数据就需要传它的地址，直接对地址里面的元素进行操作。
上面的也是一样，我们传结构体的地址，然后我们利用二级指针进行接受，这样我们就可以修改结构体里面的内容

我们头插一下数据看看

尾插一个数据

尾插数据怎么做到的

我们也需要分类谈论，如果是一个空链表我们直接将node与plist连接就好了

我们尾插数据的时候也需要利用malloc申请空间，然后你就会发现，部分的代码与头插的相识，就是申请空间，那么我们后续可以专门封装一个申请空间的函数，增加程序的可读性

第一步：申请空间

第二步：判断是否为空链表，空链表直接插入

第三步：找到原链表的最后一个地址，将最后的地址与新申请的连接上

我们如何在特殊位置插入数据呢，比如我们在pos位置后面插入数据，我们怎么操作

从图中看出，我们将新申请的节点给pos->next，我们给pos->next之前我们需要将pos->next的地址存起来，因为pos->next存的是原pos后面的地址

使用我们可以先将pos->next给新申请节点的next，然后再将新节点的地址给pos->next

我们在pos之后插入数据之后我们，需要知道pos的位置，我们创建一个函数专门来查找指针的地址

在pos后面插入数据函数

我们来用一用

那么在pos的前面怎么插入数据，其实方法可以与在pos后面插入一样，只要将在pos后面插入的数据，与pos处的数据交换就好了

下面我们来进行删除操作

怎么删除首元素呢

我们进行删除前需要判断链表是否为空，空链表就无法删除了

我们头删前将首地址记录，完成删除后，我们将地址释放

首先我们是将第二个元素的地址给头

然后释放首地址

数据的尾删又是怎么操作的

首先判断是否是空链表
如果只有一个元素直接删除
如果有多个元素我们先找到它的尾再进行删除

这种方法可以不需要记录，我们间接的记录了地址，释放，置空，就好了

如何删除pos之后的元素

第一步：寻找pos的位置
第二步：删除（画图）

在删除pos前的元素，操作大同小异