之前我们已经了解并实现了单链表，我们发现单链表实现头插头删还行，但是尾插尾删什么的需要遍历链表，使得时间复杂度增加，效率不是那么好，那么有没有改进的办法呢？

今天，我们就来了解并实现一下双链表。

我们知道，单链表是有一个结构体指针指向下一个节点，如图：

那么双链表，顾名思义，指针指向双向，两个结构体指针，分别指向下一个节点和前一个节点。 

接下来就来实现双链表：

新建一个头文件：List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;//定义数据类型，方便后期修改
typedef struct ListNode {struct ListNode* prev;struct ListNode* next;LTDataType data;
}LTNode;void ListPrint(LTNode* pos);//打印链表用于测试LTNode* BuyListNode(LTDataType x);//开辟一个节点，返回节点地址LTNode* ListInit();//初始化链表void ListInsert(LTNode* pos, LTDataType x);//在pos位置之前插入void ListErase(LTNode* pos);//删除pos位置节点void ListDestory(LTNode* phead);//销毁链表，释放内存LTNode* ListFind(LTNode* phead, LTDataType x);//查找链表中是否有值为X的节点

然后就是各函数的实现：List.c

#include"List.h"void ListPrint(LTNode* pos)
{assert(pos);LTNode* cur = pos->next;while (cur != pos){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL) {perror("BuyListNode::malloc::");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}LTNode* ListInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);newnode->next = pos;newnode->prev = prev;prev->next = newnode;pos->prev = newnode;}void ListErase(LTNode* pos)
{assert(pos);LTNode* next = pos->next;LTNode* prev = pos->prev;prev->next = next;next->prev = prev;free(pos);
}LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;ListErase(cur);cur = next;}free(phead);phead = NULL;
}