🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️

1. 双向链表的定义和结构

  我们在前面就说了链表最常用的两种结构就是 “单链表”（无头单向不循环链表）以及 “双向链表”（有头双向循环链表），掌握了这两种方法，其他类型的链表也可以定义出来。

  在单链表中的头结点与双向链表中的头结点不太一样！单链表中的头结点是指——第一个有效数据，这个头结点可以改变也可以为NULL；但是双向链表中的头结点是指——“哨兵位”节点，一定存在，并且这个节点不存储有效数据，是不可以改变的。

2. 双向链表的实现

2.1 结构声明

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2.2 双向链表的初始化

1. 直接在main创建头结点，并且给其里面数据初始化在这里插入代码片

int main()
{LTNode* head = (LTNode*)malloc(sizeof(LTNode));if (!head){perror("malloc:");exit(1);}head->data = -1;head->next = head->prev = head;return 0;
}

2. 自定义BuyNode函数进行初始化

//申请一个节点
LTNode* BuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (!node){perror("malloc:");exit(1);}node->data = x;node->prev = node->next = node;return node;
}int main()
{LTNode* head = BuyNode(-1);return 0;
}

总之双向链表一定要创造一个不为空的头结点（哨兵位）
其次在创造新的节点的时候，指向前面后面的两个节点指针并不等于NULL，而是指向自己本身，这样才体现了循环

2.3 双向链表的打印

//链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;//处理链表只有头结点的情况if (pcur == phead){printf("链表没有有效数据！");return;}//处理一般情况while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}

2.4 尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//获取新的节点LTNode* newnode = BuyNode(x);//获取尾节点LTNode* ptail = phead->prev;newnode->prev = ptail;newnode->next = phead;ptail->next = newnode;phead->prev = newnode;
}

2.5 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{//获取新的节点LTNode* newnode = BuyNode(x);newnode->prev = phead;newnode->next = phead->next;newnode->next->prev = newnode;newnode->prev->next = newnode;
}

2.6 在指定位置之前插入

//在指定位置之前插入
void LTInsertFront(LTNode* pos, LTDataType x)
{//获取新的节点LTNode* newnode = BuyNode(x);newnode->prev = pos->prev;newnode->next = pos;newnode->prev->next = newnode;newnode->next->prev = newnode;
}

2.7 在指定位置之后插入数据

//在指定位置之后插入
void LTInsertBack(LTNode* pos, LTDataType x)
{//获取新的节点LTNode* newnode = BuyNode(x);newnode->prev = pos;newnode->next = pos->next;newnode->prev->next = newnode;newnode->next->prev = newnode;
}

2.8 尾删

//尾删
void LTPopBack(LTNode* phead)
{//链表至少要有头结点和一个有效元素assert(phead && phead->next != phead);//获取要删除的节点LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.9 头删

//头删
void LTPopFront(LTNode* phead)
{//链表至少要有头结点和一个有效元素assert(phead && phead->next != phead);//获取要删除的节点LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

2.10 删除指定位置的节点

//删除指定位置的节点
void LTDelete(LTNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.11 查找

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}printf("没有找到目标元素！\n");return	NULL;
}

2.12 链表的销毁

//链表的销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//头结点也要销毁free(phead);//并没有真正将头结点置为空phead = NULL;
}

3. 双向链表的细节

1. 由于双向链表的头结点不会改变，所以我们在实现各类方法的时候都是传入一级指针，而不是二级指针。

2. 不难从尾插方法看出，由于双向链表的结构特性，我们除了打印链表、查找和销毁链表需要进行循环，其他的方法我们很少用到循环（比如找尾节点）

3. 我们在插入一个节点的时候，同样是先改变外部环境（新创建的节点），最后再改变内部环境（插入位置前后节点的prev或next）

固定套路：

newnode->prev = pos;
newnode->next = pos->next;
//newnode前一个节点
newnode->prev->next = newnode;
//newnode后一个节点
newnode->next->prev = newnode;