数据结构之 “单链表“

（1）在顺表表中，如果是头插/删的时间复杂度是O(1)；尾插/删的时间复杂度是O(N)
（2）增容一般是呈2倍的增长，势必会有一定的空间浪费。比如：申请了50个空间，只用了两个？(链表可以解决空间浪费的问题)

这一章节的内容是关于单链表。

1. 链表

链表也是线性表的一种。我们仍然从物理结构和线性结构来分析
(1)物理结构(真实)：不是线性
(2)线性结构(想象)：线性

重点：链表是由一个一个的结点连接起来的。每次创建一个结点，不存在浪费的情况。
一个结点里面存储的是：数据+下一个结点的地址。

链表里的结点，它们的地址不是连续的，而是靠(存储的地址)连接起来的。

(3)在链表中，没有增容的概念。如果要增加数据，直接再申请一个结点大小的空间即可。

2. 单链表

1. 单链表的概念

单链表的全称是”不带头,单向,不循环链表“。

1. 单链表的定义：在.h里

（1）创建链表—>在test.c里

这个方法只是示范一下，平常创建链表并不会像这么麻烦。
在初始情况下，链表是空链表，只有一个结点，指向NULL，之后尾插即可达到申请结点的结果。

//这个是写在test.c的内容#include"SLTNode.h"
//创建链表
void creatListNode()
{//使用malloc记得写头文件stdlibSLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;node1->next = node2;node2->next = node3;node3->next = NULL;
}int main()
{creatListNode();return 0;
}

（2）打印链表出来看看

2. 单链表的实现

2.1 尾插

不管是头插还是尾插，都需要再申请一个结点大小的空间，所以可以将它封装为一个函数，之后调用即可。

尾插比较简单，有两种可能。

1.链表不为空。最后一个结点的next指向NULL，我们只需将 (最后一个结点的next) 指向 (想插入的结点的地址newnode) 即可。

2.链表为空，就不用找结点了。在刚开始时，我们创建了链表struct SLTNode，这是空链表，只有一个头结点(phead)指向NULL，我们将phead->next指向newnode即可

注意在尾插时传过去的是地址，这样形参的改变可以改掉实参。

//SLTNode.h里的内容#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义链表的结点
typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//申请新结点
SLTNode* SLTBuyNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);//打印链表
void SLTPrint(SLTNode* phead);

//SLTNode.c里面的内容#include"SLTNode.h"
//用于打印链表的函数的定义
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d(地址:%p) -> ",pcur->data, pcur->next);pcur = pcur->next;}printf("NULL");
}//用于申请新结点的函数的定义
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//判断一下是否申请成功if (node == NULL){perror("malloc");return 1;}node->next = NULL;node->data = x;return node;
}//尾插函数的定义         pphead是第一个结点指针的地址（地址的地址）
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//先申请新结点SLTNode* newnode = SLTBuyNode(x);//链表为空if (*pphead == NULL)        //*pphead是第一个结点的指针(指向空，不能->next){*pphead = newnode;}else  //链表不为空{//接下来将尾结点->next指向newnode//找尾结点不能用phead直接遍历找到尾结点，因为这样的话就找不到第一个结点了(单链表只能往后)我们需要重新申请一个来存放第一个结点的地址)SLTNode* pcur = *pphead;while (pcur->next)         //不为NULL时可进入循环{pcur = pcur->next;     //将指针pcur里存放成下一个结点的地址}//出循环表示pcur是尾结点地址，将它的next修改pcur->next = newnode;}}  

//test.c的内容#include"SLTNode.h"
void SLTtest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPrint(plist);SLTPushBack(&plist, 2);SLTPrint(plist);SLTPushBack(&plist, 3);SLTPrint(plist);
}int main()
{SLTtest01();return 0;
}

2.2 头插

1.头插仍然是将pphead（地址）传过去
2.头插是将申请的结点的next指向第一个结点的地址。即 newnode->next =* pphead
3.记得最后将*pphead移到新结点处

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);   //已经头插了，那传过来的参数指定不能为空SLTNode* newnode=SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}

2.3 尾删

尾删：链表不可以为空。

在尾删时，不能直接将最后一个结点释放再置为空，因为我们还需要找到倒数第二个结点，将它的next改为NULL。

还有可能遇见只有一个结点的情况，我们直接把它释放置为空即可。

方法：
（1）创建一个ptail，遍历，使之成为倒数第二个结点，即ptail->next->next=NULL;,将ptail->next指向空。再将ptail往后走成为最后一个结点，将其释放。

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //传过来的参数不能为空，链表不能为空if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* ptail = *pphead;while (ptail->next->next){ptail = ptail->next;}  ptail->next = NULL;ptail = ptail->next;free(ptail);ptail = NULL;} 
}

（2）将prev一直是ptail的前一个

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //传过来的参数不能为空，链表不能为空if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;            //第一次时，prev=*ppheadptail = ptail->next;     //第一次循环时，ptail=第二个结点的指针}                            //当ptail->next=NULL时，ptail最后一个，prev是倒数第二个prev->next = NULL;free(ptail);ptail = NULL;}
}

2.4 头删

头删同样需要断言。

要是删除第一个结点，那么第二个结点等一下就找不到了，我们应该先将第二个结点存起来。再将*pphead释放，再将 * pphead指向第二个结点

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;
}

2.5 查找

不用传地址过去，并不希望在查找时不小心将内容修改

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

2.3 特定位置（之前/之后）插入

1. 在特定位置之前插入，那插入这个数据会影响谁呢？（需要第一个结点）

由图可知：prev->next 将会被影响。

但是如何可以找到prev呢?单链表只能从前往后找，并不能从pos往前找。

我们可以采用循环，直到 xxxx->next == pos为止。当满足这个条件时，xxxx就是prev。

注意：在插入时，链表phead可以为空，但参数pphead不能为空。pos也不能为空

prev->next = newnode;
newnode->next = pos;

//SLTNode.h里的内容
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)；

//SLTNode.c里的内容
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果pos是第一个结点，那么这就变成头插了if (pos == *pphead){SLTPushFront(*pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);  //新结点SLTNode* prev = *pphead;           //先让prev是第一个结点的指针while (prev->next!=pos)            //循环让prev=pos前一个结点指针{prev = prev->next;}prev->next = newnode;             //让prev的下一个是新结点newnode->next = pos;}
}

//test.c里的内容//通过x找到pos
SLTNode* find = SLTFind(plist, 2);
SLTInsert(&plist, find, 9);

2. 在特定位置之后插入（不需要第一个结点）
   

在“特定位置之后插入”的函数的参数中，并没有第一个结点的地址，为什么呢？

我们已经知道了pos这个地址，可以直接找到它的下一个结点的地址，并不需要通过头结点一个一个往后找。

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead&&pos);//如果是空链表if (*pphead == NULL){SLTPushBack(*pphead, x);}//不是空链表else{SLTNode* newnode = SLTBuyNode(x);  //新结点SLTNode* Next = pos->next;  //pos的下一个结点pos->next = newnode;newnode->next = Next;}
}

2.6删除特定位置pos处的结点

需要修改pos前一个结点 (prev) 的next，所以需要第一个结点（循环遍历找pos前一个结点）

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

2.7 删除pos之后的结点

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

2.8 销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}