C语言详解带头结点双向循环链表基本操作_在一个带有头结点的双向循环链表中

各有好坏：

上一节详解了 不带头结点的单向链表,通过单向链表我们虽然可以完成链表的基本操作，但是如果需要添加、删除尾结点等，我们时间复杂度会成为O（n），并且在单向链表中我们无法直接得到结点的前驱，只能苦苦遍历。

与单向链表相比，带头结点双向循环链表可以很好的解决上述出现的问题，并且可以有效避免二级指针的问题。

---

带头结点双向循环链表定义：

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

---

基本操作代码

1. 建立链表结构

想要完成双链表的增删查改，首先要建立一个正确的链表结构
双向 和 循环 是此链表的基本特点，所以会有一个前驱指针和一个后继指针以及数据域。

typedef int ElemType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ElemType data;
}ListNode;
}
1
2
3
4
5
6
7
8

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

2. 创建结点空间

这里很简单，我们就不做冗赘。

ListNode* CreatNode(ElemType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8

还是简单说一下，创建一个data = x 的结点之后，返回结点的地址。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

初始化链表

注意: 这里可以使用二级指针作为形参接受实参，因为我们这里需要在函数里修改头结点的值，所以我们实参进行址传递。

ListNode* ListInit()
{
	ListNode* phead = CreatNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
1
2
3
4
5
6
7

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

头插

创建新节点，链接前驱和后继。

//头插
void ListPushHead(ListNode* phead, ElemType x)
{
	ListNode* newnode = CreatNode(x);
	//保存第一个结点
	ListNode* 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
11

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

头删

如果链表是空，直接返回。

void ListHeadDelt(ListNode* phead)
{
	if (phead->next == phead)
	{
		return;
	}
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

尾插

尾结点就是头结点的前驱，尾结点的后继就是头结点。

void ListPushTail(ListNode* phead, ElemType x)
{
	ListNode* tail = phead->prev;
	ListNode* newnode = CreatNode(x);
	 
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

尾删

寻找尾结点的前驱，跳过尾结点，链接新链表，free结点空间。

void ListTailDelt(ListNode* phead)
{
	ListNode* tail = phead->prev;
	//尾结点的前驱
	ListNode* prev_tail = tail->prev;
	prev_tail->next = phead;
	phead->prev = prev_tail;
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

查找

遍历链表，找到结点就返回此结点的位置。

ListNode* ListFind(ListNode* phead, ElemType x)
{
	ListNode* now = phead->next;
	while (now != phead)
	{
		if (now->data == x)
		{
			return now;
		}
		now = now->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

在相应位置之前插入值

创建一个新的结点并完成链表的双向链接特性。

void ListInsert(ListNode* pos, ElemType x)
{
	ListNode* find_prev = pos->prev;
	ListNode* newnode = CreatNode(x);
	find_prev->next = newnode;
	newnode->prev = find_prev;
	newnode->next = pos;
}
1
2
3
4
5
6
7
8

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

在相应位置删除

跳过删除的位置，链接链表

void ListDelt(ListNode* pos)
{
	ListNode* find_prev = pos->prev;
	find_prev->next = pos->next;
	pos->next->prev = find_prev;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

清空链表

循环的条件已经不是 != NULL ，而是 != 头结点 ，因为链表是双向循环的。

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

---

整体代码

LinkList.h

#pragma once
//带头结点的双向循环 链表
#include <stdio.h> 
#include <stdlib.h>

typedef int ElemType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ElemType data;
}ListNode;

//初始化
ListNode* ListInit();

//清空链表
void ListDestory(ListNode* phead);

//尾插
void ListPushTail(ListNode* phead, ElemType x);

//打印链表
void ListPrint(ListNode* phead);

//头插
void ListPushHead(ListNode* phead, ElemType x);

//头删
void ListHeadDelt(ListNode* phead);

//尾删
void ListTailDelt(ListNode* phead);

//随机插入   pos位置之前插入
void ListInsert(ListNode* pos, ElemType x);

//随机删除    pos位置删除
void ListDelt(ListNode* pos);

//查找
ListNode* ListFind(ListNode* phead, ElemType x);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

LinkList.c

#include "LinkList.h"

//创建空间
ListNode* CreatNode(ElemType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->prev = NULL;

	newnode->next = NULL;
	return newnode;
}

//初始化
ListNode* ListInit()
{
	ListNode* phead = CreatNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//尾插
void ListPushTail(ListNode* phead, ElemType x)
{
	ListNode* tail = phead->prev;
	ListNode* newnode = CreatNode(x);
	 
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//ListInsert(phead, x);
}

//打印链表
void ListPrint(ListNode* phead)
{
	ListNode* new = phead->next;
	while (new != phead)
	{
		printf("%d->", new->data);
		new = new->next;
	}
	printf("NULL\n");
}


//头插
void ListPushHead(ListNode* phead, ElemType x)
{
	//ListNode* newnode = CreatNode(x);
	保存第一个结点
	//ListNode* first = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next = first;
	//first->prev = newnode;
	ListInsert(phead->next,x);
}

//头删
void ListHeadDelt(ListNode* phead)
{
	/*if (phead->next == phead)
	{
		return;
	}
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;*/
	ListDelt(phead->next);
}

//尾删
void ListTailDelt(ListNode* phead)
{
	//ListNode* tail = phead->prev;
	尾结点的前驱
	//ListNode* prev_tail = tail->prev;
	//prev_tail->next = phead;
	//phead->prev = prev_tail;
	//free(tail);
	//tail = NULL;
	ListDelt(phead->prev);
}

//查找
ListNode* ListFind(ListNode* phead, ElemType x)
{
	ListNode* now = phead->next;
	while (now != phead)
	{
		if (now->data == x)
		{
			return now;
		}
		now = now->next;
	}
	return NULL;
}


//随机插入   pos位置之前插入
void ListInsert(ListNode* pos, ElemType x)
{
	ListNode* find_prev = pos->prev;
	ListNode* newnode = CreatNode(x);
	find_prev->next = newnode;
	newnode->prev = find_prev;
	newnode->next = pos;
}

//随机删除    pos位置删除
void ListDelt(ListNode* pos)
{
	ListNode* find_prev = pos->prev;
	find_prev->next = pos->next;
	pos->next->prev = find_prev;
	free(pos);
	pos = NULL;
}


//清空链表
void ListDestory(ListNode* phead)
{
	ListNode* now = phead->next;
	while (now != phead)
	{
		ListNode* next = now->next;
		free(now);
		now = next;
	}
	free(phead);
	phead = NULL;
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

test.c

#include "LinkList.h"

void TestList()
{
	//初始化
	ListNode* plist = ListInit();

	//尾插
	ListPushTail(plist, 5);
	ListPushTail(plist, 6);
	ListPushTail(plist, 7);
	ListPushTail(plist, 8);
	printf("尾插: ");
	ListPrint(plist);
	
	//头插
	ListPushHead(plist, 4);
	ListPushHead(plist, 3);
	ListPushHead(plist, 2);
	printf("头插: ");
	ListPrint(plist);

	//头删
	ListHeadDelt(plist);
	ListHeadDelt(plist);
	printf("头删: ");
	ListPrint(plist);


	//尾删
	ListTailDelt(plist);
	printf("尾删: ");
	ListPrint(plist);

	//查找  随机插入
	ListNode* pos = ListFind(plist, 5);
	ListInsert(pos, 555);
	printf("随机插入: ");
	ListPrint(plist); 

	// 随机删除
	pos = ListFind(plist, 7);
	ListDelt(pos);
	printf("随机删除: ");
	ListPrint(plist);


	//销毁链表
	ListDestory(plist);

}

int main()
{
	TestList();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

---