双向链表

链表分类 8种 (带头/不带头 单向/双向 循环/循环)
最常用两种 单链表(不带头单向不循环链表) 双向链表（带头双向循环链表）

双链表有 头节点（哨兵位） 后继指针(next) 前驱指针(prev)

双向链表为空时，为一个哨兵位

同样采用多文件操作

1.申请节点

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//申请不成功{perror("malloc fail");exit(1);//给非0值}node->data = x;node->next = node->prev = node;return node;
}

2.链表初始化

void LTInit(LTNode** pphead)
{//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);//随便赋一个值
}

3.尾插

以上图为例 尾插时 head->prev指向的就是d3

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;//也就是newnode->prev指向d3newnode->next = phead;phead->prev->next = newnode;//d3的next指针指向新节点phead->prev = newnode;
}

4.打印链表

让pcur指向phead的next指针，然后遍历链表，直到pcur=phead

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

5.头插

头插是插到头结点与d1之间，插在头结点前边跟尾插一样(因为链表是双向循环的)

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;//先改影响小的phead->next = newnode;}

6.尾删

void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;}

7.头删

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

8.查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

9.指定位置插入

10.删除pos节点

void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针
{//pos理论上来说不能为phead,但是参数没有phead，所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

11.链表的销毁

void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针)}

12.程序源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;}LTNode;//声明双向链表种提供的方法//初始化
void LTInit(LTNode** pphead);
void LTPrint(LTNode* phead);
//插入数据之前，链表必须初始化到只有一个头结点的情况
// 不改变哨兵位的地址，所以传一级指针即可
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);void LTDesTroy(LTNode* phead);

List.c

#include"List.h";void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(1);//给非0值}node->data = x;node->next = node->prev = node;return node;
}
void LTInit(LTNode** pphead)
{//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);
}
//尾插
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);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;//先改影响小的phead->next = newnode;}
//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//指定位置插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
//删除pos节点
void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针
{//pos理论上来说不能为phead,但是参数没有phead，所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//链表销毁
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针)}
//LTErase和LTDestroy参数理论上要传二级，因为我们需要让形参的改变影响到实参，但是为了接口的一致性才穿的一级
//传一级存在的问题是，当形参phead置为NULL后，实参plist不会被修改为NULL,因此解决方法是 调用完方法后手动将实参置为NULL

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h";void ListTest01()
{LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPushFront(plist, 3);LTPrint(plist);LTNode* find = LTFind(plist, 3);{if (find == NULL){printf("找不到\n");}else{printf("找到了\n");}}LTInsert(find, 66);LTPrint(plist);LTErase(find);LTPrint(plist);}
int main()
{ListTest01();return 0;
}