?? ?各位大佬们好！很荣幸能够得到您的访问，让我们一起在编程道路上任重道远！?
??博客专栏：【数据结构初阶】?
? 本篇内容简介：数据结构初阶中线性表之单链表的实现！
? 了解作者：励志成为一名编程大牛的学子，目前正在升大二的编程小白。
?励志术语：编程道路的乏味，让我们一起学习变得有趣！
文章目录
? 顺序表的问题（缺陷）及思考
问题：
1. 中间 / 头部的插入删除，时间复杂度为O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。
例如：当前容量为100，满了以后增容道200，我们再继续插入5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上的问题呢？下面给出链表的结构来看看。
? 链表
? 链表的概念及结构
概念：
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
形象得可以用火车的形式表示：
?现实中，数据结构中：
?注意：
? ? ? ? 1. 从上面的图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定是连续的。
? ? ? ? 2. 现实的结点一般都是从堆上申请出来的。
? ? ? ? 3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能? ? ? ? ? ? ? 不连续。?
假设在32位系统上，结点中值域为int类型，则一个结点的大小为8个字节，则也可能有下述链表：
??链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
? 1. 单向或者双向
?? 2. 带头或者不带头
?? 3. 循环或者非循环
?虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：
?1. 无头单向非循环链表：结构简单，一般不会单独用来存放数据，实际中更多是作为其他数据结构的子结构，如：哈希桶，图的邻接表等等，另外这种结构在 笔试面试?出现很多。
?2. 带头双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现起来反而更见简单，后面我们代码实现就知道了。
??链表的实现
（无头+单向+非循环链表的 增删查改 的实现）
? 1. 单链表的结构
①. 存放数据。
②. 存放下一个结点的地址。
代码实现：
typedef int SLTDataType;
//结构
typedef struct SListNode
{
SLTDataType Data;
struct SListNode* next;
}SListNode;? 2. 单链表的打印
//单链表的打印
void SListPrint(SListNode* phead);在这里我们一定要结合图形写代码：
注意：这里我们不能加上断言（因为链表可能为空）。
?代码实现：
//单链表的打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->Data);
cur = cur->next;//cur往后走
}
printf("NULL\n");
}测试打印结果：（此时链表为空，打印NULL）
? 3. 单链表的结点动态申请
//单链表结点的动态申请 返回newnode
SListNode* BuySListNode(SLTDataType x);申请结点的代码，比较简单，没有什么值得注意的，我们直接看代码：
//单链表结点的动态申请 返回newnode
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//直接结束
}
else
{
//初始化结点
newnode->Data = x;
newnode->next = NULL;
return newnode;
}
}? 4. 单链表的尾插
//单链表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x);注意：
1. 这个我们为什么要用二级指针呢？
? ?因为我们要改变这个头结点的位置，到时候我们是转递一个指针过来的，而改变指针的方式就是用，指针的指针才能改变。
?
比如： int a=10;
? ? ? ? ? ? int b=20;
? ? ? ? ? ? int* p1=&a;
? ? ? ? ? ? int* p2=&b;
? ? ? ? ? ? Swap(&p1,&p2);
?
? ? ? ? ? ? void Swap(int** p1,int** p2)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ?int* tmp=*p1;
? ? ? ? ? ? ? ? ? ?*p1=*p2;//解引用
? ? ? ? ? ? ? ? ? ?*p2=tmp;
? ? ? ? ? ? }
这样的代码才能改变指针所指向的内容。
?
2. 需要加一个断言（assert）：
? 因为plist的地址不可能为空，即使plist指向的内容为空，地址也不可能为空。
我们依旧画图写代码：
代码实现：
//单链表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);//申请一个结点
//1.为空
if (*pphead == NULL)
{
*pphead = newnode;
}
//2.不为空
else
{
SListNode* prev = *pphead;
while (prev->next != NULL)
{
prev = prev->next;//往后走
}
prev->next = newnode;
}
}测试尾插结果：（成功尾插4个数据）
? 5. 单链表的头插
//单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x);头插代码没有什么好注意的，无论是链表为空还是不为空，此代码都不需要特殊判断：
?代码实现：
//单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
//申请结点
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}测试头插结果：（插入三个数据成功）
? 6. 单链表的销毁
//单链表的销毁
void SListDestory(SListNode** pphead);怎么销毁呢？我们要看图：
?代码实现：
//单链表的销毁
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur != NULL)
{
//建cur后一个结点
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}? 7. 单链表的头删
//单链表的头删
void SListPopFront(SListNode** pphead);注意：（有两种情况）
1. 当链表为空时，不做删除处理，直接返回或者直接暴力判断。
2. 当链表不为空时，我们按图写代码：
代码实现：
//单链表的头删
void SListPopFront(SListNode** pphead)
{
assert(pphead);
//判断链表是否为空
if (*pphead == NULL)
{
return;
}
//或者 assert(*pphead!=NULL)
SListNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}测试头删：（成功头删）
?? 8. 单链表的尾删
//单链表的尾删
void SListPopBack(SListNode** pphead);?尾删我们分为三种情况：
1. 没有结点，我们不做出来，直接返回，或者暴力检查。
2. 只有一个结点，释放结点，再置为空。
3. 有多个结点，我们这里看图：
?代码实现：
//单链表的尾删
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}
//只有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个结点
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
//往后走
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}测试尾删结果：（成功尾删）
?? 9. 单链表的查找
//单链表的查找
SListNode* SListFind(SListNode* phead, SLTDataType x)单链表的查找比较简单，我们直接看代码即可：
//单链表的查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur != NULL)
{
//往后遍历
if (cur->Data == x)
{
return cur;
}
cur = cur->next;
}
//找不到
return NULL;
}测试查找结果：（我们这里找单链表中的，数字6）
? 10. 单链表在pos之前插入
//单链表在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);1. 如果pos在第一个结点，相当于头插。
2. 如果pos在其他位置，我们依旧看图：
代码实现：
//单链表在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);//断言pos不能为空
if (pos == *pphead)
{
//调用头插
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//判断pos是否传错 如果传错 prev==NULL
assert(prev);
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}测试在pos之前插入结果：（在1的前面插入10，成功）
? 11. 单链表在pos之后插入
//单链表在pos之后插入
void SListInsertAfert(SListNode* pos, SLTDataType x);在pos之后插入，我们要注意一点：
先时newnode->next=pos->next;
再使pos->next=newnode;
如果顺序不是相反的话，会照成newnode自己指向自己。
代码实现：
//单链表在pos之后插入
void SListInsertAfert(SListNode* pos, SLTDataType x)
{
assert(pos);
//申请结点
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}测试在pos之后插入：（插入50成功）
?? 12. 删除pos的位置
//单链表删除pos的位置
void SListErase(SListNode** pphead, SListNode* pos);注意：
1. 如果pos的位置是第一个结点，那就调用头删。
2. 其他位置，我们画图见真晓：
?代码实现：
//单链表删除pos的位置
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
//调用头删
SListPopFront(pphead);
}
else
{
//其他位置
SListNode* prev = *pphead;
while (prev->next != pos)
{
//往后走
prev = prev->next;
//判断pos是否在链表中
assert(prev);
}
prev->next = pos->next;
free(pos);
//pos = NULL;//这里置为空，没有用，形参是实参的拷贝
}
}测试删除pos位置的数据：
?? 13. 删除pos之后的位置
//单链表删除pos之后的位置
void SListEraseAfter(SListNode* pos);1. 当pos之后的位置为空时，不做处理，直接返回。
2. 当pos在其他位置时，看图得真相：
?代码实现：
//单链表删除pos之后的位置
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)//只有一个结点
{
return;
}
else
{
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
}测试删除pos之后的结果：（成功删除pos=1之后的位置）
? 单链表实现所有源代码
?? SList.h 头文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType Data;
struct SListNode* next;
}SListNode;
//单链表的打印
void SListPrint(SListNode* phead);
//单链表结点的动态申请 返回newnode
SListNode* BuySListNode(SLTDataType x);
//单链表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x);
//单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x);
//单链表的销毁
void SListDestory(SListNode** pphead);
//单链表的头删
void SListPopFront(SListNode** pphead);
//单链表的尾删
void SListPopBack(SListNode** pphead);
//单链表的查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
//单链表在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
//单链表在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
//单链表删除pos的位置
void SListErase(SListNode** pphead, SListNode* pos);
//单链表删除pos之后的位置
void SListEraseAfter(SListNode* pos);? SList.c 源文件
#include"SList.h"
//单链表的打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->Data);
cur = cur->next;//cur往后走
}
printf("NULL\n");
}
//单链表结点的动态申请 返回newnode
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//直接结束
}
else
{
//初始化结点
newnode->Data = x;
newnode->next = NULL;
return newnode;
}
}
//单链表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
assert(pphead);
SListNode* newnode = BuySListNode(x);//申请一个结点
//1.为空
if (*pphead == NULL)
{
*pphead = newnode;
}
//2.不为空
else
{
SListNode* prev = *pphead;
while (prev->next != NULL)
{
prev = prev->next;//往后走
}
prev->next = newnode;
}
}
//单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);
//申请结点
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//单链表的销毁
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur != NULL)
{
//建cur后一个结点
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
//单链表的头删
void SListPopFront(SListNode** pphead)
{
assert(pphead);
//判断链表是否为空
if (*pphead == NULL)
{
return;
}
//或者 assert(*pphead!=NULL)
SListNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
//单链表的尾删
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}
//只有一个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//多个结点
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
//往后走
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//单链表的查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (cur != NULL)
{
//往后遍历
if (cur->Data == x)
{
return cur;
}
cur = cur->next;
}
//找不到
return NULL;
}
//单链表在pos之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);//断言pos不能为空
if (pos == *pphead)
{
//调用头插
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
//判断pos是否传错 如果传错 prev==NULL
assert(prev);
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//单链表在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
//申请结点
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//单链表删除pos的位置
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
//调用头删
SListPopFront(pphead);
}
else
{
//其他位置
SListNode* prev = *pphead;
while (prev->next != pos)
{
//往后走
prev = prev->next;
//判断pos是否在链表中
assert(prev);
}
prev->next = pos->next;
free(pos);
//pos = NULL;//这里置为空，没有用，形参是实参的拷贝
}
}
//单链表删除pos之后的位置
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)//只有一个结点
{
return;
}
else
{
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
}? Test.c 源文件
#include"SList.h"
void test1()
{
SListNode* plist = NULL;
//测试尾插
SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
//测试头插
SListPushFront(&plist, 5);
SListPushFront(&plist, 6);
SListPushFront(&plist, 7);
SListPrint(plist);
//测试头删
SListPopFront(&plist);
SListPrint(plist);
//测试尾删
SListPopBack(&plist);
SListPrint(plist);
//测试查找
SListNode* pos = SListFind(plist, 1);
if (pos)
{
/*printf("找到了\n");*/
//测试在pos之前插入数据
SListInsert(&plist, pos, 10);
//测试在pos之后插入数据
SListInsertAfter(pos, 50);
SListPrint(plist);
//测试删除pos位置
/*SListErase(&plist, pos);
SListPrint(plist);*/
//删除pos之后的位置
SListEraseAfter(pos);
SListPrint(plist);
}
SListDestory(&plist);
}
int main()
{
test1();
return 0;
}? 结束语
各位大佬好，今天这个无头非循环单向链表就实现到这里了，希望这篇接近万字的实现单链表的博客能够，使各位大佬温习或者更加深刻的去理解单链表的实现过程。都看到这了，给个三联吧！！！
