双向链表的增删查改

目录

 结构体类型中要有三个元素：1、指向前一个节点的指针prev。2、存储的数据val。3、指向后一个节点的指针next。还有要注意的点就是：头节点head和尾结点tail的关系，head->prev=tail，tail->next=head.

1.两个typedef，做好基础工作

2.需要定义的各个函数

初始化函数的细节

申请空间函数

插入函数函数细节（默认尾插）

 删除函数细节

7.关于头插尾插，头删尾删

查找函数

销毁函数

打印函数

11.完整程序加运行

---

•  结构体类型中要有三个元素：1、指向前一个节点的指针prev。2、存储的数据val。3、指向后一个节点的指针next。还有要注意的点就是：头节点head和尾结点tail的关系，head->prev=tail，tail->next=head.

若一个双向链表只有头节点head那么他的head->next=head;head->prev=head;

---

1.两个typedef，做好基础工作

typedef int LTDataType;




typedef struct ListNode




{



	struct ListNode* next;



	struct ListNode* prev;



	LTDataType data;



}LTNode;

方便以后修改数据类型和简化写代码。

---

2.需要定义的各个函数

LTNode* LTDinit();//初始化双向链表





LTNode* BuyListNode(LTDataType x);//申请新的节点





void ListPrint(LTNode* phead);//打印双向链表





void ListInsert(LTNode* pos, LTDataType x);//在任意位置插入





void ListPushBack(LTNode* phead, LTDataType x);//尾部插入





void ListPushFront(LTNode* phead, LTDataType x);//头部插入





void ListErase(LTNode* pos);//删除数据





void ListPopBack(LTNode* phead);//尾部删除





void ListPopFront(LTNode* phead);//头部删除





LTNode* ListFind(LTNode* phead, LTDataType x);//查找





void ListDestory(LTNode* phead);//销毁双向链表

---

初始化函数的细节

LTNode* LTDinit()



{



	LTNode* guard = NULL;//创建哨兵位节点，方便尾插




	guard = (LTNode*)malloc(sizeof(LTNode));



	if (guard == NULL)



	{



		perror("malloc fail\n");



		exit;//开辟成功则继续，失败则退出程序




	}



	else




	{



		guard->next = guard;



		guard->prev = guard;



	}



	return guard;



}

有一个哨兵位节点就方便后续的插入，当然在销毁双向链表的时候也需要在哨兵位上注意一点

---

申请空间函数

参数是数据x,返回值是新开辟空间的地址，找到地址后就可以方便插入操作

LTNode* BuyListNode(LTDataType x)



{



	LTNode* cur = NULL;



	cur = (LTNode*)malloc(sizeof(LTNode));//malloc之后一定要记得检查




	if (cur == NULL)



	{



		perror("malloc fail\n");



	}



	cur->next = NULL;



	cur->prev = NULL;



	cur->data = x;



	return cur;



}

---

插入函数函数细节（默认尾插）

第一个参数是插入位置的地址，第二个参数是所需插入的数据

void ListInsert(LTNode* pos, LTDataType x)



{



	assert(pos);



	LTNode* new =BuyListNode(x);



	if (new == NULL)



	{



		perror("malloc fail");



	}



	LTNode* next = pos->next;



	new->next = next;



	new->prev = pos;



	pos->next = new;



	next->prev = new;



}

---

 删除函数细节

需要传参pos，告诉位置，删除数据，并重新链接链表

void ListErase(LTNode* pos)



{



	assert(pos);



	LTNode* prev = pos->prev;//记录pos前的数据，方便在pos位置数据销毁后重新链接




	LTNode* next = pos->next;//记录pos后的数据，方便在pos位置数据销毁后重新链接




	LTNode* cur = pos;//创建一个cur新指针用来free空间




	prev->next = next;



	next->prev = prev;



	free(cur);



}

函数的效果图如下

---

7.关于头插尾插，头删尾删

头插尾插就是ListInsert函数的特殊情况，在头部和尾部插入；

同理，头删尾删就是ListErase函数的特殊情况，在头部和尾部删除；

因此可以借助这两个原本已有的函数，只需要传入头尾的地址即可

void ListPopBack(LTNode* phead)//尾删



{



	assert(phead);



	LTNode* cur = phead->prev;



	ListErase(phead->prev);



	free(cur);



	cur = NULL;



}



void ListPopFront(LTNode* phead)//头删



{



	assert(phead);



	LTNode* cur = phead;



	ListErase(phead);



	free(cur);



	cur = NULL;



}

void ListPushBack(LTNode* phead, LTDataType x)//尾插



{



	assert(phead);



	ListInsert(phead->prev, x);



 



}



void ListPushFront(LTNode* phead, LTDataType x)//头插



{



	assert(phead);



	ListInsert(phead, x);



 



}

---

查找函数

返回值是指针，若没找到则放回一个NULL。

LTNode* ListFind(LTNode* phead, LTDataType x)



{



	assert(phead);



	LTNode* cur = phead->next;//将head地址赋给cur，通过cur遍历




	while (cur != phead)



	{



		if (cur->data == x)



			return cur;



		cur = cur->next;



	}//当cur==head的时候说明双向链表已经遍历完一遍了，此时还未找到，则说明所给地址不存在于此链表中




	return NULL;



}

---

销毁函数

void ListDestory(LTNode* phead)



{



	assert(phead);



	LTNode* cur = phead->next;//同上，用cur从头遍历




	while (cur != phead)



	{



		LTNode* next = cur->next;//用next记住原本的下一个位置，方便在销毁后迭代




		free(cur);



		cur = next;



	}



	free(phead);//最后把phead位置的内存给释放




}

---

打印函数

给上头结点，往后依次打印

void ListPrint(LTNode* phead)



{



	assert(phead);



	LTNode* cur = phead->next;



	while (cur!=phead)



	{



		printf("%d<->", cur->data);



		cur = cur->next;



	}



		printf("NULL\n");



}

---

11.完整程序加运行

LTNode* LTDinit()



{



	LTNode* guard = NULL;



	guard = (LTNode*)malloc(sizeof(LTNode));



	if (guard == NULL)



	{



		perror("malloc fail\n");



		exit;



	}



	else




	{



		guard->next = guard;



		guard->prev = guard;



	}



	return guard;



}



LTNode* BuyListNode(LTDataType x)



{



	LTNode* cur = NULL;



	cur = (LTNode*)malloc(sizeof(LTNode));//malloc之后一定要记得检查




	if (cur == NULL)



	{



		perror("malloc fail\n");



	}



	cur->next = NULL;



	cur->prev = NULL;



	cur->data = x;



	return cur;



}



void ListPrint(LTNode* phead)



{



	assert(phead);



	LTNode* cur = phead->next;



	while (cur!=phead)



	{



		printf("%d<->", cur->data);



		cur = cur->next;



	}



		printf("NULL\n");



}



void ListPushBack(LTNode* phead, LTDataType x)



{



	assert(phead);



	ListInsert(phead->prev, x);



 



}



void ListPushFront(LTNode* phead, LTDataType x)



{



	assert(phead);



	ListInsert(phead, x);



 



}



void ListInsert(LTNode* pos, LTDataType x)



{



	assert(pos);



	LTNode* new =BuyListNode(x);



	if (new == NULL)



	{



		perror("malloc fail");



	}



	LTNode* next = pos->next;



	new->next = next;



	new->prev = pos;



	pos->next = new;



	next->prev = new;



}void ListErase(LTNode* pos)




{



	assert(pos);



	LTNode* prev = pos->prev;



	LTNode* next = pos->next;



	LTNode* cur = pos;



	prev->next = next;



	next->prev = prev;



	free(cur);



	cur = NULL;



}



void ListPopBack(LTNode* phead)



{



	assert(phead);



	LTNode* cur = phead->prev;



	ListErase(phead->prev);



	free(cur);



	cur = NULL;



}



void ListPopFront(LTNode* phead)



{



	assert(phead);



	LTNode* cur = phead;



	ListErase(phead);



	free(cur);



	cur = NULL;



}



LTNode* ListFind(LTNode* phead, LTDataType x)



{



	assert(phead);



	LTNode* cur = phead->next;



	while (cur != phead)



	{



		if (cur->data == x)



			return cur;



		cur = cur->next;



	}



	return NULL;



}void ListDestory(LTNode* phead)




{



	assert(phead);



	LTNode* cur = phead->next;



	while (cur != phead)



	{



		LTNode* next = cur->next;



		free(cur);



		cur = next;



	}



	free(phead);



}

头文件如下：

#define _CRT_SECURE_NO_WARNINGS



#include <>



#include <>



#include <>



#include <>




typedef int LTDataType;




typedef struct ListNode




{



	struct ListNode* next;



	struct ListNode* prev;



	LTDataType data;



}LTNode;




LTNode* LTDinit();//初始化双向链表





LTNode* BuyListNode(LTDataType x);//申请新的节点





void ListPrint(LTNode* phead);//打印双向链表





void ListInsert(LTNode* pos, LTDataType x);//在任意位置插入





void ListPushBack(LTNode* phead, LTDataType x);//尾部插入





void ListPushFront(LTNode* phead, LTDataType x);//头部插入





void ListErase(LTNode* pos);//删除数据





void ListPopBack(LTNode* phead);//尾部删除





void ListPopFront(LTNode* phead);//头部删除





LTNode* ListFind(LTNode* phead, LTDataType x);//查找





bool ListEmpty(LTNode* phead);//判断双向链表是否为空





void ListDestory(LTNode* phead);//销毁双向链表