我们在单链表中，有了next指针，这就使得我们要查找下一个结点的时间复杂度为O(1)。可是如果我们要查找上一个结点的话，那最坏的时间复杂度就是O(n)了，因为每次都需要从头开始遍历查找。为了克服这一缺点，设计出双向链表。双向链表是在单链表的每个结点中，再设置一个指向前驱结点的指针域。所以在双向链表中的所有结点都有两个指针域，一个指向直接后继，一个指向直接前驱。
//双向链表的存储结构
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node;
重点：由于这是双向链表，那么对于双向链表中的某一结点p，都有以下公式，即结点p的前驱的后继是p本身，结点p后继的前驱是p本身：
p->next->prior = p = p->prior->next
由于双向链表是从单链表扩展出来的，所以很多操作与单链表相同，如计算长度，查找元素等涉及一个方向的指针操作。
但双向链表由于增加了前驱指针，所以在插入、删除等操作与单链表不同，接下来看看双向链表的基本操作。
双向链表的创建
//5.1 创建双向链接
Status createLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));//创建头结点
if(*L == NULL) return ERROR;
(*L)->data = -1;
(*L)->prior = NULL;
(*L)->next = NULL;
return OK;
}
双向链表中增加数据元素
Status addElemToLinkList(LinkList *L){
//p 指向头结点
LinkList p = *L;
for(int i = 1; i < 10; i++){
//1 创建临时结点
LinkList temp = (LinkList)malloc(sizeof(Node));
if(temp == NULL) return ERROR;
temp->data = i;
temp->next = NULL;
temp->prior = NULL;
//2 将前一个结点的后继设置为temp
p->next = temp;
//3 将temp结点的前驱设置为p
temp->prior = p;
//4 将p指向下一个结点
p = p->next;
}
return OK;
}
双向链表插入数据
image.png
算法思路：
1、找到需要插入位置的前一个结点A；
2、将C结点的后继改成A->next，即B；
3、将A->next(B)结点的前驱改成C；
4、将C的前驱改成A；
5、将A的后继改成C；
Status ListInsert(LinkList *L, int i, ElemType data){
//p指向头结点
LinkList p = *L;
//新建临时结点temp
LinkList temp = (LinkList)malloc(sizeof(Node));
if(temp == NULL) return ERROR;
temp->data = data;
temp->next = NULL;
temp->prior = NULL;
//找到需要插入位置的前一个结点
int j = 1;
while(j<i && p != NULL){
j++;
p = p->next;
}
if(p == NULL) return ERROR;
//temp的后继是p的后继
temp->next = p->next;
//当增加结点的位置不是最后一个结点时，需要将p的后继的前驱改为temp
if(p->next != NULL){
p->next->prior = temp;
}
//temp的前驱是p
temp->prior = p;
//将p的后继改为temp
p->next = temp;
return OK;
}
双向链表的删除
image.png
算法思路：
1、找到需要删除结点B；
2、A->next = B->next;
3、B->next->prior = B->prior;
Status ListDelete(LinkList *L, int i, ElemType *e){
//从第一个结点的位置开始查找
LinkList temp = (*L)->next;
int j = 1;
for(j = 1; j < i && temp != NULL; j++){
temp = temp->next;
}
if(j>i || temp == NULL) return ERROR;
//将删除结点的后继设置为删除结点的后继
temp->prior->next = temp->next;
//若删除的不是最后一个结点，则需要将删除结点后继的前驱设置为删除结点的前驱
if(temp->next != NULL){
temp->next->prior = temp->prior;
}
*e = temp->data;
//由于是删除操作，故需要将删除结点处的内存释放
free(temp);
return OK;
}
总结：双向链表相对于单链表来说，要更复杂一些，毕竟增加了prior指针，对于插入和删除操作需要格外小心。另外，由于每个结点都需要记录两份指针，所以双向链表在空间上需要多占一些。不过，由于良好的对称性，使得对某个结点的前后结点操作方便一些，可以有效提高算法的时间性能。
