目录
1.为什么要研究双链表
在单链表中提到过，链表相对于顺序表的劣势在于在进行定向的插入删除的时候很困难，需要从头结点开始向后遍历，直到找到要目标节点，才能进行插入和删除，原因在于从一个节点只能找到它的下一个元素而不能找到它的前一个元素。
双链表与单链表的区别就在于通过一个元素既可以找到它的前一个元素，也可以找到它的后一个元素，使插入和删除更加方便，为了更方便找到链表尾部，并且每一个节点的建立一致，我们使用循环结构，但同时每一个节点还需要多存储一个指针。为了避免使用二级指针的麻烦，这里的双链表是带有头结点的。
2.双链表的结构
1.逻辑结构
?注意头结点中是不存放任何数据的。
逻辑结构是抽象出来的，方便理解的结构。
2.物理结构
物理结构是内存中实际存储的结构，每一个节点都会存储它的前一个节点的地址和后一个节点的地址。
3.基本函数
1.初始化链表
LTNode* ListInit()
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));//建立一个头节点
node->next = node;
node->prev = node;//节点的next与prev都指向它自身
return node;
}链表的初始化就是建立一个头结点。头结点中不存储任何数据，只是为了避免二级指针的麻烦，我们的每一次传参传的都是头指针，在函数中改变形参的时候是无法改变实参的，但如果通过这个头指针改变链表中的其他元素（因为存的都是地址）是可以的，头指针不存储任何数据，所以是否改变其实无所谓，这也是有头指针的好处。
2.开辟一个节点
LTNode* BuyListNode(DataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->data = x;
node->prev = NULL;
node->next = NULL;//将两个指针都先初始化为空
return node;
}开辟一个节点接收数据的值data，然后将其两个指针暂时初始化为空。
3.打印链表
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)//定义一个cur来遍历整个链表
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");//当cur为头节点时换行，这里避免了对头结点data的打印
}注意对头结点的data不被打印的处理，当cur为phead时，退出循环，直接进行换行。
4.销毁链表
void ListDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead;
LTNode* next = phead->next;
while (cur != phead)
{
free(cur);
cur = next;
next = next->next;
}//遍历链表逐个删除
free(phead);
phead = NULL;//注意这里只是将形参置为空，实参的部分需要人工置为空
}特别注意最后一步，只是将建立的phead的形参变为了空，但是实参并没有改变，需要在工程文件中人工将其置为空。
4.尾插与尾删
1.尾插
void ListPushBack(LTNode* phead, DataType x)
{
assert(phead);//断言
LTNode* newnode = BuyListNode(x);//建立一个新节点
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;//将新节点插入
}尾插操作就是先通过头结点找到链表的尾，然后再头与尾之间插入一个元素，即可。
2.尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
tailprev->next = phead;
phead->prev = tailprev;//尾结点前一个元素与头结点建立关系
free(tail);
}依然是通过头节点找尾结点，将尾结点前一个节点与头结点建立关系即可，最后将尾结点释放。
5.头删与头插
1.头插
void ListPushFront(LTNode* phead, DataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* next = phead->next;
phead->next = newnode;
newnode->next = next;
next->prev = newnode;
newnode->prev = phead;新节点分别与头结点和头结点下一个节点建立关系
}即在头结点之后插入一个元素，即将该元素与头结点的下一个节点和头结点之间分别建立关系。
2.头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next!=phead);
LTNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;//头结点与该节点的下一个节点建立关系
free(next);
}同理，无论是插入还是删除，都是通过头结点找到被改变的元素然后看哪几个节点需要建立关系即可，与单链表是一样的。
6.定向插入删除
1.查找
LTNode* ListFind(LTNode* phead, DataType x)
{
assert(phead);
LTNode* cur = phead->next;
while(cur!=phead)
{
if (cur->data == x)
{
return cur;//遍历链表，如果找到则返回该节点
}
cur = cur->next;
}
return NULL;//没找到则返回空指针
}由于要进行定向插入和删除，所以我们首先需要通过查找来找到该节点，然后向插入删除的函数中传入该节点。
2.在pos前插入
void ListInsert(LTNode* pos, DataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* prev = pos->prev;
pos->prev = newnode;
newnode->prev = prev;
prev->next = newnode;
newnode->next = pos;//找到pos前的节点建立关系即可
}即在pos和pos前的节点之间插入一个节点，我们只需要建立这个节点与二者之间的关系即可。
3.删除pos
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;//建立pos前的节点和pos后的节点之间的关系即可
}对pos节点之前的元素和之后的元素建立关系即可。
7.全部代码
1.List.h文件
#pragma once
#include<stdio.h>
#include<assert.h>
#define DataType int
typedef struct LTNode {
DataType data;
struct LTNode* prev;
struct LTNode* next;
}LTNode;
LTNode* ListInit();
LTNode* BuyListNode(DataType x);
void ListPrint(LTNode* phead);
void ListDestroy(LTNode* phead);
void ListPushBack(LTNode* phead, DataType x);
void ListPopBack(LTNode* phead);
void ListPushFront(LTNode* phead, DataType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, DataType x);
void ListInsert(LTNode* pos, DataType x);//在前面插入
void ListErase(LTNode* pos);
2.List.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"LTNode.h"
LTNode* ListInit()
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->next = node;
node->prev = node;
return node;
}
LTNode* BuyListNode(DataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->data = x;
node->prev = NULL;
node->next = NULL;
return node;
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void ListDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead;
LTNode* next = phead->next;
while (cur != phead)
{
free(cur);
cur = next;
next = next->next;
}
free(phead);
phead = NULL;
}
void ListPushBack(LTNode* phead, DataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
}
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* tail = phead->prev;
LTNode* tailprev = tail->prev;
tailprev->next = phead;
phead->prev = tailprev;
free(tail);
}
void ListPushFront(LTNode* phead, DataType x)
{
assert(phead);
LTNode* newnode = BuyListNode(x);
LTNode* next = phead->next;
phead->next = newnode;
newnode->next = next;
next->prev = newnode;
newnode->prev = phead;
}
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next!=phead);
LTNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
free(next);
}
LTNode* ListFind(LTNode* phead, DataType x)
{
assert(phead);
LTNode* cur = phead->next;
while(cur!=phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, DataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* prev = pos->prev;
pos->prev = newnode;
newnode->prev = prev;
prev->next = newnode;
newnode->next = pos;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
3.test.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"LTNode.h"
void menu()
{
printf("****1.尾插********2.尾删****\n");
printf("****3.头插********4.头删****\n");
printf("****5.前插********6.删除****\n");
printf("****0.销毁双链表************\n");
}
int main()
{
LTNode* phead=ListInit();
ListPushBack(phead, 1);
ListPushBack(phead, 2);
ListPushBack(phead, 3);
ListPushBack(phead, 4);
ListPushBack(phead, 5);
ListPrint(phead);
int input = 0;
do {
menu();
scanf("%d", &input);
int x;
int y;
switch (input)
{
case 1:scanf("%d", &x);
ListPushBack(phead, x);
ListPrint(phead);
break;
case 2:ListPopBack(phead);
ListPrint(phead);
break;
case 3:scanf("%d", &x);
ListPushFront(phead, x);
ListPrint(phead);
break;
case 4:ListPopFront(phead);
ListPrint(phead);
break;
case 5:scanf("%d", &x);
LTNode* pos = ListFind(phead,x);
scanf("%d", &y);
ListInsert(pos, y);
ListPrint(phead);
break;
case 6:scanf("%d", &x);
LTNode* pos2 = ListFind(phead, x);
ListErase(pos2);
ListPrint(phead);
break;
case 0:ListDestroy(phead);
phead = NULL;
break;
default:printf("wrong type!\n");
break;
}
} while (input);
return 0;
}8.测试结果
1.尾插：成功。
2.尾删至删空报错：成功。
3.头插：成功。
4.头删至删空报错：成功。
5.查找不在表中的元素报错：成功。
6.定向插入：成功。
7.定向删除至删空：成功。
综上，代码测试成功。
9.总结
本来想写一个前言的，但是发现好像没啥可讲的，前言基本包含在为什么使用双向链表里了，双向链表的优势对于单链表来说还是很明显的，但大部分的OJ题里还是单链表的多，其实我认为这两种链表的思考方式都是一样的，首先寻找在进行了操作之后哪些节点发生了改变，然后将这些节点记录下来重新相连即可。如果代码对你有帮助，或者你是一个白嫖党欢迎给作者一键三连啊~