双向链表（带头双向循环链表）的实现
前言：前面实现的单向链表，全称是不带头单向不循环链表。这里实现带头双向不循环链表，比单向链表好实现一点。
目录
test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！
链表的分类
将是否带头，单向还是双向，是否循环，随机组合一共有八种类型，只要会写不带头单向不循环链表和带头双向循环链表这两个链表，其他的链表实现起来就简单多了。
单向链表与双向链表的比较：
| 单向链表 | 双向链表 | |
| 是否带头 | 不带头 | 带头（有哨兵位） |
| 单向还是双向 | 单向 | 双向 |
| 是否循环 | 不循环 | 循环 |
逻辑图解比较：
双向链表的节点的定义：
typedef int LTTypeData;
typedef struct ListNode
{
LTTypeData data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;prev指向前一个节点
next指向下一个节点
data存储数据
为什么tydef一个新的数据类型是为了方便以后修改存储的数据类型。
多文件实现：
| 文件名称 | 负责的功能 |
| List.h | 链表的定义，需要用到库里的头文件的包含，链表需要实现函数的声明。 |
| List.c | 链表函数的实现 |
| test.c | 测试接口（这里大家可以自己测，自己写） |
这里的建议是每写一个接口就测试一个接口，省得全写完在测试，有一堆麻烦，还没开始解决麻烦，就先把自己的心态搞崩了。
List.h来看一下需要实现的函数接口：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTTypeData;
typedef struct ListNode
{
LTTypeData data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);List.c的各个函数的实现：
因为会频繁的创建新的节点，这里直接将创建新的节点分装成一个函数。
创建节点的函数：
LTNode* LTBuyNode(LTTypeData x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}注意这里创建出的节点的next和prev指针都指向自己。
图解：
链表的初始化：
void LTInite(LTNode** pphead)
{
assert(pphead);//链表不能无效
*pphead = LTBuyNode(-1);
}这里*pphead指向的节点为头结点（哨兵位），哨兵位的数据为无用的数据。
尾插：
void LTPushBack(LTNode* phead, LTTypeData x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}为什么参数是一级指针而不是二级指针？
在单链表时尾插需要传二级指针是因为需要改变指针变量phead的值；而在双向链表中有哨兵位，改变的是哨兵位的prev和next指针的值，所以不需要传二级指针。
注意修改顺序：先改newnode的prev和next，再改原链表的尾节点的next（指向新的节点）和头节点的prev（指向新的节点）
图解：
注意这里2和3不能调换顺序，如果调换顺序，那么prev->next就找不到原来链表的尾节点了。
头插：
void LTPushFront(LTNode* phead, LTTypeData x)
{
assert(phead);//防止链表无效
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}注意：还是顺序问题：最后两句不能调换顺序，否则，phead->next就指向的不是原链表的第一个节点，就找不到原链表的第一个节点了。
打印链表：
void LTPrint(LTNode* phead)
{
assert(phead);//防止链表无效
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}这里注意循环结束的标志：
当pcur指向哨兵位时，循环结束。
看一下打印效果：
#include "List.h"
void test1()
{
LTNode* plist = NULL;
LTInite(&plist);
LTPushBack(plist, 1);
LTPrint(plist);
LTPushBack(plist, 2);
LTPrint(plist);
LTPushBack(plist, 3);
LTPrint(plist);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
}
int main()
{
test1();
}效果展示：
尾删：
void LTPopBack(LTNode* phead)
{
//链表不能为空，不能无效
assert(phead && phead->next != NULL);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}这里需要修改的链表的地方：尾节点的前一个节点的next和头节点的prev
步骤图解：
注意：这里需要保存下尾节点的地址，防止到最后释放的时候找不到。
头删：
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != NULL);
LTNode* del = phead->next;
del->next->prev = del->prev;
phead->next = del->next;
free(del);
del = NULL;
}跟尾删一样，需要注意的一点就是，需要创建一个新的变量（del）存储需要删除的节点的地址。
查找：
LTNode* LTFind(LTNode* phead, LTTypeData x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}注意下循环结束的条件：跟上面的打印函数一样，需要遍历一遍链表。
返回值：如果没找到返回NULL，找到了就返回那个节点的地址。
插入（在指定位置之后插入）：
void LTInsert(LTNode* pos, LTTypeData x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}注意：最后两句的顺序不能交换。这里的原因上面的头插尾插的原因一样，若交换就找不到pos指向的节点的下一个节点。
删除指定位置的数据：
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
这里没啥好注意的 。
销毁链表：
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
LTNode* next = phead->next;
while (pcur!=phead)
{
next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
注意：这里用到前后指针：防止释放完一个节点找不到之后的节点。
最后哨兵位释放，因为这里传的是一级指针不会修改test.c 文件中的phead的值，所以调用完该函数后，需要手动的将test.c中的phNULL.
那么,这里为什么不传二级指针呢？
保证接口的一致性，所以传的二级指针。
实现双链表的全部源码：
List.h：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTTypeData;
typedef struct ListNode
{
LTTypeData data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);List.c：
#include "List.h"
LTNode* LTBuyNode(LTTypeData x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}
void LTInite(LTNode** pphead)
{
assert(pphead);
*pphead = LTBuyNode(-1);
}
void LTPushBack(LTNode* phead, LTTypeData x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void LTPushFront(LTNode* phead, LTTypeData x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != NULL);
LTNode* del = phead->next;
del->next->prev = del->prev;
phead->next = del->next;
free(del);
del = NULL;
}
void LTPopBack(LTNode* phead)
{
assert(phead && phead->next != NULL);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
LTNode* LTFind(LTNode* phead, LTTypeData x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTTypeData x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
LTNode* next = phead->next;
while (pcur!=phead)
{
next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！
#include "List.h"
void test1()
{
LTNode* plist = NULL;
LTInite(&plist);
LTPushBack(plist, 1);
LTPrint(plist);
LTPushBack(plist, 2);
LTPrint(plist);
LTPushBack(plist, 3);
LTPrint(plist);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTNode* find = LTFind(plist, 4);
//if (find == NULL)
//printf("没找到\n");
//else
//printf("找到了\n");
//LTInsert(find, 5);
//LTPrint(plist);
//LTErase(find);
//LTPrint(plist);
//LTDestroy(plist);
//plist = NULL;
}
int main()
{
test1();
return 0;
}结语：
继单链表后的又一个数据结构的实现。
cheers！
原文地址：https://blog.csdn.net/2402_82658387/article/details/137839290
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！