【数据结构】循环链表的增删查改

---

前言

本文我们所要实现的是循环链表，即带头双向循环链表

---

一、什么是带头双向循环链表

带头双向循环链表与无头单向非循环链表不同的是，它结构复杂，一般用于单独存储数据，实际中使用的链表数据结构，均是带头双向循环链表。而无头单向非循环链表结构简单，一般不会用来单独存储数据，实际更多用于其他数据结构的子结构。

---

二、带头双向循环链表的实现

在实现循环链表增删查改之前，首先应该创建一个循环链表

typedef int CLTDataType;

typedef struct CListNode
{
	struct CListNode* next;
	struct CListNode* prev;
	CLTDataType data;
}CLTNode;
1
2
3
4
5
6
7
8

其中prev是前一个结点地址，next是下一个结点。

---

2.1、动态开辟一个空间

代码如下（示例）：

CLTNode* BuyListNode(CLTDataType x)
{
	CLTNode* newnode = (CLTNode*)malloc(sizeof(CLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

2.2、初始化与打印

1、初始化

代码如下（示例）：

CLTNode* LTInit()
{
	CLTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
1
2
3
4
5
6
7
8

2、打印

void LTPrint(CLTNode* phead)
{
	assert(phead);

	CLTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

---

2.3、插入操作

尾插

void LTPushBack(CLTNode* phead, CLTDataType x)
{
	assert(phead);

	CLTNode* newnode = BuyListNode(x);
	CLTNode* tail = phead->prev;

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

1
2
3
4
5
6
7
8
9
10
11
12
13

---

头插

头插一共两种写法

第一种：

先让新结点的next指向下一个结点，再让头结点的next指向新结点，有先后顺序。

代码如下：

void LTPushFront(CLTNode* phead, CLTDataType x)
{
	assert(phead);

	CLTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}
1
2
3
4
5
6
7
8
9
10
11

第二种：

创建一个新指针，无先后顺序

代码如下：

void LTPushFront(CLTNode* phead, CLTDataType x)
{
	assert(phead);
	CLTNode* newnode = BuyListNode(x);
	CLTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

---

在pos之前插入

pos在head处时，进行尾插

pos在d1处时，进行头插

代码如下：

void LTInsert(CLTNode* pos, CLTDataType x)
{
	assert(pos);
	CLTNode* prev = pos->prev;
	CLTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

在头删和尾删也可直接调用此函数
头删：LTInsert(phead, x)
尾删：LTInsert(phead->next, x)

---

2.4、删除操作

尾删

void LTPopBack(CLTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	CLTNode* tail = phead->prev;
	CLTNode* tailPrev = tail->prev;

	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}
1
2
3
4
5
6
7
8
9
10
11

---

头删

代码如下：

void LTPopFront(CLTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	CLTNode* first = phead->next;
	CLTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;

}
1
2
3
4
5
6
7
8
9
10
11

---

删除pos处的位置

代码如下：

void LTErase(CLTNode* pos)
{
	assert(pos);
	CLTNode* prev = pos->prev;
	CLTNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
1
2
3
4
5
6
7
8
9

在头删和尾删也可直接调用此函数
头删：LTErase(phead->next)
尾删：LTErase(phead->prev)

---

2.4、查找与销毁操作

1、查找

代码如下：

CLTNode* LTFind(CLTNode* phead, CLTDataType x)
{
	assert(phead);
	CLTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、销毁

代码如下：

void LTDestroy(CLTNode* phead)
{
	assert(phead);
	CLTNode* cur = phead->next;
	while (cur != phead)
	{
		CLTNode* next = cur->next;
		free(cur);

		cur = next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13