单链表的头插，尾插，头删，尾删等操作

前言

1. 顺序表要求是具有连续的物理空间，并且数据的话是在这些空间当中是连续的存储。但这样会带来很多问题，比如说在头部或者说中间插入的话，效率不是很高；并且申请空间可能需要扩容，并且越往后一般来说都是异地扩容，虽然看起来的话是简单的调用了一下realloc，但是从底层来看的话，这个代价很大。而且扩容的话也会存在一定程度的浪费，因此就需要链表的存在。

2. 链表的话是一个数据存一个内存块。这些内存块之间并不一定要求是物理上连续的，这些内存块之间用指针进行相关的链接，链表实际上具有八种结构。

3. 链表其实就是用指针这么链接起来的一些个内存块。

链表当中各个节点在物理上不一定是连续的，这个节点之间也并没有任何的顺序关系(都是各自随意malloc出来的)，根本就不需要去考虑顺序，孤岛之间只需要有一根桥梁即可

单链表就关注这三个有机组成部分：

1. 节点 SLTNode

2. 节点地址(指向节点的指针) SLTNode*

3. 一级指针(指向链表第一个节点) phead

4. 二级指针(指向上面的一级指针) pphead

---

逻辑结构与物理结构

1. 虽然有时候平时画图的时候，画链表的时候可能会带一些箭头之类的，但是真正在内存里面是不可能有箭头这些东西的。内存里面是不可能存着箭头→这些东西的。我们把这些箭头叫做逻辑结构，是我们想象出来的，因为这些箭头比指针更为直观。

2. 在内存里面实实在在怎么存的被称为物理结构。

3. 我们画图的时候看起来好像指针啊什么呀都是在动的，但实际上在内存里面的话，一切都是死的，没有动，无非就是不断的给指针变量进行赋值。然后在我们脑海中直观的形象表现就是：该指针变量不断的指来指去。

4. 逻辑结构就是我们为了方便理解，形象化画出来的；但是在计算机内存里面是十分枯燥的，实实在在数据在内存中的变化是物理结构。

---

单链表节点(结构体类型)的创建

1. 从语言的角度来讲，凡是有多个数据，都需要存到结构体里面去。链表的每一个节点就是通过结构体来表示。结构体里面有当前的数值data，并且还需要一个指针。因为上一个节点需要存下一个节点的地址，这样我才有寻找的依据，这样的话，各个内存块之间才可以像链条一样这么串起来。

2. 并且我们已经知道每一个节点实际上就是一个结构体。既然上一个节点需要存下一个节点的地址。那么因此显而易见，无非就是一个结构体指针罢了，我们叫做next。

3. 之前在c语言当中我们也讲过，结构体里面是不能够嵌套结构体的，就是无穷套娃了。但我们刚才结构体里面并没有结构体，是一个结构体指针，大小是确定的，就是四个字节。

//节点结构体的创建
typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;

单链表的打印

1. 空的顺序表可以打印，当然一样道理，空的链表也可以打印，给我显示为空不就可以了

2. phead就是链表第一个节点的地址，如果这个链表是空链表，那么phead就是NULL

3. 当我为空链表的时候，phead就为NULL，在打印链表的时候不能够进行断言，不然的话空链表我就打印不出来了，直接把我程序终止了。

4. 链表的话在物理上并不是连续的，它的每一个节点都是malloc出来的。

5. 每一个节点（说白了就是结构体）都会存放下一个节点的地址，因此就需要这一很关键的一步:cur = cur -＞ next

6. 0就是假，非0就是真，NULL本质就是0。

//单链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->",cur->data);cur = cur->next;}printf("NULL\n");
}

单链表malloc一个新节点并赋值

//单链表malloc一个新节点并赋值
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuySLTNode::Malloc");return NULL;}newnode->data = x;;newnode->next = NULL;return newnode;
}

单链表的尾插

1. 由于之前一样的，在这个地方是不能够进行空指针断言的，因为如果是断言的话，我在空链表的情形下想要去尾插，但是断言了的话，给我程序提前终止了，这还玩个屁啊。

2. 尾插的第一步是先得搞一个节点出来，这个地方就不像顺序表一样了，要考虑什么空间够不够啊，要不要扩容啊之类的就不需要考虑了。在这边的话就自己去malloc新创建一个节点。

3. 然后对于这个新节点newnode的值给进去，next指针为NULL。

4. 然后就是找到原先的尾巴，原尾节点的next成员要存储新尾节点的地址。

5. 刚才讲的情况都是链表不为空的情况，如果链表是空的话，这种情况需要额外处理。这时候只需要把phead指向新节点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;}
}

单链表的头插

1. 这个也需要分两种情况，以总是链表为空的情况，第二种就是链表非空。但是发现仅有的三行代码可以完全解决空的情况。

2. 然后发现在这个函数内部也需要创建一个新的节点。那么就是说可以把创建新的节点这个过程给他单独的提取出来。

//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

单链表的尾删

1. 删除的时候也是需要用二级指针。因为万一你要把指针置空的时候，如果你传一级指针的话，就完蛋了。那么原先那个指针就变成野指针了。

2. 链表在尾删的时候要注意分几种特殊情况，第一种情况是当前只有一个节点，第二种特殊情况就是整个链表都是空的。对于第一种情况直接free，然后把指针置空就完事儿了。对于第二种情况，直接暴力assert检查就可以。

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}prev->next = NULL;free(tail);tail = NULL;}
}

单链表的头删

1. 首先也可以暴力检查一下这个链表是不是空的。但头删不需要特判链表只有一个节点的情况。

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first = *pphead;*pphead = (*pphead)->next;free(first);first = NULL;
}

---

单链表的初始化

这个非常简单，直接初始化就可以，因为只有一个值。直接创建一个结构体指针赋为NULL就可以

SLTNode* plist = NULL;

关于单链表函数操作中的有关于assert断言的问题

不是在参数里面碰到一个指针就assert一下，不是这么一根筋的。像这边单链表的话，当phead为NULL时我们都知道此时此刻表示一个空链表，但是空链表我就不能头插，尾插插入了吗？我照样可以这么插入；空链表难道我就不能打印了吗？我照样可以打印，只是什么都没有而已。但是对于删除而言，如果此时此刻你已经是一个空链表了，那么你还删个毛线啊？所以此时此刻呢又需要用assert断言一下，这种东西都是具体问题具体分析。

关于参数为二级指针的问题

1. 尤其要注意形参的改变不会影响实参，这个其实底层要理解的话，就是得通过函数栈帧。当传址调用的时候，实际上地址也是在拷贝，但由于你是在函数里面对指针进行解引用操作，因此产生的影响是持久性的，即使调用的函数退出回来了。

2. malloc向堆区动态申请内存的时候，是随机在内存里面划分一块区域的。

3. 当你的实参是一个指针的时候，虽然这时候函数传参看起来好像也是传址调用，但实际上调用函数内部执行的各种操作，对于函数外头的这个参数指针不会发生任何影响。因为实际上无论如何都会有拷贝这个环节会发生。

4. 在这边想要着重说明的是：我们在进行函数传参的时候，这时候就必须传二级指针。我们在函数体外已经先有一个指针，我们的函数内部操作都离不开要改变该指针的指向位置，要实现这个操作，就不能传一级指针，因为这样只有我这个一级指针自己在捣鼓；如果我传指针的地址（也就是二级指针），这样子我才能在函数体内去改变函数体外这个指针所指向的位置。

5. 我这个phead是一个实实在在的结构体指针，各种有关于单链表的操作，其中都需要phead指向的位置发生变化，如果在函数里面传一级指针的话，函数里面的各种乱七八糟的运转，跟我函数外面的phead指针一点关系都没有，因为你在函数内部自己有一个参数指针(形参)，也许这个形参与phead指向的地址是一样的，但是当你传一级指针的时候，在函数里面各种捣鼓运算改变的都是你形参指向的位置。如果想要改变我这个phead指针指向的位置，就必须把phead的地址当成参数传给函数，因此这个参数也就是指针的地址，显而易见即为二级指针。