数据结构--双向循环链表的实现

之前学习了单链表的实现，单链表在实现的过程中，尾删，尾插是比较麻烦的，时间复杂度为O(N)，而双向循环链表就不会有这样的顾虑，双向循环链表的结构是很有优势的。具体优势在实现的时候会显现出来。

在实现双向循环链表时，我们选择了插入头指针。

//头文件包
#include
#include
#include

typedef int Data;


typedef struct List
{
	Data val;
	struct List* next;
	struct List* prev;
}List,list;

//初始化
List* InitList(List** phead);

List* DestoryList(List* phead);
//尾插
void PushBack(List* phead, Data x);
void PopBack(List* phead);

void PushFront(List* phead, Data x);
void PopFront(List* phead);

void EraseList(List* phead, List** ppos);
void InsertList(List* phead, List* pos, Data x);
void InsertList2(List* phead, List* pos, Data x);

void PrintList(List* phead);

List* FindList(List* phead, Data x);

List* Buynewnode(Data x)
{
	List* newnode = (List*)malloc(sizeof(list));
	if (newnode == NULL)
	{
		printf("malloc failed");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

List* InitList(List** pphead)
{
	(*pphead) = Buynewnode(0);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
	return *pphead;
}

//初始化链表也就是为了插入一个哨兵结点，Buynewnode函数在后面还会用到
//在这里初始化链表参数用了二级指针，这是因为要改变结点指针的值，所以传二级指针

//尾插
void PushBack(List* phead, Data x)
{
	assert(phead);
	
	List* newnode = Buynewnode(x);
	List* tail = phead->prev;//找尾

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

}
//尾插的时候，结构优势就来了，就是在找尾时不用再从头遍历找尾，

//头插
void PushFront(List* phead, Data x)
{
	assert(phead);

	List* next = phead->next;
	List* newnode = Buynewnode(x);

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

//任意位置插入函数
void InsertList(List* phead, List* pos, Data x)//插到pos前面
{
	assert(pos);

	List* newnode = Buynewnode(x);
	List* prevtail = pos->prev;

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

void InsertList2(List* phead, List* pos, Data x)//插到pos后面
{
	assert(pos);

	List* newnode = Buynewnode(x);
	List* next = pos->next;

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

}
//在插入进任意位置的时候，无论是插在pos前面还是后面时间复杂度都很低
//这就是结构优势，不用找尾。

//尾删
void PopBack(List* phead)
{
	assert(phead);
	assert(phead->next != NULL);//保证链表中不只有哨兵结点

	List* tail = phead->prev;
	List* prevtail = tail->prev;

	prevtail->next = phead;
	phead->prev = prevtail;

	free(tail);
}
//在删除的过程中，要注意的一点就是不要将哨兵结点删除，可以用
//assert断言一下，头删的时候也是。

//头删
void PopFront(List* phead)
{
	assert(phead);
	assert(phead->next != phead);

	List* cur = phead->next;
	List* next = cur->next;
    free(cur);
	phead->next = next;
	next->prev = phead;
}

//任意位置删除
void EraseList(List* phead, List** ppos)
{
	assert(phead && *ppos);

	List* prevtail = (*ppos)->prev;
	List* next = (*ppos)->next;

	prevtail->next = next;
	next->prev = prevtail;
	free(*ppos);
	*ppos = NULL;
}
//在这里pos可以传一级指针，也可以传二级指针，如果最后给pos赋NULL，就要用二级指针；
//如果不修改pos的值，就用一级指针。修不修改pos的值都可以。

void PrintList(List* phead)
{
	assert(phead);

	List* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("n");
}

List* FindList(List* phead, Data x)
{
	assert(phead);

	List* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

销毁链表

List* DestoryList(List* phead)
{
	assert(phead);
	List* cur = phead->next;
	while (cur != phead)
	{
		List* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}