双向链表
前几篇文章，我们大致了解了链表是个什么东西，他有许多节点，节点里一个用于存储数据，一个用于存储下一个节点的地址。
这样的链表也叫做单链表。
而本文将介绍一下双向链表😎
介绍
双向链表，顾名思义，就是有两个方向，一个连接到上一个节点，另一个链接到下一个节点。
在c语言中，我们定义单链表是如下的。
struct Node{ int data; struct Node *next;}那么双向链表呢？实现起来也很简单。
struct Node{ int data; struct Node *next; struct Node *prev;}效果如下图
双向链表的优势与缺点
- 如果我们有指向任何节点的指针，那么我们可以进行反向查询。
比如这张图，我们这里显示一个名为temp的指针，那么我们可以访问temp,temp->next,temp->prev
而在单向链表里面，我们是无法通过一个指针来查询上一个节点的！😎你必须再用一个指针跟踪上一个节点！
- 删除节点更加方便
- 反转查询方便
缺点就是我们必须为上一个节点的指针使用额外的内存。还有就是在插入和删除时要操作更多的链接！，因此更容易出错！🤔
实现
假设我们有一个如下的链表
我们要实现，在头部插入节点，在尾部插入节点，打印函数，反转打印函数。
1.首先实现插头函数
void InsertAtHead(int x){ //插在头部 struct Node myNode; myNode.data=x; myNode.next=NULL; myNode.prev=NULL;}你觉得上面写的对吗？🤔
那肯定错了呀！ struct Node myNode;这里采用的是局部变量，只存在于栈空间，函数结束后就会被删除🤡
void InsertAtHead(int x){ //插在头部 struct Node *newNode=(struct Node*)malloc(sizeof(struct Node)); newNode->data=x; newNode->next=NULL; newNode->prev=NULL;}这样在堆里面申请内存才是正确的，还记得我们之前说过要操作堆里面的内存必须通过指针吗😎
由于创建一个新节点很常用，所以我们把他从这个函数中剥离出来！
struct Node *GetNewNode(int x){ struct Node *newNode=(struct Node*)malloc(sizeof(struct Node)); newNode->data=x; newNode->next=NULL; newNode->prev=NULL; return newNode;}接着我们再来实现插入
void InsertAtHead(int x){ struct Node *newNode=GetNewNode(x); if(head==NULL){ //处理空节点的情况 head = newNode; return; } head->prev=newNode; newNode->next=head; head=newNode;}处理空节点的情况就不画图了（懒）🤡
假设我们要在2前面插入一个4，如图（上面400地址的next应该是0，下面600地址左右均为0，这里笔误了）。
插入函数会将他们变成这样
简化成如下
如果你问newNode指针跑哪去了？那说明你还是没有搞懂栈和堆的内存分布，建议补一下os的知识🤔
newNode是函数里的局部变量，也就是说只要函数完成，它就会被一起清出内存，所以这里才没画。
void InsertAtHead(int x){ //插在头部 struct Node myNode;//写成struct Node *myNode;那么第7行就可以改写成return myNode; myNode.data=x; myNode.next=NULL; myNode.prev=NULL; return &myNode;}那就拓展一下吧，如果之前的函数写成这样会发生什么？
假设我们创建了一个地址为50的新节点，注意这个节点的内存地址在stack（栈）里面！
所以一但函数完成，那么栈帧将会被回收！所以即使你有了50的地址，但是那片地址里的东西全被回收了，所以会变成空空如也🤣
这就是为什么我们需要在堆上申请内存。
struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
struct Node *newNode在栈上申请了个地址用于存放指针，来操作堆里面的内容！。
(struct Node*)malloc(sizeof(struct Node));在堆里面申请内存！
当函数结束时，我们会获得堆里面的地址，也就是那个指针所指的地址，这是不会被自动回收的！
2.实现打印
打印和单链表没什么区别
void Print(){ struct Node* temp=head; printf("forward:"); while(temp!=NULL){ printf("%d",temp->data); temp=temp->next; } printf("\n");}3.实现反转打印
void ReversePrint(){ struct Node *temp=head; if(temp==NULL)return;//如果是空链表直接退出 while(temp->next!=NULL){ temp=temp->next; } printf("reverse:"); while(temp!=NULL){ printf("%d",temp->data); temp=temp->prev; } printf("\n");}这个比单链表实现简单多了吧！
部分信息可能已经过时