双向带头循环链表实现

带头双向循环链表的实现

定义

typedef int LTDataType;
typedef struct ListNode
{
    
	LTDataType data;
	struct ListNode* next;//指针指向后一个结点
	struct ListNode* prev;//指向前一个结点
}LTNode;

就像这样： （图拙）—_—！

实现

初始化

创建一个新结点当头结点，返回这个头结点，就当作初始化了

LTNode* ListCreate()
{
    
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	assert(phead);
	phead->prev = phead;
	phead->next = phead;//头指针指向自己，尾指针也指向自己
	return phead;//返回头
}

打印

没什么好说的 遍历即可

void ListPrint(LTNode* phead)
{
    
	assert(phead);

	LTNode* cur = phead->next;//从头结点的next开始遍历
	while (cur != phead)
	{
    
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

创建一个新结点

所有插入的前提，要创建出来一个新结点，我们把它封装成一个函数

LTNode* BuyLTNode(LTDataType x)
{
    
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

尾插

void ListPushBack(LTNode* phead, LTDataType x)
{
    
	assert(phead);
	LTNode* newnode = BuyLTNode(x);//创建新结点
	LTNode* tail = phead->prev;先把尾存起来

	tail->next = newnode;把尾的next指向新结点
	newnode->prev = tail;新结点的prev指向尾

	newnode->next = phead;新结点的next指向头
	phead->prev = newnode;头的prev指向新结点
}

尾删

void ListPopBack(LTNode* phead)
{
    
	assert(phead);
	LTNode* tail = phead->prev;//被删的尾
	LTNode* newtail = tail->prev;//新的尾

	free(phead->prev);//把尾删了
	phead->prev = NULL;//安全

	phead->prev = newtail;//把头的prev指向新的尾
	newtail->next = phead;//新的尾的next指向头

}

头插

void ListPushFront(LTNode* phead, LTDataType x)
{
    
	LTNode* newnode = BuyLTNode(x);
	LTNode* prev= phead->prev;//先把尾存起来

	newnode->next = phead;//新头的next指向头
	phead->prev = newnode;//头的prev指向新头
	prev->next = newnode;//尾的next指向新头
	newnode->prev = prev;//新头的prev指向尾
}

头删

删除的是头结点的下一个结点

void ListPopFront(LTNode* phead)//删除头结点的下一个结点
{
    
	assert(phead);
	assert(phead->next != phead);
	LTNode* newhead = phead->next;
	LTNode* next = newhead->next;
	
	phead->next = next;
	next->prev = phead;
	free(newhead);
	newhead = NULL;

}

查找一个数

没啥好说，遍历，跟打印一样

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    
	assert(phead);

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

在某个数字前插入

这个函数往往和find函数配合起来一起用，find找到那个数字返回该结点地址

void ListInsert(LTNode* pos, LTDataType x)
{
    
	assert(pos);

	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
	//跟头插非常相似
	newnode->next = pos;
	pos->prev = newnode;
	posPrev->next = newnode;
	newnode->prev = posPrev;
}

删除某个数字

void ListErase(LTNode* pos)
{
    
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	pos = NULL;
}

总结

总体来讲，双向带头循环虽然结构最为复杂，但是实现较为容易，并且实现也较为清晰，其各方面的效率也相当之优秀，是一个较为出色的数据结构。