一、前言
hello啊，各位宝子们。今天的你是在继续选择躺平，还是在持之以恒地努力学习呢？躺平呢有躺平的安逸，努力呢也有努力的收获。也希望大家平衡好这两者之间的得失关系。言归正传，今天咱们继续深入翱翔数据结构与算法的海洋，进一步领悟其独特的魅力。，up今天所要给大家介绍的数据结构就是——双链表。希望大家努力学习，耐心阅读。
二、链表的分类
这时候有的宝子可能就比较困惑。up我们之前不是才学习了单链表的数据结构吗？而今天又要开始学习双链表，那么链表到底又是怎么一个分类法呢。别急，up这就带领大家解开这层神秘的面纱。
链表的结构非常多样化，具体分为三个大方面——是否带头、方向指向以及是否循环。这样的话由于每个大方面存在两种情况，所以组合情况就有8（222）种链表结构。
2.1是否带头
2.2单向或者双向
2.3循环或者不循环
到这里，大家的困惑相信也就烟消云散了吧。那我们之前所学习的单链表，它的全称就是不带头单向不循环链表。而我们这次所要学习的双链表，全称则就是带头双向循环链表。虽然链表的结构分类可达8种之多，但是最常见的就是单链表和双链表这两种结构。
三、双链表
3.1双链表的概念
双链表是一种数据结构，它的每个节点除了存储数据外，还有两个指针，分别指向前一个节点和后一个节点。这种结构使得双链表在进行插入和删除操作时更为高效，因为可以直接访问任何节点的前驱和后继节点。
3.2双链表的结构
四、双链表各功能的实现
4.1双链表结点的创建
代码展示：
ListNode* Listbuynode(ListDataType x)//申请结点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->pre = newnode->next = newnode;
return newnode;
}
4.2双链表的初始化
4.2.1第一种初始化方式
代码展示：
void ListInit1(ListNode** pphead)//第一种初始化
{
assert(pphead);
*pphead = Listbuynode(-1);
}
4.2.2第二种初始化方式
ListNode* ListInit2()//第二种初始化
{
ListNode* phead = Listbuynode(-1);
return phead;
}
以上两种初始化的方式具体的不同在于：初始化1采用的是void类型，不需要返回值；初始化二采用的是ListNode*型，需要返回值。
4.3双链表判断是否为空
代码展示：
bool ListEmpty(ListNode* phead)//判空
{
assert(phead);
return phead->next == phead;
}
4.4双链表的尾、头及pos位置插入
4.4.1尾插
尾插的实质：在判断链表不为空的前提下，先让新结点的newnode->pre和newnode->next分别指向原链表的phead->pre和phead，最后再让原链表中的phead->pre->next和phead->pre再分别指向新节点newnode.
代码展示：
void ListPushBack(ListNode* phead,ListDataType x)//尾插
{
assert(phead);
ListNode* newnode = Listbuynode(x);
newnode->pre = phead->pre;
newnode->next = phead;
phead->pre->next = newnode;
phead->pre = newnode;
}
4.4.2头插
头插的实质：在判断链表不为空的情况下，先让新节点的newnode->pre和newnode->next分别指向原链表的phead和phead->next,最后再让原链表中的phead->next->pre和phead->next再分别指向新节点newnode。
注意事项：头插的位置是是在头结点之后，如果插入在头结点之前，实际效果是尾插。
代码展示：
void ListPushFront(ListNode* phead, ListDataType x)//头插
{
assert(phead);
ListNode* newnode = Listbuynode(x);
newnode->next = phead->next;
newnode->pre = phead;
phead->next->pre = newnode;
phead->next = newnode;
}
4.4.3pos位置之后插入
pos位置后插入的实质：在pos结点不为空的情况下，先让新结点newnode->next和newnode->pre分别指向原链表中的pos->next和pos，最后再让原链表中的pos->next->pre和pos->next指向新节点newnode。
代码展示：
void ListInsertBack(ListNode* pos, ListDataType x)//在pos位置后插入结点
{
assert(pos);
ListNode* newnode = Listbuynode(x);
newnode->next = pos->next;
newnode->pre = pos;
pos->next->pre = newnode;
pos->next = newnode;
}
4.4.4pos位置之前插入
pos位置之前插入的实质：pos结点不为空的情况下先让新节点newnode->next和newnode->pre分别指向原链表中的pos和pos->pre，最后再让原链表中的pos->pre->next和pos->pre分别指向新节点newnode。
代码展示：
void ListInsertFront(ListNode* pos, ListDataType x)//在pos位置前插入结点
{
assert(pos);
ListNode* newnode = Listbuynode(x);
newnode->next = pos;
newnode->pre = pos->pre;
pos->pre->next = newnode;
pos->pre = newnode;
}
4.5双链表的尾、头及pos位置删除
4.5.1尾删
尾删的实质：在判断链表非空的情况下，先把尾结点用del保存下来方便后续操作，再让del结点的del->pre->next指向phead，并且让phead->pre指向del->pre，最后再把del结点释放掉并且置为空即可。
代码展示：
void ListPopBack(ListNode* phead)//尾删
{
assert(!ListEmpty(phead));
ListNode* del = phead->pre;
del->pre->next = phead;
phead->pre = del->pre;
free(del);
del = NULL;
}
4.5.2头删
头删的实质：在判断链表非空的情况下，先把头删结点用del保存下来方便后续操作，接着再让del结点的del->next->pre指向phead，并且让phead->next指向del->next，最后再把del结点释放掉并且置为空即可。
注意事项： 头删删除的是头结点的下一个结点也就是11结点，并非是头结点，因为在双链表中头结点是不能删除和销毁的。
代码展示：
void ListPopFront(ListNode* phead)//头删
{
assert(!ListEmpty(phead));
ListNode* del = phead->next;
del->next->pre = phead;
phead->next = del->next;
free(del);
del = NULL;
}
4.5.3pos位置结点删除
pos位置删除实质：在判断pos结点不为空的情况下，先让pos->next->pre指向pos->pre，接着让pos->pre->next指向pos->next，最后将pos结点释放掉并且置为空即可。
代码展示：
void ListErase(ListNode* pos)//删除pos位置结点
{
pos->next->pre = pos->pre;
pos->pre->next = pos->next;
free(pos);
pos = NULL;
}
4.6双链表特定元素的查找
查找的实质：在判断链表不为空的情况下，定义一个开始结点指针pcur从phead->next结点开始，遍历整个链表，如果找到了则return pcur，没找到则return NULL，直到pcur = phead为止跳出循环。
代码展示：
ListNode* ListFind(ListNode* phead, ListDataType x)//查找特定元素
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)//找到了
{
return pcur;
}
pcur = pcur->next;
}
return NULL;//未找到
}
4.7双链表元素的打印
打印的实质：在判断链表不为空的情况下，定义一个开始结点指针pcur从phead->next结点开始，遍历整个链表，逐一打印元素，直到pcur=phead为止跳出循环。
void ListPrint(ListNode* phead)//双链表的打印
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d ->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
4.8双链表的销毁
4.8.1第一种销毁方式
void ListDestroy1(ListNode** pphead)//第一种销毁方法
{
assert(pphead);
ListNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}
4.8.2第二种销毁方式
void ListDestroy(ListNode* phead)//第二种销毁方法
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
销毁的实质：在判断链表不为空的情况下，定义一个开始结点指针pcur从pcur->next结点开始，遍历整个链表，逐一销毁，直到pcur = phead为止跳出循环，最后再把头结点销毁掉在置为空即可。
4.9双链表的传参
上面所有功能对已经实现完毕了，但是你可能会懵逼——为什么有的函数传参传的是一级指针，而又有的是传的二级指针呢？这里up给大家统一回答：关于传参到底是传一级指针还是二级指针，是看头结点是否发生改变，如果头结点不发生改变就传一级指针，相反如果头结点发生改变就传二级指针。
五、双链表整体代码分析
5.1头文件——List.h及代码展示
代码展示：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int ListDataType;//重命名
typedef struct ListNode//结点的结构体创建
{
ListDataType data;
struct ListNode* pre;
struct ListNode* next;
}ListNode;
ListNode* Listbuynode(ListDataType x);//申请结点
void ListInit1(ListNode** pphead);//第一种初始化
ListNode* ListInit2();//第二种初始化
bool ListEmpty(ListNode* phead);//判空
void ListPushBack(ListNode* phead, ListDataType x);//尾插
void ListPushFront(ListNode* phead, ListDataType x);//头插
void ListPopBack(ListNode* phead);//尾删
void ListPopFront(ListNode* phead);//头删
void ListInsertBack(ListNode* pos, ListDataType x);//在pos位置后插入结点
void ListInsertFront(ListNode* pos, ListDataType x);//在pos位置前插入结点
void ListErase(ListNode* pos);//删除pos位置结点
ListNode* ListFind(ListNode* phead, ListDataType x);//查找特定元素
void ListPrint(ListNode* phead);//双链表的打印
void ListDestroy1(ListNode** pphead);//第一种销毁方法
void ListDestroy(ListNode* phead);//第二种销毁方法
5.2主体代码文件——List.c及代码展示
代码展示：
#include "List.h"
ListNode* Listbuynode(ListDataType x)//申请结点
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->pre = newnode->next = newnode;
return newnode;
}
void ListInit1(ListNode** pphead)//第一种初始化
{
assert(pphead);
*pphead = Listbuynode(-1);
}
ListNode* ListInit2()//第二种初始化
{
ListNode* phead = Listbuynode(-1);
return phead;
}
bool ListEmpty(ListNode* phead)//判空
{
assert(phead);
return phead->next == phead;
}
void ListPushBack(ListNode* phead,ListDataType x)//尾插
{
assert(phead);
ListNode* newnode = Listbuynode(x);
newnode->pre = phead->pre;
newnode->next = phead;
phead->pre->next = newnode;
phead->pre = newnode;
}
void ListPushFront(ListNode* phead, ListDataType x)//头插
{
assert(phead);
ListNode* newnode = Listbuynode(x);
newnode->next = phead->next;
newnode->pre = phead;
phead->next->pre = newnode;
phead->next = newnode;
}
void ListPopBack(ListNode* phead)//尾删
{
assert(!ListEmpty(phead));
ListNode* del = phead->pre;
del->pre->next = phead;
phead->pre = del->pre;
free(del);
del = NULL;
}
void ListPopFront(ListNode* phead)//头删
{
assert(!ListEmpty(phead));
ListNode* del = phead->next;
del->next->pre = phead;
phead->next = del->next;
free(del);
del = NULL;
}
void ListInsertBack(ListNode* pos, ListDataType x)//在pos位置后插入结点
{
assert(pos);
ListNode* newnode = Listbuynode(x);
newnode->next = pos->next;
newnode->pre = pos;
pos->next->pre = newnode;
pos->next = newnode;
}
void ListInsertFront(ListNode* pos, ListDataType x)//在pos位置前插入结点
{
assert(pos);
ListNode* newnode = Listbuynode(x);
newnode->next = pos;
newnode->pre = pos->pre;
pos->pre->next = newnode;
pos->pre = newnode;
}
void ListErase(ListNode* pos)//删除pos位置结点
{
pos->next->pre = pos->pre;
pos->pre->next = pos->next;
free(pos);
pos = NULL;
}
ListNode* ListFind(ListNode* phead, ListDataType x)//查找特定元素
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)//找到了
{
return pcur;
}
pcur = pcur->next;
}
return NULL;//未找到
}
void ListPrint(ListNode* phead)//双链表的打印
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d ->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void ListDestroy1(ListNode** pphead)//第一种销毁方法
{
assert(pphead);
ListNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(*pphead);
*pphead = NULL;
}
void ListDestroy(ListNode* phead)//第二种销毁方法
{
assert(phead);
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
5.3测试文件——test.c及代码展示
5.3.1尾插演示
代码展示;
ListPushBack(plist, 1);//尾插
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
5.3.2头插演示
代码展示;
ListPushFront(plist, 5);//头插
ListPushFront(plist, 6);
5.3.3尾删演示
代码展示：
ListPopBack(plist);//尾删
ListPopBack(plist);
5.3.4头删演示
ListPopFront(plist);//头删
ListPopFront(plist);
5.3.5特定元素查找演示
代码展示：
ListNode* find = ListFind(plist, 4);//特定位置元素查找
if (find != NULL)
{
printf("找到了!");
}
else
{
printf("未找到！");
}
5.3.6pos位置后插入演示
代码展示：
ListInsertBack(find, 4);//pos后插入结点
5.3.7pos位置前插入演示
代码展示：
ListInsertFront(find, 3);//pos前插入结点
5.3.8pos结点删除演示
ListErase(find);//删除pos结点
5.3.9链表销毁演示
代码展示：
ListDestroy(plist);//链表的销毁
plist = NULL;
ListPrint(plist);
#include "List.h"
void test01()
{
//ListNode* plist = NULL;//初始化1
//ListInit1(&plist);
ListNode* plist = ListInit2();//初始化2
ListPushBack(plist, 1);//尾插
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushFront(plist, 5);//头插
ListPushFront(plist, 6);
//ListPopBack(plist);//尾删
//ListPopBack(plist);
//ListPopFront(plist);//头删
//ListPopFront(plist);
//ListNode* find = ListFind(plist, 4);//特定位置元素查找
//if (find != NULL)
//{
// printf("找到了!");
//}
//else
//{
// printf("未找到！");
//}
//ListInsertBack(find, 4);//pos后插入结点
//ListInsertFront(find, 3);//pos前插入结点
//ListErase(find);//删除pos结点
ListDestroy(plist);//链表的销毁
plist = NULL;
ListPrint(plist);
}
int main()
{
test01();
return 0;
}
六、总结
OK啦宝子们，到这里，数据结构——双链表以及所有功能的实现就讲述完毕了。怎么样大家的功力是否又蹭蹭蹭地往上涨了呢？经过这么久的努力学习，相信大家已然成为了一个高手了吧，哈哈哈。不过不要骄傲，我相信大家一定可以越来越NB。最后呢，祝大家在学习的道路上一帆风顺，终成大神。记得三连O。
只有不断学习，才能不断进步，才能在激烈的竞争中立于不败之地。
