数据结构——双向链表dlist

前言：大家好😍，本文主要介绍了数据结构——双向链表dlist

一 双向链表定义

1. 双向链表的节点结构

 二 双向链表操作

 2.1 定义

2.2 初始化

2.3 插入

2.3.1 头插

2.3.2 尾插

2.3.3 按位置插

2.4 删除

2.4.1 头删

2.4.2 尾删

2.4.3 按位置删

2.5 其余操作

2.6 主函数测试

---

一 双向链表定义

双向链表（Doubly Linked List）是一种常见的线性数据结构，与单链表不同，双向链表的每个节点包含两个指针：一个指向前一个节点，一个指向后一个节点。这种结构使得双向链表支持从两个方向遍历，同时在插入和删除操作中更加灵活和高效。 

1. 双向链表的节点结构

双向链表的每个节点包含三个部分：

1. 数据域：存储数据元素。

2. 前驱指针（prev）：指向当前节点的前一个节点。

3. 后继指针（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;//nullpnewnode->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");
}

2.6 主函数测试