C语言编程数据结构带头双向循环链表全面详解

目录

• 前言
• 一、什么是带头循环双向链表
• 二、链表初始化
• 三、链表接口函数

• 1.尾插
• 2.头插
• 3.头删
• 4.尾删
• 5.任意位置插入数据
• 6.任意位置删除数据

typedef int LTDataType;//万一以后需要改链表数据类型，可以直接在这里更改（int）
typedef struct ListNode
{
	struct ListNode*next;
	struct ListNode*prev;
	LTDataType data;
}ListNode;//结构体重命名

#include<stdlib.h>//malloc函数头文件
ListNode* BuyListNode(LTDataType x)//创建一个节点
{
	ListNode*newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* ListInit()//链表初始化
{
	ListNode*phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

#include<assert.h>//assert函数头文件
void ListPushBack(ListNode*phead, LTDataType x)//尾插
{
    assert(phead);//对传过来的指针进行断言,因为你要进行尾插至少得有个头节点啊
    //如果传过来的是空指针会进行报错
	ListNode*tail = phead->prev;
	ListNode*newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->data = phead;
	phead->prev = newnode;
}

void ListPushFront(ListNode*phead,LTDataType x)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*newnode = BuyListNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPopFront(ListNode*phead)
{
	assert(phead);
	ListNode*first = phead->next;
	ListNode*second = first->next;
	phead->next = second;
	second->prev = phead;
}

void ListPopBack(ListNode*phead)
{
	assert(phead);
	assert(phead->next != phead);//要进行尾删至少保证有一个节点可删（非head节点）
	ListNode*tail = phead->prev;//头节点前驱指向尾部
	ListNode*prev = tail->prev;//通过尾部得到d2地址
	prev->next = phead;//d2后驱head节点
	phead->prev = prev;//head前驱指向d2节点
}

ListNode* ListFind(ListNode*phead, LTDataType x)
{
	assert(phead);
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//遍历完链表都没有找到就返回空指针
}

void ListInsert(ListNode*pos, LTDataType x)
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

ListNode*pos = ListFind(plist, 3);
ListInsert(pos, 300);

void ListErase(ListNode*pos)//指定位置删除
{
	assert(pos);
	ListNode*prev = pos->prev;
	ListNode*next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);//prev和next连起来了，pos就可以被释放掉了
}

void ListPrint(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		printf("%d\n", cur->data);
		cur = cur->next;
	}
	printf("\n");
}