【c语言数据结构】超详细！模拟实现双向链表(初始化、销毁、头删、尾删、头插、尾插、指定位置插入与删除、查找数据、判断链表是否为空)

#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);

#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->newnode
	pcur->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指向pcur
	newnode->prev = phead;
	newnode->next = pcur;

	//哨兵位的next，原头结点的prev，分别指向newnode
	phead->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->prev
	LTNode* del = phead->next;

	//删除尾结点 哨兵位的prev指向del->prev, 尾结点的前一结点的next->哨兵位
	del->prev->next = phead;//注意这俩行代码不可调换！
	phead->prev = del->prev;//先改了头结点的指向 del也会跟着改！
	

	//删除完之后释放del
	free(del);
	del = NULL;
}

//头删数据
void LTPopFront(LTNode* phead) {
	assert(phead);
	assert(!LTEmpty(phead));

	//哨兵位phead 要删除的第一个结点del(phead->next) 新的第一结点del->next
	LTNode* del = phead->next;

	//删除结点 哨兵位的next指向新第一结点 新的第一结点的prev指向哨兵位
	del->next->prev = phead;
	phead->next = del->next;
	

	//释放del
	free(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
	//先安newnode
	newnode->next = pos->next;
	newnode->prev = pos;

	//先连接pos后面的，再连pos
	pos->next->prev = newnode;
	pos->next = newnode;
}

//删除指定位置的节点
void LTIErase(LTNode* pos) {
	assert(pos);//传过来的位置不为空

	/*
	pos前面的节点pos->prev
	pos后面的节点pos->next

	删除pos影响这两个节点

	pos前面指针的节点的next指针->Pos后面的节点
	pos后面的节点的prev指针就->pos前面的节点*/

	//pos->prev pos pos->next
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}