在之前顺序表的学习过程中，我们知道顺序表中头插和中插的复杂度是O（N）。那我们可不可以将其降低为O（1）呢？可不可以不增容想用就用想扔就扔而不会浪费一点空间呢？那就是我们今天的内容：链表
继我们学习了顺序表之后，接下来我们就来学习顺序表的下一个内容：链表。
目录
链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是链表中指针链接次序的实现
那么链表是如何实现的呢？
以火车为例，火车的车头和车厢并不是粘连在一起的，而是通过连接起来的，可以增减车厢的个数。每个车厢是独立存在的，增减某一元素对原有数据不影响
再单链表中“车厢”就是结点，而单链表就是由结点构成的。
而由于上图可知，结点是由数据元素及保存下一个结点地址的指针组成的。
接下来我们来学习单链表的实现。
单链表
我们需要三个文件来准备
SList.h——声明结构体的组成、声明函数方法
SList.c——实现函数
test.c——单链表测试
单链表的组成
typedef int SListDataType;
//定义链表结构——节点
typedef struct SListNode
{
SListDataType data;//保存的数据
struct SListNode* next;//指向下一个节点的指针
}SLN;单链表的打印函数
SList.h
//链表的打印
void SLN_print(SLN* next);SList.c
//链表的打印
void SLN_print(SLN* phead)
{
SLN* p = phead;
while(p!= NULL)//可以简写为while(p)
{
printf("%d ->", p->data);
p = p->next;
}
printf("NULL\n");
}创建单链表的新节点
//根据x创建节点
SLN* SLN_buy_node(SListDataType x)
{
//根据x创建结点
SLN* new_node = (SLN*)malloc(sizeof(SLN));
if (new_node == NULL)
{
perror("malloc error");
return 1;
}
new_node->data = x;
new_node->next = NULL;
return new_node;
}单链表的尾插
前面我们知道链表是依赖于指针连接起来的，所以我们创建一个空链表是这样的
//创建一个空链表
SLN* slist =NULL;因此，我们进行尾插的时候分为两种情况：链表为空和链表不为空
链表为空时，直接将新结点赋值给首结点；不为空时，从前往后走，当指针不为空时向后走，当指针为空的时候跳出循环，插入结点，尾部节点指针为NULL。
代码为：
//链表的尾插
void SLN_back_push(SLN** pphead, SListDataType x)
{
SLN* new_node = SLN_buy_node(x);
//链表为空
if (*pphead == NULL)
{
*pphead = new_node;
}
else
{
//找尾结点
SLN* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//找到尾结点
ptail->next = new_node;
}
}单链表的头插
头插思路：
//链表的头插
void SLN_head_push(SLN** pphead, SListDataType x)
{
assert(pphead!=NULL);
SLN* new_node = SLN_buy_node(x);
new_node->next = *pphead;
*pphead = new_node;
}单链表的尾删
//链表的尾删
void SLN_back_pop(SLN** pphead)
{
assert(pphead!= NULL&&*pphead!= NULL);
//找prev和ptail
SLN*prev = NULL;
SLN*ptail = *pphead;
//找尾结点
while (ptail->next != NULL)
{
prev = ptail;
ptail=ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}但是这段代码当链表只有一个结点的时候就会出错，
单链表的头删
void SLN_head_pop(SLN** pphead)
{
assert(pphead != NULL && *pphead != NULL);
SLN*next=(*pphead)->next;
free(*pphead);
*pphead=next;
}单链表的查找
//链表的查找
SLN* SLN_find(SLN* pphead, SListDataType x)
{
SLN*p=pphead;
while (p != NULL)
{
if (p->data == x)
{
printf("find %d\n", x);
return p;
}
p = p->next;
}
return NULL;
}单链表插入数据
指定位置之前
思路图：
prev的指针指向newcode的数值，newcode的next指针指向pos
代码：
//指定位置之前插入
void SLN_Before_insert(SLN** pphead, SLN* pos, SListDataType x)
{
assert(pphead != NULL && pos != NULL);
// pos 是头节点，执行头插
if (pos == *pphead)
{
SLN_head_push(pphead, x);
}
else
{
SLN* newnode = SLN_buy_node(x);
// 找pos的前一个结点
SLN * prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev--> newnode--> pos prev->next = newnode;
prev->next = newnode;
newnode->next = pos;
}
}指定位置之后
思路图：
只需要将pos的next指针指向newcode，将nextcode的next指针指向下一个数据，即以下这种情况：
newcode->next=pos->next;
pos->next=newcode;代码：
//指定位置之后插入
void SLN_After_insert( SLN* pos, SListDataType x)
{
assert(pos);
SLN* newnode = SLN_buy_node(x);
newnode->next = pos->next;
pos->next = newnode;
}单链表删除数据
指定结点
思路：
//指定结点删除
void SLN_delete(SLN** pphead, SLN* pos)
{
assert(pphead&&pos);
//pos是第一个节点
if (pos==*pphead)
{
SLN_head_pop(pphead);
}
else
{
SLN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}指定节点之后
//指定位置之后插入
void SLN_After_insert( SLN* pos, SListDataType x)
{
assert(pos);
SLN* newnode = SLN_buy_node(x);
newnode->next = pos->next;
pos->next = newnode;
}单链表的结点数据修改
//链表的数据修改
void SLN_change(SLN** pphead, SLN* pos, SListDataType x)
{
assert(pos);
pos->data = x;
}单链表的销毁
//链表的销毁
void SLN_destroy(SLN** pphead)
{
SLN* p = *pphead;
while (p != NULL)
{
SLN*next=p->next;
free(p);
p=next;
}
*pphead = NULL;
}本期单链表的内容到此结束，后续我们会就单链表的问题进行一些题目的练习，或者学习其他的链表结构。在这里求个赞，谢谢