双向链表
双向链表有一点不同于单向链表. 单向链表只能是一个顺序方向进行查找, 而双向链表可以对下一个以及上一个进行查找
image.png
从上图中可以看到，双向链表中各节点包含以下 3 部分信息（如下图所示）：
- 指针域 prior：用于指向当前节点的直接前驱节点；
- 数据域 data：用于存储数据元素。
-
指针域 next：用于指向当前节点的直接后继节点；
image.png
1.双链表的节点结构
typedef struct Node {
struct Node *prior;//指向直接前驱节点
ElemType data;//数据域
struct Node *next;//指向直接后继节点
} Node;
2. 创建双向链表
//5.1 创建双向链表
Status createLinkList(LinkList *L){
//*L 指向头结点
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->prior = NULL;
temp->next = NULL;
temp->data = i;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
3.遍历双向链表
//2、遍历双向链表
void printfLinkLisk(LinkList list){
printf("遍历链表：\n");
if (list == NULL || list->next == NULL) {
printf("这是一个空链表\n");
return;
}
LinkList p = list;
//判断next是否全部正确
printf("根据next从前往后遍历：");
while (p->next) {
printf("%d ",p->next->data);
p = p->next;
}
printf("\n");
//判断prior是否全部正确
printf("根据prior从后往前遍历：");
while (p != list) {
printf("%d ",p->data);
p = p->prior;
}
printf("\n");
}
4.双向链表插入元素
因为我的双向链表有头节点，所以只有两种添加情况：
-
添加至表的中间位置
同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 4 个步骤(步骤中的顺序中 3 必须放到 1 和 2 后面，其它顺序可变)，如下图所示：
- 将priorNode->next节点的prior指向新节点；
- 将新节点->next指向原来的priorNode->next；
- 将priorNode->next指向新节点；
- 新节点的prior指向priorNode。
image.png
-
添加至表尾
与添加到表中间的步骤只需要少掉步骤 1。因为priorNode->next是Null，不能用它执行操作，否则会崩溃。
//5.3 双向链表插入元素
Status ListInsert(LinkList *L, int i, ElemType data){
//1. 插入的位置不合法 为0或者为负数
if(i < 1) return ERROR;
//2. 新建结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
//3.将p指向头结点!
LinkList p = *L;
//4. 找到插入位置i直接的结点
for(int j = 1; j < i && p;j++)
p = p->next;
//5. 如果插入的位置超过链表本身的长度
if(p == NULL){
return ERROR;
}
//6. 判断插入位置是否为链表尾部;
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
}else
{
//1️⃣ 将p->next 结点的前驱prior = temp
p->next->prior = temp;
//2️⃣ 将temp->next 指向原来的p->next
temp->next = p->next;
//3️⃣ p->next 更新成新创建的temp
p->next = temp;
//4️⃣ 新创建的temp前驱 = p
temp->prior = p;
}
return OK;
}
5.删除双向链表指定位置上的结点
根据索引删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。
image.png
//5.4 删除双向链表指定位置上的结点
Status ListDelete(LinkList *L, int i, ElemType *e){
int k = 1;
LinkList p = (*L);
//1.判断双向链表是否为空,如果为空则返回ERROR;
if (*L == NULL) {
return ERROR;
}
//2. 将指针p移动到删除元素位置前一个
while (k < i && p != NULL) {
p = p->next;
k++;
}
//3.如果k>i 或者 p == NULL 则返回ERROR
if (k>i || p == NULL) {
return ERROR;
}
//4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
LinkList delTemp = p->next;
*e = delTemp->data;
//5. p->next 等于要删除的结点的下一个结点
p->next = delTemp->next;
//6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
//7.删除delTemp结点
free(delTemp);
return OK;
}
6.删除双向链表指定的元素
根据值删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。
//5.5 删除双向链表指定的元素
Status LinkListDeletVAL(LinkList *L, int data){
LinkList p = *L;
//1.遍历双向循环链表
while (p) {
//2.判断当前结点的数据域和data是否相等,若相等则删除该结点
if (p->data == data) {
//修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣
p->prior->next = p->next;
//修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣
if(p->next != NULL){
p->next->prior = p->prior;
}
//释放被删除结点p
free(p);
//退出循环
break;
}
//没有找到该结点,则继续移动指针p
p = p->next;
}
return OK;
}
7.在双向链表中查找元素
//5.6.1 在双向链表中查找元素
int selectElem(LinkList L,ElemType elem){
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return i;
}
i++;
p = p->next;
}
return -1;
}
8.在双向链表中更新结点
//5.6.2 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
