一、什么是双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
二、双向链表结构
image.png
三、双向链表的使用
- 创建双向链表
//双向循环链表初始化
Status creatLinkList(linkList *L){
*L = (linkList)malloc(sizeof(Node));
if (*L == NULL) return ERROR;
(*L)->next = *L;
(*L)->prior = *L;
//新增数据
linkList p = *L;
for (int i = 0; i < 2; i++) {
//1.创建一个临时结点
linkList temp = (linkList)malloc(sizeof(Node));
temp->data = i;
//2.为新增的结点建立双向链表关系
//①p的后继为temp
p->next = temp;
//②temp的前驱是p
temp->prior = p;
//③temp的后继为*L
temp->next = *L;
//④p的前驱为新建的temp
if (i == 0) {
p->prior = temp;
}
//⑤p要记录最后的结点的位置，方便下一次插入
p = p->next;
}
return OK;
}
-
双向链表插入
image.png
//双向循环链表插入元素
Status LinkListInsert(linkList *L, int index, ElemType e){
//创建指针p，指向双向链表头
linkList p = (*L);
int i = 1;
//2.双向链表为空，则返回error
if (*L == NULL) return ERROR;
//3.找到插入的前一个位置的结点p
while (i < index && p->next != *L) {
p = p->next;
i++;
}
//4.如果i>index,则返回error
if (i > index) return ERROR;
//5.创建新结点temp
linkList temp = (linkList)malloc(sizeof(Node));
//6.temp的结点为空 返回error
if (temp == NULL) return ERROR;
//7.将生成的新结点temp数据域赋值e
temp->data = e;
//8.将结点temp的前驱设为p
temp->prior = p;
temp->next = p->next;
p->next = temp;
//如果temp 结点不是最后一个结点
if (*L != temp->next) {
//temp节点的下一个结点的前驱为temp 结点
temp->next->prior = temp;
}else{
(*L)->prior = temp;
}
return OK;
}
-
双向链表删除
image.png
Status LinkListDelete(linkList *L,int index,ElemType *e){
int i = 1;
linkList temp = (*L)->next;
if (*L == NULL) return ERROR;
//如果删除到只剩下首元结点了,则直接将*L置空
if (temp->next == *L) {
free(*L);
(*L) = NULL;
return OK;
}
//找到要删除的结点
while (i < index) {
temp = temp->next;
i++;
}
//给e赋值要删除结点的数据域
*e = temp->data;
//修改被删除结点的前驱结点的后继指针
temp->prior->next = temp->next;
//修改被删除结点的后继结点的前驱指针
temp->next->prior = temp->prior;
//删除结点temp
free(temp);
temp = NULL;
return OK;
}
