1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
从以上图片可以看出：
1.链式结构在逻辑上是连续的，但在物理上不一定是连续的。
2.现实中的节点一般是在堆上申请出来的。
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，可能不连续。
2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
2.1单向或双向
2.2带头或者不带头
2.3循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3 单向无头链表的实现
在头文件中包含一些函数的声明。
因为每个节点都是一个结构体，所以每个节点都要存放一个结构体的指针，指向下一个节点。
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
SLTNode* BuyListBNode(SLTDataType x);
void PrintSList(SLTNode* phead);
void SLTPushBcak(SLTNode** pphead,SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPopback(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead,SLTDataType x);//头删
void SLTFind(SLTNode* pphead,SLTDataType x);//查找
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);3.1打印链表
打印链表首先要遍历链表，那么循环的条件就是走到空。所以我们创建一个临时变量cur代替头节点用来遍历，这样就可以不用动头节点，打印就是将节点中的数据打印出来，所以先将各个节点的数据打印出来，再指向下一个节点，需要注意的是next就是下一个节点的地址，所以将cur->next赋给cur就可以拿到下一个节点的地址了，拿到地址就可以继续访问下一个节点了。
void PrintSList(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3.2创建节点
这里malloc一个节点出来就行了，然后判断是否malloc成功，将需要的数据存进data中就行了，然后将next置为NULL，然后返回这个节点。
SLTNode* BuyListBNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*) malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}3.3尾插节点
这个函数的第一个参数是一个二级指针，目的是为了修改结构体，尾插节点首先需要创建一个节点，然后·判断一下当前链表是否为空，如果为空则将这个节点设置为头节点，所以解引用这个二级指针，拿到一级指针的地址，就可以修改了。如果不为空，则创建一个临时变量来保存头节点的地址，然后使用这个变量来遍历链表找到尾节点，循环的结束条件就是tail的next为空，因为尾节点的next是NULL，循环结束之后tail就走到了尾节点的位置，然后将新节点赋给tail的next即可。
void SLTPushBcak(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyListBNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}3.4头插节点
尾插节点还是需要创建一个节点，然后将这个节点的next指向这个头节点，但是头插之后头节点就是新插入的这个节点，所以需要使用二级指针，最后将新节点newnode赋给*pphead，这样头节点就更新了。
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuyListBNode(x);
newnode->next = *pphead;
*pphead = newnode;
}3.4尾删节点
尾删需要分很多种情况：
1.没有节点，这种情况就直接暴力检查，没有节点是删除不了的，直接assert即可。
2.一个节点，如果是一个节点的话，这个节点的next一定是NULL，所以使用if判断*pphead->next是否为NULL，如果是的话直接free掉这个节点然后置为空就行了。
3.如果是多个节点的话创建一个临时变量来遍历链表找到尾，需要注意的是，这个循环的结束条件是tail->next->next为空。下面这段代码就是错误的，因为free（tail）的本质是将tail指向的节点free，再将tail置为空相当于给tail赋值0x00000000，局部变量出了作用域就销毁了，但是前一个节点还是野指针，next虽然还是指向这个节点，但是这个节点已经free了。所以解决的方法就是找到tail的前一个节点，然后free掉tail->next，再置空。
正确的方法：
void SLTPopback(SLTNode** pphead)
{
assert(*pphead);
//一个节点
if ((*pphead)->next = NULL)
{
free(*pphead);
*pphead = NULL;
}
else//多个节点
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
3.5头删节点
头删也需要用到二级指针，然后暴力检查链表是否为空，不为空则创建一个变量newnode来保存头节点的next，然后free掉头节点，再将newnode赋给*pphead。
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}3.6查找节点
这个函数很简单，找到data就行，然后返回节点。
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x)
{
SLTNode* cur = pphead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}3.6在pos位置之前插入节点
pos的位置也需要分情况：
1.暴力检查
2.如果是头插，直接调用头插函数。
3.正常情况，创建一个结构体变量来遍历链表寻找pos节点，但是循环的结束条件设置成pre->next=pos最合适，因为我们需要保存pos的前一个节点，所以循环结束后pre就是pos的前一个节点，此时创建一个需要插入的节点newnode，将pre的next指向newnode，再将newnode的next指向pos，就完成链接了。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead,x);
}
else
{
SLTNode* pre = *pphead;
while (pre->next != pos)
{
pre = pre->next;
}
SLTNode* newnode = BuyListBNode(x);
pre->next = newnode;
newnode->next = pos;
}
}3.7在pos位置之后插入节点
首先暴力检查，再创建一个新节点newnode，插入需要注意的是以下这种写法是错误的，因为当我们将pos的next指向newnode的时候，就与后面的节点完全断开了，然后newnode的next又指向pos的next相当于形成了一个死循环。正确的方法应该是pos的next指向newnode的next，相当于先将newnode的next指向pos的后一个节点形成newnode的尾部链接，再将pos的next指向newnode完成newnode的头部链接。
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListBNode(x);
newnode->next = pos->next;
pos->next = newnode;
}3.8删除pos位置的节点
首先暴力检查，再判断pos是不是头删，正常删除就是创建一个变量遍历链表，pos的next为空作为循环的结束条件，循环结束之后pre就是pos的前一个节点，这个时候将pre的next指向pos的next也就是pos的下一个节点就行了，然后frre掉pos，这时候就不需要置空了。
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* pre = *pphead;
while (pre->next != pos)
{
pre = pre->next;
}
pre->next = pos->next;
free(pos);
}
}3.9删除pos位置之后的节点
首先暴力检查，然后再检查是否为尾节点。创建一个变量posNext保存pos的下一个节点，然后即将pos的下一个节点指向pos的下下个节点即可。然后free掉posNext。文章来源：https://www.toymoban.com/news/detail-753543.html
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);//检查是否是尾节点
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
}今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。文章来源地址https://www.toymoban.com/news/detail-753543.html
到了这里，关于数据结构-单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构]链表之单链表（详解）](https://imgs.yssmx.com/Uploads/2024/01/400368-1.png)
