🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）
目录
单链表和双向链表的比较
链表的打印
单链表
双向链表
初始化
双向链表
开辟空间，写入新数据
单链表
双向链表
尾部插入数据
单链表
双向链表
头部插入数据
单链表
双向链表
尾部删除数据
单链表
双向链表
头部删除数据
单链表
双向链表
查找
单链表
双向链表
在指定位置之前插入数据
单链表
在指定位置之后插入数据
单链表
双向链表
删除指定位置数据
单链表
双向链表
删除指定位置后的数据
单链表
销毁链表
单链表
双向链表
单链表和双向链表的比较
| 单向链表 | 双向链表 | |
| 指代不同 | 链表的链接方向是单向的，访问链表时时要顺序读取从头开始访问 | 每个数据的节点都有两个指针，即直接前驱和直接后驱 |
| 优点不同 | 单个节点创建方便，普通的线性内存通常在创建的时候就需要设定数据的大小，节点的访问方便，可以通过循环/递归的方法访问到任意数据 | 从双向链表中的任意一个节点开始，方便访问前驱节点和后继节点 |
| 缺点不同 | 增加/删除节点复杂，需要多分配一个指针存储空间 | 平均访问效率低于线性表，只能从头到尾遍历，只能找到后继，无法找到前驱（只能前进） |
链表的打印
单链表
//链表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}双向链表
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->dada);
pcur = pcur->next;
}
printf("\n");
}初始化
双向链表
//双向链表初始化
LTNode* LTInit()
{
//哨兵位设置为-1
LTNode* phead = SLTBuyNode(-1);
return phead;
}开辟空间，写入新数据
单链表
//开辟空间，写入新数据
SLTNode* SLTbuyNode(SLTDatatype x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
//先插入，后数据为空（后为空）
newnode->data = x;
newnode->next = NULL;
return newnode;//返回数据
}双向链表
//扩容，申请新节点
LTNode* SLTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//扩容
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
//数据赋值
newnode->dada = x;
//指向自己
newnode->next = newnode->prev = newnode;
return newnode;
}尾部插入数据
单链表
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{
//传的参数不为空
assert(pphead);
SLTNode*newnode = SLTbuyNode(x);
//链表为空，新节点作为phead
//*pphead是指向第一个节点的指针
if (*pphead == NULL)//头节点为空
{
*pphead = newnode;
return;
}
//链表不为空，找尾节点
//ptail作为尾节点
SLTNode* ptail = *pphead;
//先方向，后数据
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}双向链表
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = SLTBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}头部插入数据
单链表
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{
//传参有效
assert(pphead);
//开辟空间，新数据进入
SLTNode* newnode = SLTbuyNode(x);
//先方向，后数据
newnode->next = *pphead;
*pphead = newnode;
}双向链表
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = SLTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next = newnode;
phead->prev = newnode->prev->prev;
}尾部删除数据
单链表
//尾删
void SLTPopBack(SLTNode** pphead)
{
//保证传参数据有效
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
//有多个节点
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (prev->next)
{
prev = ptail;
ptail = ptail->next;
}
prev = NULL;
//销毁尾节点
free(ptail);
ptail = NULL;
}双向链表
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}头部删除数据
单链表
//头删
void SLTPopFront(SLTNode** pphead)
{
//保证传参有效
assert(pphead);
//保证链表有效
assert(*pphead);
//让第二个节点成为新的头
SLTNode* next = (*pphead)->next;
//把旧的头节点释放掉
free(*pphead);
*pphead = next;//第一个节点 = 原来第二个节点
}双向链表
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}查找
单链表
SLTNode* SLTFind(SLTNode** pphead, SLTDatatype x)
{
//保证传参有效
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}双向链表
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->dada == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}在指定位置之前插入数据
单链表
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{
//保证传参有效
assert(pphead);
//保证指定位置数据有效
assert(pos);
//链表也不能为空
assert(*pphead);
//新节点，开辟新空间
SLTNode* newnode = SLTbuyNode(x);
//pos刚好是头节点
if (newnode->next = *pphead)
{
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头节点的情况
SLTNode* prev = *pphead;
if (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}在指定位置之后插入数据
单链表
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDatatype x)
{
//保证目标数据有效
assert(pos);
//创建新节点
SLTNode* newnode = SLTbuyNode(x);
//先方向，后数据
newnode->next = pos->next;
pos->next = newnode;
}双向链表
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = SLTBuyNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next = newnode;
pos->next->prev = newnode;
}删除指定位置数据
单链表
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
//保证传的参数有效
assert(pphead);
//保证单链表有效
assert(*pphead);
//保证目标数据有效
assert(pos);
//pos刚好是头节点，没有前驱节点
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
//pos不是头节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//释放
prev->next = pos->next;
free(pos);
pos = NULL;
}双向链表
//删除pos位置的数据
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* del = pos;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(del);
del = NULL;
}删除指定位置后的数据
单链表
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
//保证目标数据有效
assert(pos);
//pos->next数据有效
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
//释放
free(del);
del = NULL;
}销毁链表
单链表
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
//保证传的参数有效
assert(pphead);
//保证链表有效
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}双向链表
//销毁
void LTDesTroy(LTNode* phead)
{
//哨兵位不能为空
assert(phead);
LTNode* pcur = phead->next;
while(pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:“成为正确答案的第一步，相信自己会是正确答案”。文章来源：https://www.toymoban.com/news/detail-854337.html
我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！
好了划走吧。文章来源地址https://www.toymoban.com/news/detail-854337.html
到了这里，关于【数据结构】-- 单链表 vs 双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[C语言][数据结构][链表] 单链表的从零实现!](https://imgs.yssmx.com/Uploads/2024/04/847183-1.png)
