数据结构——带头双向循环链表_带头结点的双循环链表d.带头结点的单循环链表

带头双向循环链表的结构

带头双向循环链表的结构如下图：

可以看到，带头双向循环链表是结构最复杂的链表

但是在实际使用链表结构存储数据时，都是使用带头双向循环链表，虽然这个结构有些复杂，但是这样的结构会给我们带来很多优势，实现代码的时候反而简单了

下面我们来实现一下带头双向循环链表

---

带头双向循环链表的实现

因为这是一个双向链表，所以要在结构体中定义2个结构体类型指针，用来指向节点的前一个结点和后一个结点

所以带头双向循环链表的结构体如下：

typedef int LTDataType;

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

}LTNode;
1
2
3
4
5
6
7
8
9

---

建立新节点

这里还是使用malloc去建立一个结点，其余的与单链表中建立新节点类似，这里不多说。

LTNode* BuyNewNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

初始化函数

因为这个结构是包含头节点的，所以要在初始化函数中把头节点定义出来

LTNode* phead = BuyNewNode(-1);
1

因为此时只有头节点一个结点，又因为结构是循环的，所以头节点的下一个结点和上一个节点都是头节点自己

phead->next = phead;
phead->prev = phead;
1
2

所以，初始化的代码为：

LTNode* LTInit()
{
	LTNode* phead = BuyNewNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
1
2
3
4
5
6
7

---

打印函数

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

---

判空函数

当只剩头节点一个节点时，链表就为空了，所以当phead->next == phead时，就说明链表为空了

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
1
2
3
4
5

---

尾插函数

尾插函数第一步就是要找尾，在单链表中，想要找到尾就需要遍历一遍链表，效率低耗时

但是在带头双向循环链表中，找到尾很简单，尾节点就是头节点的前一个节点

然后再依次将结点前后链接上即可

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNewNode(x);
	LTNode* 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

---

头插函数

在实现单链表时，头节点就是头指针指向的结点
在带头双向循环链表中，头节点就是头节点的下一个结点

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNewNode(x);
	LTNode* nex = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = nex;
	nex->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

---

尾删函数

在单链表中，我们循环需要找到尾节点以及尾节点前面的节点，十分的麻烦
但是在带头双向循环链表中，就没有这样的问题

头节点的prev就是尾节点tail，尾节点的prev就是尾节点的前一个节点tailprev

然后将tailprev当成尾节点链接起来，最后free掉tail

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	tailprev->next = phead;
	phead->prev = tailprev;
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

头删函数

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	LTNode* nex = del->next;
	phead->next = nex;
	nex->prev = phead;
	free(del);
	del = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

头删与尾删类似，不多说

---

查找函数

在单链表中，查找某个节点的循环条件是什么时候遇到空，什么时候结束循环

在带头双向循环链表中，循环条件则是遇到头节点，就结束循环

LTNode* LTFind(LTNode* phead,LTDataType x)
{
	assert(phead);
	LTNode* 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

---

插入函数

在pos位置前插入，这个pos的地址是由LTFind函数返回的

如果我们直接就将新的节点newnode插入到pos前面位置，它们之间的链接操作有一定的顺序，如果随意改变链接关系是会出问题的

所以我们可以用一个指针posprev去保存pos->prev的地址，然后再链接posprev、newnode和 pos间的链接关系，这时的链接关系的改变不需要按照一定的顺序，按照逻辑随意修改

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* newnode = BuyNewNode(x);
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;

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

我们可以用这个删除函数与实现头插和尾插

尾插：因为在pos前插入，头节点的前一个结点就是尾结点，所以调用LTInsert函数时传的地址是phead

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x); 
	//调用LTInsert函数尾插
}
1
2
3
4
5
6

头插：phead->next的前插入就是头插，所以传参为phead->next

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead->next, x); 
	 //调用LTInsert函数头插
}
1
2
3
4
5
6

---

删除函数

这里的操作也如上个函数一样，用一个指针posprev保存pos->prev的地址，用指针posnext保存pos->next的地址，然后链接posprev和posnext

随后free掉pos即可

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

这个函数还有个瑕疵就是：
如果pos传的是哨兵位头节点的地址，那么删除操作就会出错
这里如果想检查，就需要传一个参数，用来比较pos和头节点地址是否相同，但是没有必要
在后面C++中会有更好的写法

同样，可以调用LTErase去实现头删和尾删

头删：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);

}
1
2
3
4
5
6
7

尾删：

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}
1
2
3
4
5
6

---

销毁函数

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

	LTNode* del = phead->next;
	LTNode* nex = del->next;
	while (del!= phead)
	{
		free(del);
		del = nex;
		nex = nex->next;
	}

	free(phead);
	phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

带头双向循环链表的特点

在前面实现的过程中可以发现：

• 以往单链表的尾删、删除和插入操作的时间复杂度是 O(n),因为需要找尾或找前一个结点，但是带头双向循环链表完美得解决了这个问题，我们可以通过phead->prev找到尾，通过某一结点的prev找到前一个结点，所以在带头双向循环链表中，尾删和插入的时间复杂度为O(1)
• 在单链表的头插、尾插、头删、尾删等函数中，传的参数有二级指针，不容易理解，但是带头双向循环链表有头节点，传参是头节点的地址，因为在函数中是不会改变这个地址的指向，所以不用传二级指针

---

链表和顺序表的对比

这两个结构各有优势，很难说谁更优，这两个结构相辅相成

顺序表：

• 物理上存储空间连续
• 支持随机访问
• 任意位置插入或者删除元素可能需要搬移元素，效率低O(N)
• 连续物理空间，空间不够后需要增容。增容有一定程度的消耗

链表：

• 物理上存储空间不连续，但是逻辑上连续
• 不支持随机访问
• 任意位置插入删除效率高
• 按需申请释放空间