前言：大家好😍，本文主要介绍了数据结构——双向链表dlist
一 双向链表定义
双向链表（Doubly Linked List）是一种常见的线性数据结构，与单链表不同，双向链表的每个节点包含两个指针：一个指向前一个节点，一个指向后一个节点。这种结构使得双向链表支持从两个方向遍历，同时在插入和删除操作中更加灵活和高效。
1. 双向链表的节点结构
双向链表的每个节点包含三个部分：
数据域：存储数据元素。
前驱指针（
prev）：指向当前节点的前一个节点。后继指针（
next）：指向当前节点的后一个节点。
二 双向链表操作
2.1 定义
//定义了双向链表的结构体
typedef int ELEM_TYPE;
struct DNode
{
ELEM_TYPE data; //数据域
struct DNode* next; //下一个结点地址
struct DNode* prior;//上一个
};
typedef struct DNode DNode;
typedef struct DNode* PDNode;2.2 初始化
void Init_Double_List(struct DNode* plist) //双向链表 第一种struct DNode*
{
assert(plist != NULL);
plist->next = NULL;
plist->prior = NULL;
}
2.3 插入
2.3.1 头插
bool Insert_head(DNode* plist, ELEM_TYPE val)//二DNode*
{
assert(plist != NULL);
if (NULL == plist)
{
exit(EXIT_FAILURE);
}
DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
if (NULL == pnewnode)
exit(1);
pnewnode->data = val;
//插在辅助接点后面
pnewnode->next = plist->next;
pnewnode->prior = plist;
if (!Is_Empty(plist))
{
pnewnode->next->prior = pnewnode;
//这个也可以plist->next->prior = pnewnode;
}
plist->next = pnewnode;
return true;
}2.3.2 尾插
bool Insert_tail(PDNode plist, ELEM_TYPE val)//三PDNode
{
assert(NULL !=plist );
if (NULL == plist)
{
exit(EXIT_FAILURE);
}
//购买新节点
DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
if (NULL == pnewnode)
exit(1);
pnewnode->data = val;
//找到合适的待插入位置需要让一个临时指针p指向尾结点
DNode* p = plist;
while (p->next != NULL)
p = p->next;
//插入三行代码：只有三个指针域需要修改231
pnewnode->next = p->next;//null
pnewnode->prior = p;
p->next = pnewnode;
return true;
}2.3.3 按位置插
bool Insert_pos(DNode* plist, ELEM_TYPE val, int pos)
{
assert(NULL != plist);
if (NULL == plist)
{
exit(EXIT_FAILURE);
}
//对pos合法性断言
assert(pos >= 0 && pos <= Get_length(plist));
//对pos判断 //pos=0 直接return头插函数
//pos=length return尾插函数
if (pos == 0)
{
return Insert_head(plist, val);
}
else if(pos==Get_length(plist))
{
return Insert_tail(plist, val);
}
//剩下的pos都是合法且是中间位置，需要修改四个指针域
//找到合适的插入位置让p指向待插入位置的上一个结点
else
{
DNode* pnewnode = (DNode*)malloc(sizeof(DNode));
if (NULL == pnewnode)
exit(1);
pnewnode->data = val;
DNode* p = plist;
while (p->next != NULL)
p = p->next;
//插入四行代码 因为有四个指针域要修改
pnewnode->next = p->next;
pnewnode->prior = p;
pnewnode->next->prior = pnewnode;
p->next = pnewnode;
return true;
}
}2.4 删除
2.4.1 头删
bool Del_head(DNode* plist)
{
//判空
assert(NULL != plist);
if (NULL == plist)
{
exit(EXIT_FAILURE);
}
//判断链表是否为空
if (Is_Empty(plist))
return false;
//申请俩个临时指针p和q，分别指向删除结点前驱和删除结点本身
DNode* p = plist;//可以不要这行
DNode* q = p->next;
//区分情况 若是只有唯一一个有效结点 则只要需要修改一个指针域
// >1则修改俩个指针域
if (Get_length(plist)>1)
{
q->next->prior = p;
}
//跨越指向+释放
p->next = q->next;
free(q);
q = NULL;
return true;
}2.4.2 尾删
bool Del_tail(DNode* plist)
{
assert(NULL != plist);
if (NULL == plist)
{
exit(EXIT_FAILURE);
}
//对双向链表判空
if (Is_Empty(plist))
return false;
//辅助接点后有结点就可以尾删
//申请俩个临时指针p和q，分别指向删除结点前驱和删除结点本身
DNode* p = plist;
while (p->next->next != NULL)
p = p->next;
DNode* q = p->next;
//跨越指向+释放
p->next = q->next;
free(q);
q = NULL;
return true;
}2.4.3 按位置删
2.5 其余操作
//9.判空
bool Is_Empty(DNode* plist)
{
return plist->next == NULL;
}
//10获取有效值长度
int Get_length(DNode* plist)
{
int count = 0;
DNode* p = plist->next;
for (; p != NULL;p=p->next)
{
count++;
}
return count;
}
//11.清空
void Clear(DNode* plist)
{
Destroy1(plist);
}
//12.销毁1(需要辅助节点参与进来)
void Destroy1(DNode* plist)
{
//无限头删
while (plist->next != NULL)
{
Del_head(plist);
}
}
//13.销毁2(不需要辅助节点参与进来)相当于单链表的销毁
void Destroy2(DNode* plist)
{
//不借助头结点
//要用俩个指针pq去搭配 销毁所有结点
//0.assert head
//1.申请指针p，让其指向第一个有效结点
DNode* p =plist->next;//p有可能为NULL， 有可能不空
//2.申请指针q，先不给q赋值
DNode* q = NULL; //因为p有可能是NULL，所以不能现在直接把p->next给到q
//3.反复通过p和q打配合，去销毁后续节点
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
//4.节点全部销毁完毕，别忘了把辅助节点的指针域置空
plist->next = NULL;//这一行代码可以帮助，下一次启用的时候，辅助节点不用初始化了
}
//14.打印
void Show(DNode* plist)
{
DNode* p = plist->next;
for (; p != NULL;p=p->next)
{
printf("%d", p->data);
}
printf("\n");
}