"5.双链表的简介.md"
在数据结构中，链表是一种重要的线性数据结构，其中的数据元素不是在物理位置上相邻，而是通过指针连接。双链表是链表的一种变体，它在每个节点中不仅包含指向下一个节点的指针，还包含一个指向前一个节点的指针，这使得双向操作变得可能。
### 单链表与双链表的比较
#### 单链表
单链表每个节点只包含一个指针，通常称为`next`指针，用于指向序列中的下一个节点。由于只有一个方向的链接，单链表的插入和删除操作相对简单，但其主要缺点是无法直接从前一个节点访问当前节点，只能从头节点开始按顺序查找，这在需要反向遍历或随机访问时效率较低。
#### 双链表
双链表的每个节点包含两个指针，一个`next`指针指向下一个节点，另一个`prior`指针指向前一个节点。这种设计使得双链表在进行插入和删除操作时更加灵活，因为可以从前后两个方向进行。然而，双链表的存储空间需求比单链表高，因为每个节点需要额外存储一个指针，所以其存储密度较低。
### 双链表的初始化
在C语言中，我们可以定义一个结构体来表示双链表的节点，如`DNode`，包括数据域`data`以及前驱`prior`和后继`next`两个指针。`DLinkList`是一个指向`DNode`类型的指针，通常用作链表的头指针。初始化双链表通常包括分配一个头结点并设置其`prior`和`next`指针为`NULL`。
```c
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;
}
// 判断双链表是否为空（带头结点）
bool Empty(DLinkList L){
if(L->next == NULL)
return true;
else
return false;
}
```
### 双链表的插入操作
插入新节点到双链表中通常有两种情况：
1. 在指定节点`p`之后插入节点`s`。首先，更新`s`的`next`和`prior`指针，然后更新`p`的`next`指针和`p->next`的`prior`指针。
2. 需要注意的是，如果`p`是链表的最后一个节点，`p->next`为空，直接插入会导致空指针错误，因此在插入之前需要检查这种情况。
```c
// ① 在p结点之后插入s结点（考虑了p是尾结点的情况）
bool InsertNextDNode(DNode* p, DNode* s){
if(p == NULL || s == NULL) // 非法参数
return false;
if(p->next == NULL){ // 如果p是尾结点
p->next = s;
s->prior = p;
s->next = NULL;
} else {
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;
}
return true;
}
```
### 双链表的其他操作
除了插入，双链表还支持其他常见的操作，如删除节点、反向遍历、查找特定节点等。删除操作与插入类似，需要同时更新被删除节点及其前后节点的指针。反向遍历只需从尾节点开始向前移动即可。查找特定节点可以通过正向或反向遍历实现，具体取决于查找效率的需求。
双链表是一种灵活的数据结构，提供了对链表的双向访问能力，但需要更多的存储空间。在需要频繁进行反向操作或对性能要求较高的场景下，双链表是一个很好的选择。
我的内容管理
展开
