了解过单向链表的人都知道，单向链表是从从头到尾，一个结点指向下一个结点的单向的数据链路，就好比我们平时见到的单向马路一样，只能朝着一个方向前进，每一个数据结点都只知道它的下一个结点在哪里，却不知道它的上一个结点在哪里。
那么我们如果要查找上一个结点的位置，就只能从头遍历。
双向链表
为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链表（double linkedlist）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
双向链表
存储结构
// ElemtType类型根据实际情况而定，这里假设为int
typedef int ElemType;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
// Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int Status;
// 线性表的双向链表存储结构
typedef struct DulNode {
ElemType data;
struct DulNode *prior;//前驱
struct DulNode *next;//后继
} DulNode, *DulLinkList;
创建
创建一个带头结点空的双向链表
// 创建一个带头结点空的双向链表·
Status CreatDulNode(DulLinkList *L) {
*L = (DulLinkList)malloc(sizeof(DulNode ));
if (*L == NULL) {
return ERROR;
}
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
return OK;
}
插入
我们要向第i个位置插入一个新的结点
算法思路：
- 首先找到第i-1个结点p；
- 将p->next->prior = temp;
- 将temp->next = p->next;
- 将p->next = temp;
- 将temp->prior = p;
效果如下图所示
双向链表的插入
代码实现：
Status InsertNode(DulLinkList *L, ElemType data, int index) {
// 让p指向头结点
DulLinkList p = *L;
int j = 1;
while (p && j < index) {
p = p->next;
j++;
}
if (!p || j > index) {
return ERROR;
}
// 创建新的结点
DulLinkList temp = (DulLinkList)malloc(sizeof(DulNode));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
// 插入的位置是末尾
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
return OK;
}
// 插入的位置不是末尾
// 先处理temp 的后继
p->next->prior = temp;
temp->next = p->next;
// 再处理temp 的前驱
p->next = temp;
temp->prior = p;
return OK;
}
删除
删除双向链表的第i个位置的结点
算法思路：
- 找到第i为位置的结点p；
- 将p->prior->next=p->next;
- 将p->next-prior = p->prior;
- free(p);
双向链表删除
代码实现
Status DeleteDulNode (DulLinkList *L, int index) {
// 让p指向头结点
DulLinkList p = *L;
int j = 1;
// 找到要删除的结点
while (p && j < index + 1) {
p = p->next;
j++;
}
// p不存在， 删除的位置非法
if (!p || j > index + 1) {
return ERROR;
}
// 删除的是末尾
if (p->next == NULL) {
p->prior->next = NULL;
p->prior = NULL;
free(p);
}
// 删除的不是末尾
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
双向循环链表
既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。
双向链表的循环带头结点的空链表如图所示。
双向链表
非空的循环的带头结点的双向链表如图所示。
双向循环链表
由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁？当然还是它自己。它的前驱的后继自然也是它自己，即：
p->next->prior = p = p->prior->next
双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的，查找元素的，获得元素位置的等。
总结
- 双向链表对比单向链表，多了一个前驱，用来记录该结点的上一个结点；
- 处理双向链表的插入和删除，需要多处理一个前驱；
- 双向链表在空间占用上比单链表要多一些，不过由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。就是用空间来换时间。
