【数据结构】双链表—超详解

大家好，欢迎来到IT知识分享网。

目录

一.🐾前言🐾

二.🐾链表的种类🐾

1.⌛什么是链表⌛

2.⌛链表的构成⌛

三.🐾双链表的实现🐾

1.⌛结点的定义⌛

2.⌛创建一个新结点⌛

3.⌛初始化⌛

4.⌛打印链表⌛

5.⌛头插⌛

6.⌛尾插⌛

7.⌛头删⌛

8.⌛尾删⌛

9.⌛查找链表⌛

10.⌛在pos位置进行插入⌛

11.⌛删除pos位置⌛

四.🐾双链表的整体实现🐾

1.⌛List.h⌛

2.⌛List.c⌛

3.⌛test.c⌛

刹国（结束）！！！！

一.🐾前言🐾

前面我们讲解了顺讯表（实质就是数组）的增删查改，今天我们来讲解一下另一个数据结构—双链表。双链表其实是链表这种数据结构中的一种，本章讲解的链表是双向带头循环链表。正如你所见，链表分为带头和不带头，双向和单向，循环和不循环，因此彼此之间就能够组合出八种链表。但是在这八种链表中考得最多的是单链表（不带头单向不循环链表）和双链表（带头双向循环链表）。很显然，单链表的结构要简单得多，但是单链表实现起来却要比双链表复杂一些，而双链表结构虽然复杂一些，但是这种结构却是非常好用，且非常易于实现。咱们有简入难，今天就先来讲一下双链表，体验一下双链表的厉害之处。

二.🐾链表的种类🐾

1.⌛什么是链表⌛

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。（线性表顾名思义就是像线一样连接起来的表，需要注意的是这里所说的表是一种数据结构，而不是平时我们所说的表格），例如单链表

是不是就像一条线一样把他们连接起来，至于什么叫做链式的存储结构详细看下面的介绍，这就是一个链表，且是链表中的单链表。

2.⌛链表的构成⌛

链表中每个数据元素都由两部分组成：1、本身的信息，称为“数据域”；2、指向直接后继的指针，称为“指针域”（这里需要注意的是，指针域并不是只有指向后面元素地址的指针，也可能存在指向前面的元素地址的指针，例如单向链表只需要一个指针指向后面的元素，而双链表还需要一个指针指向前面一个元素的地址，以此来构成双向）。这两部分信息组成数据元素的存储结构，称之为“结点”；n个结点通过指针域相互链接，组成一个链表。

单链表：

双向链表：

prev为指向前一个结点的地址的指针，存储前一个结点的地址，data为该结点存储的数据，nex为

指向下一个结点的地址的指针，存储下一个结点的地址。

三.🐾双链表的实现🐾

1.⌛结点的定义⌛

//定义类型 typedef int LTDataType; typedef struct LTNode { LTDataType data; struct LTNode* prev; struct LTNode* next; }LTNode;

上面我们讲过，链表的结点由数据域和指针域爱两个部分构成，这就意味着我们需要对多类数据进行操作，因此定义一个结构体，正好可以满足这一需求。用类型重定义关键字typedef将数据类型以及结构体类型分别重定义为LTDataType和LTNode,以便后续修改代码和操作。

2.⌛创建一个新结点⌛

//创建一个新节点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }

链表只是一种数据结构，数据结构存在的意义就是存储数据，便于对数据进行操作，而对数据的操作无非就是增删查改这几类。因此我们在增加数据时就不可避免的需要开辟一个新的同类的数据类型来存储数据，链表中增加数据分为头插和尾插，头插就是在链表的头部插入数据，尾插就是在链表的末尾插入数据。在几个部分都需要使用相同的代码，可以将其独立出来写成一个函数，之后这一部分的使用直接调用函数即可，这样可以大大降低代码的冗余程度。开辟后新节点后，将数据赋值为形参X,将前后指针分别赋初值为NULL，然后返回新结点的地址。

3.⌛初始化⌛

//初始化 LTNode* LTInit() { LTNode* head = BuyLTNode(-1); head->next = head->prev = head; return head; }

双链表为带头的双向循环链表，带的这个“头”，又被称为哨兵位的头结点，这个结点的数据是不使用的，因此该结点的数据域可以任意放一个值，这里我们放的是-1。双链表的增删查改操作的数据都是从头结点的下一个结点的数据开始。初始化后的头结点如下：

4.⌛打印链表⌛

//打印链表 void LTPrint(LTNode* phead) { assert(phead); printf("guard<->"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->data); cur = cur->next; } printf("\n"); }

guard代表头结点的哨兵位，定义一个指针cur指向头结点的下一个结点，然后遍历这个链表的每一个结点，打印出每个结点内存储的数据，因为双链表是循环的，因此当cur回到头结点时，循环结束。

5.⌛头插⌛

//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); phead->next->prev = newnode; newnode->prev = phead; newnode->next = phead->next; phead->next = newnode; //LTInsert(phead->next, x); }

头插顾名思义就是在链表的头部插入数据，但是这里需要注意的是，带哨兵位头结点的链表的头插都是在头结点之后进行插入。既然是插入新数据我们就需要创建新节点，然后将其链接到头结点的后面。详细的链接过程如上代码所示，链接时要注意赋值顺序，要保证想要的地址不被更新或覆盖。例如若调换上述链接顺序，如下

//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); phead->next = newnode; phead->next->prev = newnode; newnode->prev = phead; newnode->next = phead->next; }

代码中先将头结点和新结点进行了链接，那么此时phead->next指向的就是newnode，而不是原来的下一个结点，这就会导致后面连续的错误。因此在进行链接时需要格外注意链接顺序。

6.⌛尾插⌛

//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->next; while (tail->next != phead) { tail = tail->next; } tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; //LTInsert(phead, x); }

尾插就是在链表的尾部插入数据，因此尾插的关键在于找尾，尾插的常规找法就是将链表遍历一遍然后找到尾部，建立新节点，再对其进行链接。双链表是循环起来的，因此尾部结点的next存的是头结点的地址，所以当tail->next等于phead时，就找到了尾结点。同头插一样，进行链接时注意链接顺序即可。

7.⌛头删⌛

//头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* cur = phead->next; cur->next->prev = phead; phead->next = cur->next; free(cur); //LTEarse(phead->next); }

头删即删除头结点之后的那个结点，因为这些结点都是动态开辟出来的，所以我们只需要将其释放就行，但是需要注意的是在将结点释放之前，需要将第三个结点与头结点链接起来。

8.⌛尾删⌛

//尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; while (tail->next != phead) { tail = tail->next; } tail->prev->next = phead; phead->prev = tail->prev; free(tail); //LTEarse(phead->prev); }

头插，尾插，头删明白后，相信尾插对于各位小伙伴来说就是信手拈来的事，尾删就是删除尾结点，用和尾插相同的方法找到尾结点后，先将其与前一个结点以及头结点进行链接，再将前一个结点的next与头结点进行链接，然后将其释放即可。

9.⌛查找链表⌛

//查找链表 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

查找链表查找的是链表内的数据，具体方法就是遍历链表，若找到对应数据，则返回该结点地址，即当前cur的值，若找不到则返回空指针。

10.⌛在pos位置进行插入⌛

//在pos位置之前进行插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; newnode->next = pos; pos->prev = newnode; }

在pos位置插入，即在已存在的数据中的某个位置的前面进行数据插入，所以在使用该函数时需要配合查找链表这个函数使用。当然如果你想要实现在其后面进行数据插入也可以，只需要改变一下链接就行。

上面我们讲解了找尾的常规方法，其实你有没有想到这一点，双链表是循环起来的，而头结点的prev存的不就是尾结点的地址吗，也就是说可以认为头结点的前一个结点不就是尾结点吗，所以这个函数还有一个妙用就是它同样可以实现尾插，代码如下：

//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }

同理，尾插可以实现，那么头插同样可以，头插就是在phead->next之前插入，即在第二个结点之前进行插入。代码如下：

//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x); }

所以若面试官让你快速写出一个双链表，那么你只需要写一个函数是不是就能完成这几个函数的功能。

11.⌛删除pos位置⌛

//删除pos位置 void LTEarse(LTNode* pos) { assert(pos); LTNode* next = pos->next; pos->prev->next = next; next->prev = pos->prev; free(pos); }

删除pos位置的数据，只需要找到该数据，然后释放掉该结点即可。当然，在释放之前同样需要先将该结点的前一个结点与后一个结点进行链接。

同在pos位置插入函数一样，该函数同样可以实现头删和尾删。具体实现代码如下：

//头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTEarse(phead->next); }

//尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTEarse(phead->prev); }

四.🐾双链表的整体实现🐾

1.⌛List.h⌛

声明函数，声明类型，包含头文件

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //定义类型 typedef int LTDataType; typedef struct LTNode { LTDataType data; struct LTNode* prev; struct LTNode* next; }LTNode; //函数声明 //初始化 LTNode* LTInit(); //销毁双向链表 void LTDestroy(LTNode* phead); //打印链表 void LTPrint(LTNode* phead); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头删 void LTPopFront(LTNode* phead); //尾删 void LTPopBack(LTNode* phead); //查找链表 LTNode* LTFind(LTNode* phead, LTDataType x); //在pos位置之前进行插入 void LTInsert(LTNode* pos, LTDataType x); //删除pos位置 void LTEarse(LTNode* pos); 

2.⌛List.c⌛

函数的实现

#define _CRT_SECURE_NO_WARNINGS #include"List.h" //创建一个新节点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化 LTNode* LTInit() { LTNode* head = BuyLTNode(-1); head->next = head->prev = head; return head; } //销毁双向链表 void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); } //打印链表 void LTPrint(LTNode* phead) { assert(phead); printf("guard<->"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->data); cur = cur->next; } printf("\n"); } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); phead->next->prev = newnode; newnode->prev = phead; newnode->next = phead->next; phead->next = newnode; //LTInsert(phead->next, x); } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyLTNode(x); LTNode* tail = phead->next; while (tail->next != phead) { tail = tail->next; } tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; //LTInsert(phead, x); } //头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* cur = phead->next; cur->next->prev = phead; phead->next = cur->next; free(cur); //LTEarse(phead->next); } //尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* tail = phead->next; while (tail->next != phead) { tail = tail->next; } tail->prev->next = phead; phead->prev = tail->prev; free(tail); //LTEarse(phead->prev); } //查找链表 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置之前进行插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; newnode->next = pos; pos->prev = newnode; } //删除pos位置 void LTEarse(LTNode* pos) { assert(pos); LTNode* next = pos->next; pos->prev->next = next; next->prev = pos->prev; free(pos); }

3.⌛test.c⌛

功能验证及逻辑测试

#define _CRT_SECURE_NO_WARNINGS #include"List.h" void ListTest() { LTNode* plist = LTInit(); LTPushFront(plist, 1); LTPushFront(plist, 2); LTPushFront(plist, 3); LTPushFront(plist, 4); LTPushFront(plist, 5); LTPrint(plist); //LTPushBack(plist, 1); //LTPushBack(plist, 2); //LTPushBack(plist, 3); //LTPushBack(plist, 4); //LTPushBack(plist, 5); //LTPopFront(plist); //LTPopBack(plist); //LTPrint(plist); //LTPushFront(plist, 1); //LTPushBack(plist, 5); //LTPrint(plist); LTNode* pos = LTFind(plist, 5); LTInsert(pos, 50); LTPrint(plist); //LTEarse(pos); //LTPrint(plist); } int main() { ListTest(); return 0; }

本篇以双链表的实现为主题的博客到此就要结束了，希望本篇博客可以帮助到各位小伙伴，博主码字不易，如果本篇博客对你有所帮助，还望各位小伙伴点赞👍，收藏⭐+关注，感谢各位的支持！如果有什么不明白的地方或是另有其他的高见，也可以在评论区留言，博主也会及时回复或进行更改，欢迎指正，谢谢！

刹国（结束）！！！！