数据结构学习之链表学习：单链表
在之前顺序表的学习过程中，我们知道顺序表中头插和中插的复杂度是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和ptailSLN*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;
}本期单链表的内容到此结束，后续我们会就单链表的问题进行一些题目的练习，或者学习其他的链表结构。在这里求个赞，谢谢