双链表的概念和结构
双链表的全称叫做：带头双向循环链表
它的结构示意图如下
注意：这⾥的“带头”跟前⾯我们说的单链表的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了读者们更好的理解就直接称为单链表的头结点。
带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”也可以认为是用来占位置滴！！！
双链表的实现
首先先在结构体当中输入需要的数据，则有如下的数据是需要的
结构体中的数据
typedef int LTDataType;//方便对数据类型进行统一的替换
typedef struct ListNode ListNode;//对结构体的名称重新命名交ListNode
struct ListNode
{LTDataType data;ListNode* next;ListNode* prev;
};
则上面的图可以变成这样
双链表新结点的创建及双链表的初始化
ListNode* LTBuyNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//一个结构体的大小if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;//返回头结点
}链表的初始化需要一个创建的新的结点作为哨兵位
//void LTInit(ListNode** pphead)
//{
// //创建一个头结点即“哨兵位”
// *pphead = LTBuyNode(-1);
//}ListNode* LTInit()
{ListNode* phead = LTBuyNode(-1);return phead;
}//上面是两种初始化的方法
//第一种需要传递一个二级指针
在上面的代码当中，我们只需要创建一个头结点来保证第一个“头”存在即可。
插入
第一个参数传一级还是二级，要看phead指向的结点会不会改变
如果发生改变，那么pphead的改变要影响实参，传二级
如果不发生改变，pphead不会影响实参，传一级
双链表的尾插
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//创建需要插入的结点//上面初始化的newnode是头结点，这个newnode是尾插的结点ListNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
上面的顺序是不能改变的，否则无法让新结点找到原来链表的位置
这边测试一下我们的尾插代码依次插入1 2 3 4
双链表的头插
//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}头插和尾插是类似的 ，不过有一个特殊的地方
头插是头插在哨兵位和第一个真正的结点中间
同样的，上面的顺序位置是不能改变的
测试头插代码
这个代码是在上面尾插代码基础上的操作
双链表的尾删
//尾删
void LTPopBack(ListNode* phead)
{assert(phead);assert(!Empty(phead));ListNode* del = phead->prev;ListNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}
这边仍然是在尾插的基础上的操作
这边我们进行了五次尾删，所以代码assert断言了！
将一次尾删注释，下面就是尾删的效果
双链表的头删
//头删
void LTPopFront(ListNode* phead)
{assert(phead);assert(!Empty(phead));ListNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
这个仍然是在尾插的基础上操作的，如果继续删除，跟上面的情况一样assert断言报错
以上就是最基础的增删 ，下面开始加大难度！
双链表中查找数据pos
//找相同数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
这边我们查找的是数据3，所以我们可以找到
这个在链表中没有数据6，所以我们没有找到相关的数据
在pos之后插入结点
这个和尾插以及头插其实是类似的，这里主要是寻找到pos结点，然后插入想要的数据
//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}在3的后面插入数据10
删除pos结点
//删除指定位置节点
void LTErase(ListNode* pos)
{assert(pos);// pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
双链表的销毁
这里我们提供了两种的销毁方法，两种方法基本是类似的
//销毁
void LTDesTroy(ListNode** pphead)
{assert(pphead && *pphead);ListNode* pcur = (*pphead)->next;while (pcur != *pphead){ListNode* next = pcur->next;free(pcur);pcur = next;}//销毁哨兵位结点free(*pphead);*pphead = NULL;pcur = NULL;
}
//为了更好的记忆，我们让销毁也传递一级指针
void LTDesTroy2(ListNode* phead)//传一级，需要手动将plist置为NULL
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = pcur = NULL;
}最后我们将双向链表的源码附上
list.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode ListNode;
struct ListNode
{LTDataType data;ListNode* next;ListNode* prev;
};ListNode* LTBuyNode(LTDataType x);
//为了保存接口的一致性
//
//初始化
//void LTInit(ListNode** pphead);
ListNode* LTInit(); //
void LTPrint(ListNode* phead);bool Empty(ListNode* phead);//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级//尾插
void LTPushBack(ListNode* phead, LTDataType x);//头插
void LTPushFront(ListNode* phead, LTDataType x);//尾删
void LTPopBack(ListNode* phead);//头删
void LTPopFront(ListNode* phead);//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x);//删除指定位置的结点
void LTErase(ListNode* pos);//找数据
ListNode* LTFind(ListNode* phead, LTDataType x);//销毁
void LTDesTroy(ListNode** pphead);
void LTDesTroy2(ListNode* phead);//传一级，需要手动将plist置为NULLList.c
#include"List.h"ListNode* LTBuyNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}
//初始化//void LTInit(ListNode** pphead)
//{
// //创建一个头结点即“哨兵位”
// *pphead = LTBuyNode(-1);
//}
ListNode* LTInit()
{ListNode* phead = LTBuyNode(-1);return phead;
}//打印
void LTPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}bool Empty(ListNode* phead)
{assert(phead);return phead->next == phead;
}//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//创建需要插入的结点ListNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(ListNode* phead)
{assert(phead);assert(!Empty(phead));ListNode* del = phead->prev;ListNode* prev = del->prev;prev->next = phead;phead->prev = prev;free(del);del = NULL;
}//头删
void LTPopFront(ListNode* phead)
{assert(phead);assert(!Empty(phead));ListNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}
//找相同数据
ListNode* LTFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在pos之后插入结点
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除指定位置节点
void LTErase(ListNode* pos)
{assert(pos);// pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDesTroy(ListNode** pphead)
{assert(pphead && *pphead);ListNode* pcur = (*pphead)->next;while (pcur != *pphead){ListNode* next = pcur->next;free(pcur);pcur = next;}//销毁哨兵位结点free(*pphead);*pphead = NULL;pcur = NULL;
}void LTDesTroy2(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = pcur = NULL;
}test.c
#include"List.h"
void test()
{创建双向链表变量//ListNode* plist = NULL;//LTInit(&plist);ListNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);ListNode* pos = LTFind(plist, 3);LTInsert(pos, 10);LTPrint(plist);pos = LTFind(plist, 3);LTErase(pos);LTPrint(plist);/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);*//*LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);LTPushFront(plist, 4);LTPrint(plist);*//*LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);*//*if (pos == NULL){printf("没有找到\n");}else{printf("找到了\n");}*/LTDesTroy(&plist);//LTDesTroy2(plist);//plist = NULL;}int main()
{test();return 0;
}
