【数据结构】二、线性表：3.双链表的定义及其基本操作（初始化、头插法尾插法建表、插入、遍历查找、删除、判空等）

3.双链表

单链表（Singly Linked List）和双链表（Doubly Linked List）是两种常见的链表数据结构，它们在节点之间的连接方式上有所区别。

• 单链表

1. 单链表的每个节点包含两个部分：数据域和指针域。
2. 数据域存储节点的值或数据。
3. 指针域存储指向下一个节点的指针，即单链表的指针指向下一个节点。
4. 单链表只能从头节点开始顺序访问，通过指针域进行节点之间的连接。
5. 单链表只能单向遍历，即只能从头节点开始，沿着指针域逐个访问下一个节点。
6. 无法逆向检索，有时候不太方便

• 双链表

1. 双链表的每个节点包含三个部分：数据域、指向前一个节点的指针前驱prior和指向下一个节点的指针后继next。
2. 数据域存储节点的值或数据。
3. 前驱指针指向前一个节点，后继指针指向下一个节点。
4. 双链表可以双向遍历，既能从头节点顺序遍历，也可以从尾节点逆序遍历。
5. 双链表相较于单链表需要额外存储指向前一个节点的指针，因此会在空间上占用更多的内存。
6. 可进可退，存储密度更低一点

单链表和双链表的选择取决于需要解决的问题和应用场景。对于只需要顺序遍历或仅从头部开始操作的情况，单链表可能是更简洁和高效的选择。但对于需要在两个方向上遍历或在任意位置插入或删除节点的情况，双链表就更有优势了。

typedef struct DNode{
    Elemtype data;  //数据域
    struct DNode *prior,*next;  //前驱和后继指针
}DNode, *DLinkList;

3.1初始化

双链表与单链表一样，为了操作方便也可以加入头结点，那么初始化双链表其实就是定义一个头结点，然后将指针域置空。

typedef struct DNode{//定义双链表结点类型
Elemtype data;//数据域
struct DNode *prior, *next;//前驱和后继指针
}DNode, *DLinkList;


//初始换双链表
bool InitDLinkList(DLinkList &L){
L = (DNode *) malloc(sizeof(DNode));//分配一个头结点
if(L == NULL)//内存不足，分配失败
return false;
L->prior = NULL;//头结点的前驱prior永远指向NULL
L->next = NULL;//头结点之后暂时还没有结点
return true;
}
void testDLinkList(){
DLinkList L; //初始化双链表
InitDLinkList(L);
//后续代码......
}

判断双链表是否为空

//判断双链表是否为空（带头结点）
bool Empty(DLinkList L){
if(L->next == NULL)
return true;
else
return false;
}

3.2插入

在双链表中插入节点需要更新前驱节点和后继节点的指针连接：

1. 首先，创建一个新节点，并设置它的数据值。
2. 找到要插入位置的前驱节点。
3. 将新节点的前驱指针指向前驱节点。
4. 将新节点的后继指针指向前驱节点的后继节点。
5. 更新前驱节点的后继指针指向新节点。
6. 如果新节点的后继节点非空，将后继节点的前驱指针指向新节点。

在p结点之后插入s结点：

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
if (p == NULL || s == NULL) //非法参数
return false;
s->next = p->next;        //(1)
if(p->next != NULL){//如果p结点有后继结点才可以进去这个后继节点，如果p是最后一个结点，则后继为NULL
p->next->prior = s;  //(2)
}
s->prior = p;  //(3)
p->next = s;      //(4)
return true;//插入成功
}

注意：要注意代码中结点前驱后继的调整顺序，防止出现自己指向自己的情况。

3.3删除

1. 首先，找到要删除的节点。
2. 如果要删除的节点是头节点，将头节点指针指向下一个节点，并更新下一个节点的前驱指针为 nullptr。
3. 如果要删除的节点是尾节点，将前一个节点的后继指针设为 nullptr，并更新尾节点指针为前一个节点。
4. 如果要删除的节点既不是头节点也不是尾节点，将前一个节点的后继指针指向要删除节点的后一个节点，将后一个节点的前驱指针指向要删除节点的前一个节点。
5. 释放要删除的节点的内存空间。

3.3.1删除p结点的后继结点

//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
if(p == NULL)
return false;
DNode *q = p->next;//找到p的后继结点q
if(q == NULL)
return false;//p没有后继结点
p->next = q->next;//使原本指向q的p的后继指向q的后继
if(q->next != NULL)//q结点不是最后一个结点
q->next->prior = p;
free(q);//释放结点空间
return true;//删除成功
}

3.3.2销毁一个双链表

//销毁一个双链表
void DestoryList(DLinkList &L){
//循环释放各个数据结点
while(L->next != NULL){//判断头结点是否有后继结点，直到头结点后再无其他结点结束循环
DeleteNextDNode(L);//删除L结点的后继结点
}
free(L);//释放头结点
L = NULL;//头指针指向NULL
}

3.4遍历

3.4.1后向遍历

while(p != NULL){
//对结点p做相应处理，如打印
p = p->next;
}

这里的相应操作，

• 如果是按位查找，那么就在这里累加一个计数器，当计数器到查找的值就return。
• 如果是按值查找，那么就在这里做一个数据对比。

3.4.2前向遍历

while(p != NULL){
//对结点p做相应处理
p = p->prior;
}

3.4.3前向遍历(跳过头结点)

while(p->prior != NULL){  //当前驱为NULL时，此时遍历到第一个结点，退出循环，跳过了头结点。
//对结点p做相应处理
p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现，时间复杂度为O(n)。

原文地址：https://blog.csdn.net/weixin_51350847/article/details/136462486

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！