带头双向循环链表--数据结构

---

文章目录

• 前言
• 一、创建结点的结构体
• 二、创建新结点
• 三、初始化双向链表（创建哨兵位头节点）
• 四、双链表销毁
• 五、判断链表是否为空
• 六、双向链表打印
• 七、双向链表尾插
• 八、双向链表尾删
• 九、双向链表头插
• 十、双向链表头删
• 十一、双向链表查找
• 十二、双向链表插入
• 十三、双向链表删除
• 十五、总代码
• 十四、总结

前言

• 本篇链表为双向带头循环链表，所以会用到哨兵位头节点，哨兵位头节点只会用到前（最后一个结点地址）后（第二个结点，也就是存储数据的第一个结点）结点地址，所以只存储前后结点地址，该位置的数据成员不会用到，所以可以给随机值。
• 哨兵位头结点最大的优势就是不需要动不动就判度是否为空这种分情况，它使得为空和不为空都能用一个代码。看完本篇你会了解到哨兵位头结点的方便。

一、创建结点的结构体

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

二、创建新结点

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

三、初始化双向链表（创建哨兵位头节点）

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

四、双链表销毁

//双链表的销毁
void DestoryListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	ListNode* next = NULL;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

• 注意出函数后要让指针指向空，因为指向已经释放了，所以是野指针。因为传的是自己（一级指针），而不是自己的指针（二级指针），所以在函数里无法改变实参，只能出函数后再改变指向位置。

五、判断链表是否为空

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

六、双向链表打印

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

七、双向链表尾插

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

八、双向链表尾删

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

九、双向链表头插

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

十、双向链表头删

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

十一、双向链表查找

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

十二、双向链表插入

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

十三、双向链表删除

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

十五、总代码

ListNode.h

ListNode.h

#pragma once

//带头双向循环链表

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

//创建新节点
ListNode* BuyNewnode(ListNodeDate x);

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode();

//双链表的销毁
void DestoryListNode(ListNode* phead);

//双向链表打印
void PrintListNode(ListNode* phead);

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x);

//双向链表尾删
void PopBackListNode(ListNode* phead);

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x);

//双向链表头删
void PopFrontListNode(ListNode* phead);

//双向链表查找
ListNode* FindListNode(ListNode* phead, ListNodeDate x);

//双向链表在pos前面插入
void InsertListNode(ListNode* phead, ListNodeDate x, ListNode* pos);

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos);

ListNode.c

ListNode.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

//双链表的销毁
void DestoryListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead;
	ListNode* next = cur->next;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
}

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

int main()
{
	//创建哨兵位头节点
	ListNode* plist = InitListNode();//pointer List

	//尾插尾删打印
	//PushBackListNode(plist, 0);
	//PushBackListNode(plist, 1);
	//PushBackListNode(plist, 2);
	//PushBackListNode(plist, 3);
	//PushBackListNode(plist, 4);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PrintListNode(plist);
	//头插头删打印
	//PushFrontListNode(plist, 0);
	//PushFrontListNode(plist, 1);
	//PushFrontListNode(plist, 2);
	//PushFrontListNode(plist, 3);
	//PushFrontListNode(plist, 4);
	//PopFrontListNode(plist);
	//PrintListNode(plist);

	//综合验证
	PushBackListNode(plist, 0);
	PushBackListNode(plist, 1);
	PushBackListNode(plist, 2);
	PushFrontListNode(plist, 3);
	PushFrontListNode(plist, 4);
	PushFrontListNode(plist, 5);
	PopBackListNode(plist);
	PopFrontListNode(plist);
	
	//插入
	ListNode* pos = FindListNode(plist,0);
	InsertListNode(plist, 10, pos);

	//删除
	pos = FindListNode(plist, 10);
	EraseListNode(plist,pos);
	pos = NULL;

	PrintListNode(plist);
	DestoryListNode(plist);
	plist = NULL;
	return 0;
}

十四、总结

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话，就点我进入主页关注我吧！