数据结构与算法——双链表的详解以及增、插、删、查、印、毁的实现

一、前言

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();//初始化2ListPushBack(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。

只有不断学习，才能不断进步，才能在激烈的竞争中立于不败之地。