数据结构（初阶）（四）----双向链表

双向链表
- 初始化
- 尾插
- 打印
- 尾删
- 头插
- 头删
- 查找
- 在pos位置之后插入数据
- 在pos位置之前插入数据
- 删除pos结点
- 销毁链表

双向链表

链表分类:8种（2*2*2）

带头，不带头

单向，双向

循环，不循环

最常用的是两种：

单链表：不带头，单向，不循环链表

双链表：带头，双向，循环链表

带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥占位置，类似于“放哨的”。

在这里插入图片描述

双向链表由结点组成：结点中包含数据，指向下一个结点的指针以及指向前一个结点的指针

struct ListNode
{int data;struct ListNode* next;struct ListNode* prev;
}

初始化

单链表为空链表时，那么链表中没有节点，plist就指向NULL

双向链表为空时，此时链表只有一个头结点（哨兵位），如果没有哨兵位，那么它就不能被称为双向链表，于是我们在对双向链表初始化时，一定要创建一个哨兵位。

思考：在初始化时，是否可以将哨兵位的prev，next指针初始化为NULL？

在这里插入图片描述

答案是绝对不可以。

应该将哨兵位的prev，next指针都指向它自己。

在这里插入图片描述

#include"List.h"
//申请结点
LTNode* LTBuyNode(x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->prev = newnode->next = newnode;return newnode;
}
//以参数的形式返回哨兵位
//创建链表,创建一个哨兵位
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}//以返回值的形式返回哨兵位，推荐使用
//创建链表,创建一个哨兵位
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

调用的区别

参数形式的调用

List是指向节点的指针，节点指针，它存储的内容是结点的地址
//LTNode* plist = NULL;
&pList，是取指向节点的指针的地址，这样就可以修改指向节点的指针的地址
//LTInit(&plist);

返回值形式的调用

//在初始化中，创建节点，并返回指向节点的指针（推荐使用，原因末尾会讲）
LTNode* List = LTInit();

尾插

首先我们需要知道：哨兵位结点不能被删除，结点的地址也不能发生改变
哨兵位不能为空，否则链表无效，再操作就没有用了
在这里插入图片描述

在这里插入图片描述

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

如果只有哨兵位，代码是否成立？

成立！
在这里插入图片描述

注意：

在这里插入图片描述

不能完全交换

如果交换，d3的地址丢失，代码会出问题

如果非要交换，可以先将d3的地址存储起来，保证之后可以正常使用

打印

哨兵位不是有效结点，直接从哨兵位的下一个结点打印，直到循环到哨兵位结束
在这里插入图片描述

//打印链表
void LTPrint(LTNode* phead)
{//哨兵位不再打印LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

尾删

1，首先我们在进行删除操作时，需要保证链表有效且不能为空（即只有一个哨兵位时）。
在这里插入图片描述

2，先找到最后一个结点位置，即phead->next;

将该节点保存下来，以便后续使用。

3，将最后一个结点的prev节点与哨兵位结点联系起来，使之成为新的最后结点

4，释放del节点，并置空。

//尾删
void LTPopBack(LTNode* phead)
{//assert(phead && phead->prav != phead);assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

头插

插入到第一个有效结点之前，即哨兵位后面

操作和尾插极其相似，不再赘述。

在这里插入图片描述

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{//链表要有效assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;
}

头删

和尾删非常相似。

在这里插入图片描述

//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

查找

遍历双向链表

注意，循环条件是pcur != phead，因为双向链表是循环链表，如果不加该条件，循环将会一直成立，这点与单链表不同。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur->next;}return NULL;
}

在pos位置之后插入数据

在这里插入图片描述

先修改新结点，不会影响原链表的结点

//在指定位置pos之后插入数据
void LTInsertBack(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

在pos位置之前插入数据

与在之后插入数据相似。

不再详细写。

删除pos结点

//删除pos结点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead，但是此处并没有传phead，无法校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

要将pos结点的空间释放并置空，为什么在这里不传二级指针？

在理论上参数是要传二级指针的，因为我们需要让形参的改变影响实参，

没有这样做的原因是为了保持接口的一致性。

在双向链表的方法中传的都是一级指针，可以大大降低使用方法的记忆成本。

正确解决方法是，在测试文件中调用方法后，将find置空

这就解释了为什么我们在最开始对双向链表初始化时，要以返回值的形式返回哨兵位。

销毁链表

与删除不同的是，销毁；链表要删除哨兵位。

此处依旧传一级指针，原因是保持接口一致性，统一参数，解决方法与上面一样。

在这里插入图片描述

//销毁链表
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur已经循环到phead，即pcur指向phead，phead也要销毁free(phead);phead = NULL;
}

调试
在这里插入图片描述

跳出函数后，pcur销毁，所以在函数内部不置空也没有问题

但是调用时，plist没有置空，需要手动置空

不同点	顺序表	链表（单链表）
存储空间上	物理上⼀定连续	逻辑上连续，但物理上不⼀定连续
随机访问	⽀持：O(1)	不⽀持：O(N)
任意位置插⼊或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插⼊	动态顺序表，空间不够时需要扩容和空间浪费	动态顺序表，空间不够时需要扩容和空间浪费
应⽤场景	元素⾼效存储+频繁访问	任意位置⾼效插⼊和删除