一.前言
嗨嗨嗨，大家好久不见！前面我们已经通过数组实现数据的增删查改、单链表实现数据的增删查改，现在让我们尝试一下使用双链表实现数据的增删查改吧！
二.正文
如同往常一样，对于稍微大点的项目来说，我们使用多文件操作更好一些。
List.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
struct ListNode
{
DataType data;
struct ListNode* prev;
struct ListNode* next;
};
typedef struct ListNode ListNode;
void ListInit(ListNode** pphead);//双向链表初始化
void ListDestroy(ListNode* phead);//双向链表销毁
void ListPrint(ListNode* phead);//双向链表打印
void ListPushBack(ListNode* phead, DataType x);//双向链表尾部插入节点
void ListPushFront(ListNode* phead, DataType x);//双向链表第一个有效节点前插入节点（即哨兵位的后一个节点为第一个有效节点）
void ListPopBack(ListNode* phead);//双向链表删除尾部节点
void ListPopFront(ListNode* phead);//双向链表删除第一个有效节点
void ListInsert(ListNode* pos, DataType x);//双向链表指定位置之后插入节点
void ListErase(ListNode* pos);//双向链表指定位置之后删除节点
ListNode* ListFind(ListNode* phead, DataType x);//查找目标节点我们首先定义了这个项目的头文件，并把其他函数实现过程中可能使用的头文件包含在List.h中，这样就可以方便代码的维护，并且减少冗余的代码。
这是我们的双向链表结构体的定义：
struct ListNode
{
DataType data;
struct ListNode* prev;
struct ListNode* next;
};和单链表区分的话，那就是单链表定义的结构体中没有指向前一个节点的prev。
下面是我们在实现整个项目中，各种功能的罗列，就类似于书的目录一样。
void ListInit(ListNode** pphead);//双向链表初始化
void ListDestroy(ListNode* phead);//双向链表销毁
void ListPrint(ListNode* phead);//双向链表打印
void ListPushBack(ListNode* phead, DataType x);//双向链表尾部插入节点
void ListPushFront(ListNode* phead, DataType x);//双向链表第一个有效节点前插入节点（即哨兵位的后一个节点为第一个有效节点）
void ListPopBack(ListNode* phead);//双向链表删除尾部节点
void ListPopFront(ListNode* phead);//双向链表删除第一个有效节点
void ListInsert(ListNode* pos, DataType x);//双向链表指定位置之后插入节点
void ListErase(ListNode* pos);//双向链表指定位置之后删除节点
ListNode* ListFind(ListNode* phead, DataType x);//查找目标节点List.c
#include"List.h"
ListNode* ListBuyNode(DataType x)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)
{
perror("malloc fail!");
return NULL;
}
node->next = node;//值得注意的是在创造新节点的时候，双向链表和单链表不同的是，单链表的next要指向NULL
node->prev = node;//而双向链表需要前后指针，即prev和next都要指向自己，构成循环。
node->data = x;
return node;
}
void ListInit(ListNode** pphead)
{
*pphead = ListBuyNode(0);
}
void ListPushBack(ListNode* phead,DataType x)
{
assert(phead);//双向链表的哨兵位phead不可能为NULL,如果phead都是NULL了，那么这个链表就不是双向链表。
ListNode* newnode = ListBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev-> next = newnode;
phead->prev = newnode;
}
void ListPrint(ListNode* phead)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void ListPushFront(ListNode* phead,DataType x)
{
assert(phead);
ListNode* newnode = ListBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void ListPopBack(ListNode* phead)
{
assert(phead && phead->next != phead);
ListNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
void ListPopFront(ListNode* phead)
{
assert(phead&&phead->next!=phead);
ListNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
ListNode* ListFind(ListNode* phead,DataType x)
{
ListNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void ListInsert(ListNode* pos,DataType x)
{
ListNode* newnode = ListBuyNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->prev = newnode;
pos->next = newnode;
}
void ListErase(ListNode* pos)
{
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
void ListDestroy(ListNode* phead)//值得注意的是因为这里我们传的的是一级指针，
//所以在这里phead的改变，不会影响实参plist的改变，因此在主函数中我们需要主动让plist=NULL。
//在这里我们也可以传二级指针ListNode** pphead，这样*pphead的改变就可以影响实参plist的改变了。
{
ListNode* pcur = phead;
ListNode* next = pcur->next;
while (pcur != phead)
{
free(pcur);
pcur = next;
next = next->next;
}
free(phead);
}上面的代码中，个别函数有些地方的关键点我有注释，有兴趣的小伙伴可以看一下。
test.c
#include"List.h"
//void test1()//测试双向链表初始化和创造节点
//{
// ListNode* plist = NULL;
// ListInit(&plist);
//}
//void test2()//测试双向链表尾插节点以及双向链表的打印
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPrint(plist);
//}
//void test3()//测试打印双向链表
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushFront(plist, 1);
// ListPushFront(plist, 2);
// ListPushFront(plist, 3);
// ListPushFront(plist, 4);
// ListPrint(plist);
//}
//void test4()//测试尾删
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPopBack(plist);//删一次
// ListPopBack(plist);//删两次
// ListPopBack(plist);//三次
// ListPopBack(plist);//四次，下一次再删除会报错
// ListPrint(plist);
//}
//void test5()//测试头删
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPrint(plist);
// ListPopFront(plist);//删一次
// ListPrint(plist);
// ListPopFront(plist);//2
// ListPrint(plist);
// ListPopFront(plist);//3
// ListPrint(plist);
// ListPopFront(plist);//4,下一次再删除会报错
// ListPrint(plist);
//}
//void test6()//测试查找目标数据节点、指定节点之后插入数据、删除指定节点
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListNode* find = ListFind(plist, 1);
// if (find == NULL)
// printf("没找到\n");
// else
// printf("找到了，地址是%p\n", find);
// ListErase(find);
// ListPrint(plist);
//}
void test7()//链表的销毁
{
ListNode* plist = NULL;
ListInit(&plist);
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListDestroy(plist);
ListPrint(plist);
plist = NULL;
}
int main()
{
//test1();//测试双向链表初始化和创造节点
//test2();//测试双向链表尾插节点以及双向链表的打印
//test3();//测试打印双向链表
//test4();//测试尾删
//test5();//测试头删
//test6();//测试查找目标数据节点、指定节点之后插入数据、删除指定节点
test7();//链表的销毁
return 0;
}上面的代码，是我在测试函数功能是否正常所写的代码。小伙伴们看看就行。
三.结言
关于如何通过双向链表实现数据的增删查改就讲到这里了，帅哥美女们，我们下次再见，拜拜。
