【数据结构初阶】双向带头循环链表原来是纸老虎，结构复杂，操作简单

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

struct ListNode
{
	int val;
	struct ListNode* prev;
	struct ListNode* next;
};

void ListInit(struct ListNode** pphead)
{
	struct ListNode* Guard = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (Guard == NULL)
	{
		perror("ListInit");
		return;
	}
	*pphead = Guard;
	Guard->next = Guard;
	Guard->prev = Guard;
}

struct ListNode* BuyListNode(int x)
{
	struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (newnode == NULL)
	{
		perror("BuySListNode");
		return NULL;
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}

void ListPushBack(struct ListNode* phead,int x)
{
	assert(phead);
	struct ListNode* newnode = BuyListNode(x);

	struct ListNode* tail = phead->prev;

	newnode->next = phead;
	phead->prev = newnode;

	tail->next = newnode;
	newnode->prev = tail;
}

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

void ListPushFront(struct ListNode* phead,int x)
{
	assert(phead);
	struct ListNode* newnode = BuyListNode(x);

	struct ListNode* next = phead->next;

	newnode->next = next;
	next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;

}

void ListInsert(struct ListNode* pos, int x)
{
	assert(pos);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* prev = pos->prev;

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

头插：ListNode(phead->next,x);
尾插:ListNode(phead,x);

bool ListEmpty(struct ListNode* phead)
{
	return phead->next == phead;
}

void ListPopBack(struct ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	struct ListNode* tail = phead->prev;
	struct ListNode* prev = tail->prev;
	
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

void ListPopFront(struct ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	struct ListNode* first = phead->next;
	struct ListNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

size_t ListSize(struct ListNode* phead)
{
	size_t size = 0;
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

void ListErase(struct ListNode* pos)
{
	assert(pos);
	struct ListNode* prev = pos->prev;
	struct ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}

void ListDestory(struct ListNode** pphead)
{
	assert(pphead);
	struct ListNode* cur = (*pphead)->next;
	while (cur != *pphead)
	{
		struct ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*pphead);
	*pphead = NULL;
}