双向链表-

链表特性：带头/不带头

循环/非循环

--->排列组合后，共有8种链表结构

一.双向链表的定义

前一个节点存了后一个节点的地址，后一个节点也存了前一个节点的地址，即循环链表

二.代码解析

//双向链表
//与非循环链表区别！该双向链表事先设置了一个哨兵位节点，所以不用传入二级指针，即可改变链表里面的内容
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;
//1.定义链表结构
typedef int LTDateType;//适用于多类型(eg:int)
typedef struct ListNode
{LTDateType data;//链表中储存的数据struct ListNode* prev;//指向节点的前一个节点struct ListNode* next;//指向节点的后一个节点
}LTNode;

//2.初始化链表
//法1，传入二级指针，同非循环链表,即void ListInit(LTNode**pphead);
//法2，设置哨兵位头节点
LTNode* ListInit()
{//设置哨兵位头节点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//循环链表phead->next = phead;phead->prev = phead;return phead;
}

//3.打印链表
void ListPrint(LTNode* phead)
{//循环链表，从head的下一个节点开始打印assert(phead);//链表不能为空//head是哨兵位节点，是空的，所以不打印LTNode* cur = phead->next;while (cur!=phead){cout << cur->data<<"->";cur = cur->next;}cout << endl;
}

//4.尾插
//已经创建了一个哨兵位头节点，所以尾插不需要传入二级指针
void ListPushBack(LTNode* phead,LTDateType x)
{//断言，链表不为空assert(phead);//创建一个新的节点LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data=x;//在新创建的节点中插入数据//LTNode* newnode=BuyListNode(x);LTNode* tail = phead->prev;//定义一个变量指向链表的尾部tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

//5.尾删
void ListPopBack(LTNode* phead)
{//断言，链表不为空assert(phead);//防止删除掉创建的哨兵位节点assert(phead->next != phead);//法1//LTNode* tail = phead->prev;//指向链表的尾节点//tail->prev->next = phead;//phead->next = tail->prev;//free(tail);//法2,多定义几个变量LTNode* tail = phead->prev;//尾节点LTNode* tailPrev = tail->prev;//尾节点的前一个节点free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}

LTNode* BuyListNode(LTDateType x)//用于创建新的节点
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;//滞空newnode->prev = NULL;//滞空return newnode;
}

//6.头插
void ListPushFront(LTNode* phead, LTDateType x)
{//注意插入的位置！//在哨兵位节点和第一个位置之间插入数据assert(phead);//由于每次都要检查扩展一个新的节点，所以设置一个函数专门用于扩展LTNode* newnode = BuyListNode(x);//创建好节点后，开始进行插入操作//找到哨兵位头节点后真正的第一个节点LTNode* next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;
}

//7.头删
void ListPopFront(ListNode* phead)
{assert(phead);//防止将哨兵位节点删掉assert(phead->next != phead);//定义多个变量，增加程序的可读性LTNode* next = phead->next;//要删除的头部节点LTNode* nextNext = next->next;//头数据的下一个节点phead->next = nextNext;nextNext->prev = phead;//要记得将删除的头部节点的内存还给系统free(next);
}

//8.查找
//根据传进来的数字在链表中查找是否有相同的
LTNode* ListFind(LTNode* phead,LTDateType x)
{assert(phead);//从哨兵位节点的下一个节点开始查找LTNode* cur = phead->next;//限定范围，即何时停止查找while (cur!= phead){if (cur->data == x){return cur;}else{cur = cur->next;}}//未查找到return NULL;
}

//9.pos位置前插入
void ListInsert(LTNode* pos,LTDateType x)//可直接代替头插和尾差,即直接在这两个函数体中调用该函数
{assert(pos);//创建一个新节点LTNode* newnode = BuyListNode(x);//创建一个变量指向pos位置前的一个节点LTNode* posPrev = pos->prev;posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

//10.删除pos位置
void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;
}

//11.销毁链表
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;//先释放除哨兵位头结点以外的节点，再单独销毁哨兵位头节点while (cur != phead){LTNode* next = cur->next;//先保存下一个节点的地址，防止被置成随机值后找不到free(cur);cur = next;}free(phead);phead = NULL;//不能使plist清理干净，可在测试类中手动清理
}

每写一个功能，都要进行一次测试，以下为所有的测试类合集：

//测试类
void Test()
{//初始化LTNode* plist = ListInit();//尾插cout << "尾插测试:" << endl;ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);cout << "---------------" << endl;//尾删cout << "尾删测试:" << endl;ListPopBack(plist);ListPopBack(plist);ListPrint(plist);cout << "---------------" << endl;cout << "头插测试:" << endl;ListPushFront(plist, 3);ListPushFront(plist,4);ListPushFront(plist, 5);ListPrint(plist);cout << "---------------" << endl;cout << "头删测试:" << endl;ListPopFront(plist);ListPrint(plist);cout << "---------------" << endl;cout << "查找测试:(修改数值)" << endl;LTNode* pos = ListFind(plist,4);//利用查找修改数值if (pos){pos->data = 7;}ListPrint(plist);cout << "---------------" << endl;cout << "在pos位置前插入测试:" << endl;//配合查找，插入数据LTNode* search = ListFind(plist, 1);//即在1的前面插入节点ListInsert(search, 9);ListPrint(plist);cout << "---------------" << endl;cout << "删除pos位置节点测试:" << endl;LTNode* search2 = ListFind(plist, 2);ListErase(search2);ListPrint(plist);cout << "---------------" << endl;//销毁链表ListDestroy(plist);plist = NULL;ListPrint(plist);
}
int main()
{Test();return 0;
}

以下为运行测试类时的最终结果：（因最终链表销毁，故无法进行打印，assert自动截止）