双向循环链表的介绍

1.什么是双向链表?双向循环链表?

(1)双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前驱的指针域prev，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。

(2)双向循环链表将双向链表的头结点和尾结点链接起来也能构成循环链表，其称为双向循环链表。

2.双向循环链表的实现

(1)结构

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	int data;
}ListNode;

(2)创建新链表

ListNode* BuyListNode(LTDataType x)//建立新节点
{
	ListNode* node = (struct ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	return node;
}

(3)初始化

void ListInit()//初始化
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

(4)尾插

void ListPushBack(ListNode* phead,LTDataType x)//尾插
{
	/*assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/
	ListInsert(phead, x);
}

(5)头插

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;	
}

(6)头删

void ListPushFront(ListNode* phead)//头删
{
	assert(phead);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
}

(7)尾删

void ListPushBack(ListNode* phead)//尾删
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

(8)查找某个值的位置

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;
}

(9)插入

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;
}

(10)删除

void ListErase(ListNode* pos)//删除某位置的节点
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

(11)判断是否为空

int ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead ? 1 : 0;//空为1，不空为0
}

(12)链表的长度

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

(13)销毁链表

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

(14)打印链表

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