史上最强数据结构----双向循环链表的实现（带哨兵位）_c++链表怎么创建哨兵位

1、双向链表的基本结构

图示：

2、双向链表的基本结构实现

代码：

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;//存储的数据
	struct ListNode* next;//存储下一个节点的地址
	struct ListNode* prev;//存储上一个节点的地址
}ListNode;
1
2
3
4
5
6
7

3、双向链表的初始化

图示：

代码：

第一种：传二级指针的

void ListInit(ListNode** phead);//初始化函数的声明
void ListInit(ListNode** phead)//为什么要传二级指针，因为改变的是结构体的指针，所以要传结构体的指针
{
	assert(phead);
	*phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
	(*phead)->next = (*phead);
	(*phead)->prev = (*phead);
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
}
//下面是main函数中调用初始化函数的地方，为了方便理解二级指针
int main()
{
	ListNode*phead = NULL;//初始化之后，phead就会指向哨兵位，即NULL发生了改变，即改变的是结构体的指针，所以要传二级指针
	ListNode(&phead);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第二种：不传二级指针的

ListNode* ListInit(ListNode* phead);//初始化函数的声明
ListNode* ListInit()//此处为什么不传二级指针，因为在函数中会将开辟的哨兵位的地址作为返回值返回
{
	ListNode*phead = NULL;
	phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
	phead->next = phead;
	phead->prev = phead;
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
}
int main()
{
	ListNode*phead = ListInit();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4、双向链表的尾插

图示：

代码：

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);//哨兵位不可为空
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;
	tail->next = newnode;//(1)
	newnode->prev = tail;//(2)
	newnode->next = phead;//(3)
	phead->prev = newnode;//(4)
}
1
2
3
4
5
6
7
8
9
10

5、双向链表的尾删

图示：

代码：

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next == phead);//链表为空
	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;

	free(tail);
	tail = NULL;

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

6、双向链表的头插

图示：

代码：

void ListPushFront(ListNode* phead,LTDataType x)
{
	assert(phead);
	ListNode* next = phead->next;
	ListNode* newnode = BuyListNode(x);
	phead->next = newnode;//(1)
	newnode->prev = phead;//(2)

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

7、双向链表的头删

图示：

代码：

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* nextNext = phead->next->next;
	free(phead->next);
	phead->next = nextNext;//(1)
	nextNext->prev = phead;//(2)
}
1
2
3
4
5
6
7
8
9

8、双向链表的打印

代码：

void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)//当cur = phead的时候说明已经遍历完一遍了
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

9、双向链表元素的查找

代码：

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

注意：为什么要在最开始将cur置为phead->next？

1. 因为phead作为哨兵位中存储的不是有效数据，所以不能从这个开始查找。
2. 同时phead作为查找的终止条件，不能从这个元素开始，如果从这个元素开始遍历查找的话在一开始查找就停止了。

10、双向链表特定元素的删除

图示：

代码：

void ListErase(ListNode* pos)
{
    assert(pos);
	ListNode* next = pos->next;
    ListNode* prev = pos->prev;
    free(pos);
    pos = NULL;//此处可以置空也可以不置空，因为pos只是函数中的局部变量
    prev->next = next;//(1)
    next->prev = prev;//(2)
}
1
2
3
4
5
6
7
8
9
10

驼峰法命名规则：

1. 函数名和类型名所有单词首字母大写
2. 变量：第一个单词小写，后续单词首字母大写

11、双向链表特定元素的前插

图示：

代码：

void ListInsertBefore(ListNode* phead, ListNode* pos, LTDataType x)
{
	assert(pos);
    ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	prev->next = newnode;//(1)
	newnode->prev = prev;//(2)
	pos->prev = newnode;//(3)
	newnode->next = pos;//(4)
}
1
2
3
4
5
6
7
8
9
10

12、双向链表的销毁

图示：

代码：

第一种：传二级指针的，此时会将哨兵位的空间进行释放。

void ListDestory(ListNode** phead)
{
	assert(phead);
	ListNode* cur = (*phead)->next;
	while (cur!=(*phead))//结束条件就是不等于头节点
	{
		ListNode* next = cur->next;//存储当前释放节点的下一个节点的地址
		free(cur);//释放当前节点
		cur = next;//将节点向后推移
	}
	free(*phead);//释放哨兵位节点
	*phead = NULL;//防止内存泄漏
}
1
2
3
4
5
6
7
8
9
10
11
12
13

第二种：不传二级指针的，此时不将哨兵位的空间进行释放。

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	cur = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12