1.带头双向循环链表
带头链表的头结点实际为“哨兵位 ”，哨兵位节点不存储任何有效元素，只是再放哨。
带头链表中，除了头结点，其他节点都存储有效得的数据。
实际中我们用的最多的还是单链表、和双向链表（带头双向循环链表）。
双向链表的节点结构：数据+指向后面节点的指针+指向前面节点的指针
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//双向链表的创建
typedef int LTdatatyp;
typedef struct ListNode
{
LTdatatyp data;
struct ListNode* next;//指向后面
struct ListNode* prev;//前面节点
}LTNode ;1.1双向链表的初始化
大家来思考一下这里的双向链表能不能为空，
答案是不能，
来猜测一下这样写是正确的吗？
因为next 和perv都要指向一个节点所以为NULL是不可以的。这里让他们指向newnode即可
当双向链表为空的时候：只有一个节点就是头结点。
下面调试一下来看看哨兵创建成功没。
1.2双向链表的尾插
传一级 或者二级指针是要看phead是否会改变，改变传地址 用** 接收， 不改变传一直指针即可。
尾插大概可以这样来修改next 、prev节点
代码大概是这样的，下面我们来测试一下
1.3双向链表的头插
这里的头插不是在哨兵位头插，而是在哨兵位后面进行头插。
下面的代码就是头插，
大概就是这样
1.4双向链表的打印
打印的结果就如下
1.5双向链表的尾删
这里的图可以了解一下。
上面的LTEmpty 是链表不为空
尾删后的结果如下：
1.6双向链表的头删
1.7 双向链表的查找
双向链表的查找和前面的单链表的查找类似，
1.8在pos位置之后插入节点
下面是在3的后面插入23
1.9删除pos位置的结点
Find 返回的值是3 ，删除的值就是3
销毁链表
大家可以进行调试来看看链表的销毁
那么讲到这里的话我们的双向链表就结束了。加油！！
List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
//双向链表的创建
typedef int LTdatatyp;
typedef struct ListNode
{
LTdatatyp data;
struct ListNode* next;//指向后面
struct ListNode* prev;//前面节点
}LTNode ;
//初始化
void ListInit(LTNode** pphead);
//创建新的空间
LTNode* LTBuyNode(LTdatatyp x);
//尾插
void LTPushback(LTNode* phead,LTdatatyp x);
//头插
void LTPushFront(LTNode* phead, LTdatatyp x);
//打印
void LTPrint(LTNode* phead);
//
bool LTEmpty(LTNode* phead);
//尾删
void LTPopback(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找数据
LTNode* LTFind(LTNode* phead, LTdatatyp x);
//pos后插入数据
void LTInsert(LTNode* pos, LTdatatyp x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁链表
void LTDesTroy(LTNode** pphead);List.c
#include "List.h"
LTNode* LTBuyNode(LTdatatyp 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 ListInit(LTNode** pphead)
{
//创建一个头节点（哨兵位）
*pphead = LTBuyNode(-1);
}
//尾插
void LTPushback(LTNode* phead,LTdatatyp x)//这里的插入为什么不用 * *phead 呢 这是因为头结点不会改变，
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead;// newnode的next 与phead连接
newnode->prev = phead->prev;//与 最后一个数据连接newnode的 头指针
phead->prev->next = newnode; //插入newnode
phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTdatatyp x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead ->next;//这里的pcur不能等于哨兵点
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//判断有效数据的第一个是否为空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
//尾删
void LTPopback(LTNode* phead)
{
assert(phead);
assert(! LTEmpty(phead));
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
//查找数据
LTNode* LTFind(LTNode* phead, LTdatatyp x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)//pcur不等于头指针
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
//pos后插入数据
void LTInsert (LTNode* pos, LTdatatyp x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next = newnode;
pos->next->prev = newnode;
}
//删除指定位置pos节点
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos =NULL;
}
//销毁链表
void LTDesTroy(LTNode** pphead)
{
assert(pphead &&*pphead );//头结点也不能为空
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* Next = pcur->next;
free(pcur);
pcur = Next;
}
//销毁头结点
free(*pphead);
*pphead = NULL;
pcur = NULL;
}text.c
#include "List.h"
void Listext01()
{
LTNode* plist = NULL;
ListInit(&plist);
//尾插
LTPushback(plist, 1);
LTPushback(plist, 2);
LTPushback(plist, 3);
LTPushback(plist, 4);
//头插
/*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);*/
//头删
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
LTPrint(plist);
//查找
LTNode* Find = LTFind(plist, 4);
//if (Find == NULL)
//{
// printf("找不到了\n");
//}
//else
// printf("找到了\n");
//指定位置后插入
//LTInsert(Find, 23);
//LTPrint(plist);
//删除指定位置数据
//LTErase(Find);
//LTPrint(plist);
//销毁链表
LTDesTroy(&plist);
LTPrint(plist);
LTDesTroy(&plist);
LTPrint(plist);
LTDesTroy(&plist);
LTPrint(plist);
LTDesTroy(&plist);
LTPrint(plist);
}
int main()
{
Listext01();
return 0;
}