【数据结构】-----双链表（小白必看！！！）
【数据结构】-----双链表（小白必看！！！）
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);
}总结：
双链表是一种常见的数据结构，与单链表相比，每个节点不仅保存了指向下一个节点的指针，还保存了指向前一个节点的指针。这种结构的引入增加了链表的灵活性和功能性。
首先，双链表支持双向遍历。由于每个节点都有指向前一个节点的指针，可以从任一节点开始向前或向后遍历链表，这对于某些操作如逆序遍历或者在特定节点前后插入节点非常方便。
其次，双链表更便于节点的删除和插入。在单链表中，要删除或插入一个节点，需要找到其前一个节点，而在双链表中，只需要修改节点本身的指针即可，无需额外的查找操作，从而提高了操作效率。
然而，双链表相比单链表需要额外的空间来存储前一个节点的指针，因此会占用更多的内存。在某些情况下，如果对内存占用有限制，可能需要权衡选择是否使用双链表。
总的来说，双链表是一种功能强大的数据结构，适用于需要频繁进行节点插入、删除和双向遍历的场景，但在内存占用上需要谨慎权衡。