🌈个人主页：七度光阴；
🎉系列专栏：数据结构与算法
目录
一、🚀链表的概念和结构
二、🚀链表的分类
三、🚀单链表的实现
📝动态申请节点+单链表查找
单链表的尾插+单链表的头插：
📝单链表的尾删+单链表的头删：
📝 单链表在pos位置之后插入x+单链表在pos位置之前插入x
📝删除pos位置的值
📝单链表的销毁
四、🚀所有代码
一、🚀链表的概念和结构
上一节我们了解了顺序表这个结构，同样的顺序结构还有单链表这个结构，通俗的来讲单链表就像一个小火车🚆一样，是一种形式上连续，物理空间上可能不连续的结构！
这里如果用一个指针变量执行我们的下一个节点，那么这就是单链表的结构了
图中的phead指针中存放的是第一个结点的地址，那么根据指着地址我们就可以找到这个结构体，又因为这个结构体中存放了下一个结构体的地址，所以又可以找到第二个结构体，循环往复就可以找到所有的结点，直到存放空地址的结构体。
注：图中的箭头实际上是不存在的，这里只是为了能够方便理解。
注意：
1. 从图中可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。 2. 现实中的结点一般都是从堆上申请出来的。 3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
二、🚀链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
虽然链表结构如此之多，但是我们常用的就只有两种
三、🚀单链表的实现
所谓单链表就是无头+单向+非循环 链表
📝动态申请节点+单链表查找
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//realloc是调整空间，malloc是申请空间
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);//防止链表为空，链表为空则查找的无意义
SListNode* cur = plist;//一般不希望指向头结点的指针plist被改变，想让plist不动始终指向头结点
while (cur)//保证不漏掉任何一个结点
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
单链表的尾插+单链表的头插：
单链表的尾插：
先创建一个新的结点（newnode），然后在创建一个新的指针变量tail，让tail一直遍历，一直遍历到尾结点，然后令尾结点的tail->next = newnode:,然后令newnode->next = NULL;
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);//先申请一个结点
if (*(pplist) == NULL)//链表为空时尾插
{
*pplist = newnode;
}
else//链表不为空时
{
SListNode* tail = *pplist;
while (tail->next != NULL)//令tail找到最后一个结点
{
tail = tail->next;
}
tail->next = newnode;
}
}
单链表的头插
先malloc一个结点（newnode），先令newnode->next = *pplist;,然后令*pplist = newnode；，
为什么传的是2级指针呢？
因为是要改变指针的内容，所以传的是指针的指针，然后对其解引用，即可访问指针的内容
void SListPushFront(SListNode** pplist, SLTDateType x)//注意：这里传的是2级指针，改变指针则传指针的地址
{
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
newnode->next = *pplist;
*pplist = newnode;
}
}
📝单链表的尾删+单链表的头删：
单链表的尾删🍨
拿一个指针tail指向尾结点，在拿一个指针tailPrev指向尾结点的前一个结点，然后令tailPrev->next = NULL;,假如没拿一个指针tail记录尾结点的地址，当tailPrev->next = NULL;时那就意味着尾结点的地址丢了，此时会造成内存泄漏，因此拿一个指针tail记录尾结点的地址，最后千万不要忘记释放删除的节点free(tail);
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
单链表的头删🍨
拿一个指针（next）记录首结点的下一个结点，然后free（*pplist）;,随后在把plist指向新的首结点（*pplist = next:）
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
📝 单链表在pos位置之后插入x+单链表在pos位置之前插入x
单链表在pos位置之后插入🍨
首先要拿一个next指针记录pos结点之后的一个结点，然后链接pos结点和newnode结点（pos->next = newnode;）,随后在链接newnode和next结点（newnode->next = next;）,假如不拿一个指针next记录pos的下一个结点，那此时要注意插入的结点和前后结点的链接顺序，假如不注意链接顺序可能会丢掉pos之后结点的地址，导致pos之后的结点无法与新节点newnode链接到一起
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
单链表在指定之前插入🍨
拿一个指针（prev）记录pos之前的一个结点，然后在malloc一个新的结点（newnode），然后令newnode中的next存下pos的地址，在令prev（原来pos之前的一个结点）和newnode链接到一起prev->next = newnode
void SListInsertFront(SListNode**pplist,SListNode* pos, SLTDateType x)
{
assert(pos);
assert(*pplist);
if (pos == *pplist)
{
SListPushFront(pplist, x);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)//找到了pos结点之前结点的地址
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
📝删除pos位置的值
先拿一个指针（prev）记录下pos之前的一个结点，在拿一个指针（next）记录下pos之后位置的结点，然后在把prev指向的结点和next指向的结点链接到一起prev->next = next;，然后在free(pos);
void SListErase(SListNode** pplist, SListNode* pos)
{
assert(pos);
assert(*pplist);
//头删
if (pos == *pplist)
{
SListPopFront(pplist);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)//找到pos之前的一个结点
{
prev = prev->next;
}
SListNode* next = pos->next;
free(pos);
prev->next = next;
}
}
📝单链表的销毁
建立一个循环，在建立一个指针（prev）去指向首结点（*pplist），然后先把指向首结点的指针（*pplist）去移动指向下一个结点，此时prev相当于记录了原来的首结点，然后在去free(prev);,以此去不断循环，最后当*pplist指向空时循环结束，同时也意味着链表销毁
void SListDestroy(SListNode** pplist)
{
assert(*pplist);//销毁链表一定是链表不为空才去销毁
while (*pplist)
{
SListNode* prev = *pplist;
*pplist = (*pplist)->next;
free(prev);
}
}
四、🚀所有代码
SeList.h
#pragma once
#include
#include
#include
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
//单链表在pos位置之前插入x
void SListInsertFront(SListNode** pplist,SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 删除pos位置
void SListErase(SListNode**pplist,SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode**pplist);
SeqList.c
#include "SList.h"
void SLTPrint(SLTNode* pphead)
{
assert(pphead);
while (pphead)
{
printf("%d ", pphead->data);
pphead = pphead->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newNode = malloc(sizeof(SLTNode));
if (newNode == NULL)
{
perror("malloc fail!");
exit(1);
}
newNode->data = x;
newNode->next = NULL;
return newNode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newNode = SLTBuyNode(x);
if (*pphead == NULL)
*pphead = newNode;
else
{
SLTNode* pur = *pphead;
while (pur->next)
{
pur = pur->next;
}
pur->next = newNode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newNode = SLTBuyNode(x);
newNode->next = *pphead;
*pphead = newNode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead&&(*pphead));
SLTNode* pur =*pphead;
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (pur->next->next)
{
pur = pur->next;
}
free(pur->next);
pur->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* newnode = (*pphead)->next;
free(*pphead);
(*pphead) = newnode;
}
//查找节点
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
assert(phead);
while (phead)
{
if (phead->data == x)
return phead;
phead = phead->next;
}
return NULL;
}
//指定位置之后插入
void SLTInsert(SLTNode** pphead, SLTDataType x)
{
assert(pphead && *pphead);
SLTNode* newpphead = SLTBuyNode(x);
SLTNode* pur = (*pphead)->next;
newpphead->next = pur;
(*pphead)->next = newpphead;
}
小结：链表和顺序表是两个兄弟结构，大家如果不了解顺序表的可以点击下方跳转
数据结构——顺序表