双向循环链表详解及其基本功能的实现

双向循环链表详解及其基本功能的实现

文章目录

循环链表概念定义节点类型及初始化销毁链表链表头插链表尾插特定位置插入链表头删链表尾删特定位置删除查找节点获取节点个数判断链表是否为空打印链表

循环链表概念

在单链表详解中我们提到了链表的几种基本的结构，在这里要详细讲到的就是带头双向循环链表，其结构如下：

该链表拥有1个头节点，且每个节点都有一个前驱指针和一个后继指针，分别用来保存前一个节点的地址和后一个节点的地址，这样就能够实现链表的双向访问的功能，需要注意的是链表的最后一个节点的后继指针指向头节点，头节点的前驱指针指向最后一个节点，带头双向循环链表的结构看起来比单链表的结构要复杂，但是在实现各种功能上要相对简单，接下来我们就来实现其基本功能。

定义节点类型及初始化

在初始化该链表前需要定义节点的类型，具体如下：

typedef int LTDataType; //假设该节点值的类型为int型
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
} LTNode;

然后初始化该链表，我们需要将该链表初始化为如下结构：
即只有一个头节点的循环链表。

实现如下：

void ListInit(LTNode** pphead) //因为会改变链表内部结构，所以传入二级指针方便使用
{
	assert(pphead);
	*pphead = ListBuyNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}

其中 ListBuyNode 为生成节点的函数

LTNode* ListBuyNode(LTDataType x)
{
	struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (node == NULL)
	{
		printf("malloc fail!n");
		exit(-1);
	}
	else
	{
		node->prev = NULL;
		node->next = NULL;
		node->val = x;
	}
		return node;
}

销毁链表

因为在实现链表时节点都是malloc出来的，所以在使用完链表后需要将链表销毁，否则就会造成内存泄露，实现如下：

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	
	while (cur) 
	{
		LTNode* Next = cur->next;
		free(cur); //将头节点后的节点都释放掉
		cur = Next;
	}
	free(phead); //最后在释放掉头节点
	phead = NULL;
}

链表头插

头插就是在链表的头节点和头节点的后一个节点之间插入一个节点，图示如下：

实现如下：

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = ListBuyNode(x);
	LTNode* Next = phead->next; //保存头节点的后一节点的地址
	phead->next = newnode; //头节点的后继指针指向新节点
	newnode->prev = phead; //新节点的前驱指针指向头节点
	newnode->next = Next; //新节点的后继指针指向原先头节点的后一节点
	Next->prev = newnode; //原先头节点的后一节点的前驱指针指向新节点
}

链表尾插

即在链表尾节点后插入一个新的节点，（这里我们指针链表的尾节点是指向头节点的，所以尾插实质上就是在链表的头节点前插入一个节点，所以这里主要对头节点 *** 作即可）并且仍有循环的功能，原理同上，只是插入位置有变，实现如下：

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* Prev = phead->prev; //保存头节点的前驱指针
	LTNode* newnode = ListBuyNode(x);
	phead->prev = newnode; //头节点的前驱指针指向新节点
	newnode->next = phead; //新节点的后继指针指向头节点
	newnode->prev = Prev; //新节点的前驱指针指向尾节点
	Prev->next = newnode; //尾结点的后继指针指向新节点
}

特定位置插入

即在特定两节点之间插入一个新节点，实现如下：

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = ListBuyNode(x);
	LTNode* Prev = pos->prev;
	Prev->next = newnode;
	newnode->prev = Prev;
	newnode->next = pos;
	pos->prev = newnode;
}

头插和尾插都可以复用该函数，该变参数即可。

链表头删

即删掉头节点的后一节点，图示如下：

实现如下：

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* tail = phead->next;
	LTNode* Next = tail->next;
	phead->next = Next;
	Next->prev = phead;
	free(tail); //节点的指向发生变化后别忘将tail节点释放
}

链表尾删

将链表的尾结(即头节点的前一节点)删掉，图示如下：

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* Prev = phead->prev;
	LTNode* Tail = Prev->prev;
	phead->prev = Tail;
	Tail->next = phead;
	free(Prev);
}

特定位置删除

原理同上（头删/尾删），实现如下：

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* Prev = pos->prev;
	LTNode* Next = pos->next;
	Prev->next = Next;
	Next->prev = Prev;
	free(pos);
}

其中头删尾删都能复用该函数，改变位置即可。

查找节点

找到链表中值为 x 的节点并返回该节点的位置，实现如下：

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead;
	while (cur->val != x)
	{
		cur = cur->next;
	}
	return cur;
}

获取节点个数

通过该函数算数该双向链表中的节点个数：

size_t ListSize(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead) //从头节点开始计数，当cur再次走到头节点时结束
	{
		size++;
		cur = cur->next;
	}
	return size;
}

判断链表是否为空

即返回一个判断的结果即可

bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

打印链表

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) //从头节点开始打印，当cur再次走到头节点时结束
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("n");
}