【数据结构】-----双链表（小白必看！！！）

 c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

给大家分享一句我很喜欢我话：

知不足而奋进，望远山而前行！！！

铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！

今天我们更新了双链表内容，

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

什么是双链表？

双链表的定义
 为什么引入双链表？

 单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

 双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

 双链表中结点类型的描述：

typedef int ListDataType;struct ListNode 
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;

这里可以看到我们把int变为ListNodeType类型，因为我们这个节点不一定就是int类型，用ListData代替int，就可以存储别的类型的数据了。啥时候用啥时候换。

然后用LTNode代替struct ListNode，这样更方便一些。

双链表上的操作：

1.1双链表的初始化：

在初始化之前，我们这里先说一下如何创建一个新节点。因为刚开始数据为空，因此我们先要创建新节点才可以。

//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead = (LTNode*)malloc(sizeof(LTNode));if (newhead == NULL){perror("malloc fail !!!");}newhead->next = newhead->prev = NULL;newhead->data = x;return newhead;
}

这就是创建新节点的代码。

下面我们来看一下初始化的代码：

//初始化
LTNode* InitNode()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

这样我们就完成了第一步，链表的初始化。这里记住我们创建出来的第一个节点，不能直接去使用，而是要指向本身才可以。否则会将自身变为NULL。

1.2打印链表：

这里也是非常简单，就是我们遍历链表即可。

void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur = head->next;while (cur != head){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

这里要注意的就是，while循环中条件不能是cur，否则这样就会无限的进行下去，我们要令cur！=head。这里的head就是我们的第一个节点，我们也叫它为哨兵位。

1. 3后插

后插相对来说也是比较简单的，下面我们来看一下代码。

//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->prev;Tail->next = newhead;newhead->prev = Tail;newhead->next = phead;phead->prev = newhead;}

首先我们要对phead进行断言，防止传过来的是空指针。

然后这个交换的过程需要大家自己慢慢去琢磨，原理很简单，就是将原本的最后一个变成新的节点，哨兵位的上一个变成新的节点。只是存在一些细节需要大家去注意一下。

1.4前插

//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->next;newhead->next = Tail;Tail->prev = phead;phead->next = newhead;newhead->prev = phead;}

这个是前插的代码，原理和后插也大差不差，还是将哨兵位的下一个变成新节点，原本的第一个节点变成第二个节点。

1.5头删

//头删
void LTPopFront(LTNode* head)
{assert(head);assert(head->next != head);LTNode* Next = head->next;head->next = Next->next;Next->prev = head;free(Next);Next = NULL;}

头删就是一定要断言head和head的下一个，如果只有一个哨兵位也无法进行删除。

然后剩下的就是把哨兵位的下一个变成第二个节点，第二个节点的上一个变成哨兵位，最后将原本的第一个节点释放掉，置为NULL。

1.6尾删

/尾删
void LTPopBack(LTNode* head)
{assert(head);assert(head->next != head);LTNode* cur = head->prev;head->prev = cur->prev;head->prev->next = head;free(cur);cur = NULL;
}

依然是对head和他的下一个进行断言。然后思路与前面的头删大致相同。只是是对哨兵位的上一个进行操作。

1.7任意插入

//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead = BuyNode(x);LTNode* posPrev = pos->prev;newhead->prev = posPrev;posPrev->next = newhead;pos->prev = newhead;newhead->next = pos;}

这里的任意插入我们需要事先找到我们要插入的数的位置，然后在这个位置的后面进行插入。这就需要一个find函数，这个我们后面会讲到，暂时不用去管，我们先弄清楚任意插入的思路，就是将创建一个新的节点，然后将pos的下一个变成它，后面的节点的前一个变成他。

1.8任意位置删除

//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead，但是没有参数phead，无法增加校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;

这个依然要用到Find函数，还是先不用去管，我们先看一下这个的思路，思路也是很简单，就是将pos前面的节点指向pos后面，pos后面的节点指向pos前面。

1.9寻找

LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head->next != NULL);LTNode* cur = head->next;while (cur != head){if (cur->data == x){return cur;}cur = cur->next;}printf("找不到\n");return NULL;
}

这里就是我们find函数的代码了，我们首先要对head和head->next进行断言，防止其是NULL，然后创建一个cur，进行while循环，条件依旧是cur!=head，然后找到的话就返回这个节点，找不到就返回空指针。

1.10链表的销毁

最后我们来说一下链表的销毁，这里我们要对每一个节点都要销毁。

//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

这个就要相对简单一些了，就是令pcur等于head->next,然后遍历，最后对phead进行销毁。

全部代码

List.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ListDataType;struct ListNode 
{ListDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;typedef struct ListNode LTNode;//初始化
LTNode* InitNode();//创建新节点
LTNode* BuyNode(ListDataType x);//打印
void ListNodeprint(LTNode* head);//后插
void LTNPushBack(LTNode* phead, ListDataType x);//前插
void LTPushFront(LTNode* phead, ListDataType x);//头删
void LTPopFront(LTNode* head);//尾删
void LTPopBack(LTNode* head);//任意点插入
void LTInsert(LTNode* pos, ListDataType x);//任意点删除
void LTErase(LTNode* pos);//查找
LTNode* LTFind(LTNode* head, ListDataType x);//链表的销毁
void LTDestroy(LTNode* phead);

List.c:

#include"List.h"//创建新节点
LTNode* BuyNode(ListDataType x)
{LTNode* newhead = (LTNode*)malloc(sizeof(LTNode));if (newhead == NULL){perror("malloc fail !!!");}newhead->next = newhead->prev = NULL;newhead->data = x;return newhead;
}//初始化
LTNode* InitNode()
{LTNode* phead = BuyNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//打印
void ListNodeprint(LTNode* head)
{assert(head);LTNode* cur = head->next;while (cur != head){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//后插
void LTNPushBack(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->prev;Tail->next = newhead;newhead->prev = Tail;newhead->next = phead;phead->prev = newhead;}//前插
void LTPushFront(LTNode* phead, ListDataType x)
{assert(phead);LTNode* newhead = BuyNode(x);LTNode* Tail = phead->next;newhead->next = Tail;Tail->prev = phead;phead->next = newhead;newhead->prev = phead;}//头删
void LTPopFront(LTNode* head)
{assert(head);assert(head->next != head);LTNode* Next = head->next;head->next = Next->next;Next->prev = head;free(Next);Next = NULL;}//尾删
void LTPopBack(LTNode* head)
{assert(head);assert(head->next != head);LTNode* cur = head->prev;head->prev = cur->prev;head->prev->next = head;free(cur);cur = NULL;
}//任意插入
void LTInsert(LTNode* pos, ListDataType x)
{assert(pos);LTNode* newhead = BuyNode(x);LTNode* posPrev = pos->prev;newhead->prev = posPrev;posPrev->next = newhead;pos->prev = newhead;newhead->next = pos;}//pos删除
void LTErase(LTNode* pos)
{//pos理论上不能为phead，但是没有参数phead，无法增加校验assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}LTNode* LTFind(LTNode* head, ListDataType x)
{assert(head);assert(head->next != NULL);LTNode* cur = head->next;while (cur != head){if (cur->data == x){return cur;}cur = cur->next;}printf("找不到\n");return NULL;
}//链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

test.c:

#include"List.h"int main()
{LTNode* head = InitNode();LTNPushBack(head, 1);LTNPushBack(head, 2);LTNPushBack(head, 3);LTNPushBack(head, 4);LTNode* find = LTFind(head, 1);LTErase(find);find = NULL;//打印ListNodeprint(head);//销毁LTDestroy(head);
}

总结：

双链表是一种常见的数据结构，与单链表相比，每个节点不仅保存了指向下一个节点的指针，还保存了指向前一个节点的指针。这种结构的引入增加了链表的灵活性和功能性。

首先，双链表支持双向遍历。由于每个节点都有指向前一个节点的指针，可以从任一节点开始向前或向后遍历链表，这对于某些操作如逆序遍历或者在特定节点前后插入节点非常方便。

其次，双链表更便于节点的删除和插入。在单链表中，要删除或插入一个节点，需要找到其前一个节点，而在双链表中，只需要修改节点本身的指针即可，无需额外的查找操作，从而提高了操作效率。

然而，双链表相比单链表需要额外的空间来存储前一个节点的指针，因此会占用更多的内存。在某些情况下，如果对内存占用有限制，可能需要权衡选择是否使用双链表。

总的来说，双链表是一种功能强大的数据结构，适用于需要频繁进行节点插入、删除和双向遍历的场景，但在内存占用上需要谨慎权衡。