特点：
- 结构：指向前一结点指针+数据+指向后一结点指针
- 由于循环，尾结点的下一结点next指向头结点（哨兵结点）
- 空的双向链表只有自循环的哨兵结点（头结点）
模拟实现双向链表
LIST.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//定义双向链表结构
typedef int LTDataType;//链表数据类型
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化
void LTInit(LTNode** pphead);
LTNode* LTInit2();//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead);
void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL//打印链表
void LTPrint(LTNode* phead);//尾插数据
//第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//我们通过传递的一级指针来找到头结点，就可以找到之后的节点了//那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x);//头插数据
void LTPushFront(LTNode* phead, LTDataType x);//尾删数据
void LTPopBack(LTNode* phead);//头删数据
void LTPopFront(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//删除指定位置的节点
void LTIErase(LTNode* pos);
LIST.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"LIST.h"//创建结点
LTNode* buyNode(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) {//创建一个哨兵结点（头结点）*pphead = buyNode(-1);
}
//初始化2 返回值初始化
LTNode* LTInit2() {LTNode* phead = buyNode(-1);return phead;
}//销毁 链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead) {//哨兵位不能先销毁！assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;//从哨兵位的下一结点开始遍历销毁while (pcur != (*pphead)) {LTNode* Next = pcur->next;//创建pcur下一结点，方便遍历销毁free(pcur);pcur = Next;}//跳出循环，说明哨兵位之后的全销毁了//现在释放销毁哨兵位free(*pphead);*pphead = pcur = NULL;
}//初次错误示范！！
void LTDesToryError(LTNode** pphead) {LTNode* pcur = (*pphead)->next;LTNode* Next = pcur->next;while (pcur!=*pphead) {free(pcur);pcur = Next;Next = Next->next;}pcur = Next = NULL;
}//void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL//打印链表
void LTPrint(LTNode* phead) {LTNode* pcur = phead->next;//记住第一个结点！！是哨兵位下一个结点！while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾插数据
//第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//我们通过传递的一级指针来找到头结点，就可以找到之后的节点了//那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//哨兵位 phead 新结点 newnode 尾结点pcur(phead->prev)LTNode* pcur = phead->prev;LTNode* newnode = buyNode(x);//newnode的指针修改，prev指向上个尾节点，next指向哨兵位newnode->prev = pcur;newnode->next = phead;//原先的尾节点next指针->哨兵位，现在next->newnode//哨兵位的prev原本->尾节点,现在让prev->newnodepcur->next = newnode;phead->prev = newnode;
}//头插数据
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//哨兵位phead 新结点newnode 第一个结点 pcur(phead->next)LTNode* newnode = buyNode(x);LTNode* pcur = phead->next;//插入newnode，prev指向哨兵位，next指向pcurnewnode->prev = phead;newnode->next = pcur;//哨兵位的next，原头结点的prev，分别指向newnodephead->next = newnode;pcur->prev = newnode;
}
//————————ERROR！！注意！！！删除要检查链表是否为空！！——————————
//判断链表是否为空
bool LTEmpty(LTNode* phead) {assert(phead);//error!!! return phead == NULL;不是判断哨兵位phead！！第一个结点是哨兵位下一结点！phead->next!return phead->next == phead;//如果哨兵位next指向自己，说明是自循环的只有哨兵位的空链表！
}//链表为空，返回true
//尾删数据
void LTPopBack(LTNode* phead) {assert(phead);//哨兵位不得为空assert(!LTEmpty(phead));//链表不得为空//哨兵位phead 尾结点 del(phead->prev) 尾结点前一结点 del->prevLTNode* del = phead->next;//删除尾结点 哨兵位的prev指向del->prev, 尾结点的前一结点的next->哨兵位del->prev->next = phead;//注意这俩行代码不可调换！phead->prev = del->prev;//先改了头结点的指向 del也会跟着改！//删除完之后释放delfree(del);del = NULL;
}//头删数据
void LTPopFront(LTNode* phead) {assert(phead);assert(!LTEmpty(phead));//哨兵位phead 要删除的第一个结点del(phead->next) 新的第一结点del->nextLTNode* del = phead->next;//删除结点 哨兵位的next指向新第一结点 新的第一结点的prev指向哨兵位del->next->prev = phead;phead->next = del->next;//释放delfree(del);del = NULL;
}//查找数据
//遍历链表，直至再次遇到哨兵位（找一圈了没找到就是没有）
LTNode* LTFind(LTNode* phead, LTDataType x) {LTNode* pcur = phead->next;//记住从第一个结点！不是phead！while (pcur != phead) {//找到了if (pcur->data == x) {return pcur;}pcur = pcur->next;}//遍历循环找了一圈，没找到return NULL;
}
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x) {//创建一个新结点LTNode* newnode = buyNode(x);//pos newnode pos->next//先安newnodenewnode->next = pos->next;newnode->prev = pos;//先连接pos后面的，再连pospos->next->prev = newnode;pos->next = newnode;
}//删除指定位置的节点
void LTIErase(LTNode* pos) {assert(pos);//传过来的位置不为空/*pos前面的节点pos->prevpos后面的节点pos->next删除pos影响这两个节点pos前面指针的节点的next指针->Pos后面的节点pos后面的节点的prev指针就->pos前面的节点*///pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
