一、概念与结构

这里的双向链表是指带头的的双向循环链表，这里的“带头”和之前所说的“头结点”是两个概念，带头链表里的头结点，实际是“哨兵位”。哨兵位节点不存储任何有效元素，只是起一个“站岗放哨”的作用。和单链表一样，双向链表也是由一个一个的结点组成，但这里的结点由三个部分组成：保存的数据+指向下一个节点的指针+指向前一个节点的指针。

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

注：当单链表为空时，指向第一个结点的指针为空；当双向链表为空时，链表中只有一个头结点~

二、双向链表的实现

1、初始化

双向链表的初始化有两种方式，这里更推荐使用第二种。

第一种：

void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);
}

第二种：

LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

2、尾插

尾插这里的参数要注意传的是一级指针而不是二级指针，因为我们在初始化时给头结点申请了一块空间（假设这块空间的地址是0x339），尾插操作改变的只是头结点的prev指针和next指针的值，并没有修改头结点的地址。那为什么之前的单向链表传的是二级指针呢？单链表的第一个结点phead初始情况下为NULL，现在向单链表中尾插一个结点（假设该结点的地址是0x300）。此时phead的值从NULL变为了0x300，phead的值发生了改变，所以传的是二级指针。

在尾插操作中，需要修改的就是头结点，尾结点和新插入的结点。对于新节点来说，我们需要修改prev和next指针，对于头结点要修改prev，尾结点要修改next。在双向链表中，我们不用遍历整个链表来找到尾结点，因为可以直接通过头结点的prev指针来找到尾结点。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead   phead->prev(尾结点)   newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

3、头插

头插是在第一个结点之前插入新节点，而不是在头结点之前插入。

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead  newnode  phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

4、尾删

进行删除操作之前，首先要判断双向链表是否为空。

//只有一个头节点的情况下，双向链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead  del->prev  delphead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}

5、头删

//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead  del  del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

6、在指定位置之后插入结点

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos  newnode  pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

7、删除指定位置的结点

//删除pos位置的结点
void Erase(LTNode* pos)
{assert(pos);//pos->prev  pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

三、完整参考代码

List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>//双向链表的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead);//双向链表的初始化
//void LTInit(LTNode** pphead);LTNode* LTInit();//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的结点
void LTErase(LTNode* pos);//传二级:违背接口一致性
//void LTDestroy(LTNode** pphead);
//传一级:调用完成之后将实参手动置为NULL(推荐)
void LTDestroy(LTNode* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "List.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//双向链表的初始化
//void LTInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = LTBuyNode(-1);
//}LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead   phead->prev(尾结点)   newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead  newnode  phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//只有一个头节点的情况下，双向链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead  del->prev  delphead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead  del  del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没找到return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos  newnode  pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置的结点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev  pos  pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "List.h"void test01()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPopBack(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);LTNode* find = LTFind(plist, 3);LTErase(find);LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{test01();return 0;
}