[C][数据结构][带头双向循环链表]详细讲解

1.顺序表和带头双向循环链表的区别

• 顺序表优点

  • 下标随机访问
  • CPU高速缓存命中率高

• 顺序表缺点

  • 头部或者中间插入删除效率低O(N)
  • 扩容(有一定程度性能消耗、可能存在一定程度空间浪费)

• 链表优点

  • 任意位置插入删除O(1)
  • 按需申请释放

• 链表缺点

  • 不支持下标随机访问
  • CPU高速缓存命中率低

• 综上，顺序表和带头双向循环链表是相辅相成的

  

2.带头双向循环链表

• 接口

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
LTNode* CreListNode(LTDataType x);
LTNode* ListInit();
void ListDestroy(LTNode* phead);
void ListPrint(LTNode* phead);
void ListPushBack(LTNode* phead, LTDataType x);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
 
//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置的节点
void ListErase(LTNode* pos);
 
//可选接口
//链表大小 -- 但效率不高O(N)
int ListSize(LTNode* phead);
//判断链表是否为空
bool isListEmpty(LTNode* phead);
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

• 接口实现

LTNode* CreListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)  //检查是否开辟成功
	{
		perror("malloc:");
		exit(1);
	}
 
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
 
	return node;
}
 
LTNode* ListInit()
{
	LTNode* phead = CreListNode(0);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}
 
void ListDestroy(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
 
	free(phead);
	phead = NULL;
}
 
void ListPrint(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	//不能单纯循环
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* newnode = CreListNode(x);
	LTNode* tail = phead->prev;  //找尾
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;  //确定实质的尾
	phead->prev = newnode;
 
	//ListInsert(phead, x);  //以上代码可以用这个封装替换
}
 
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* newnode = CreListNode(x);
	LTNode* next = phead->next; 
 
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
 
	//ListInsert(phead->next, x);  //以上代码可以用这个封装替换
}
 
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);  //确保不只有一个头节点  --  还有的删
 
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
 
	free(tail);
 
	tailPrev->next = phead;
	phead->prev = tailPrev;
 
	//ListErase(phead->prev);  //以上代码可以用这个封装替换
}
 
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	LTNode* first = phead->next;
	LTNode* next = first->next;
 
	free(first);
 
	phead->next = next;
	next->prev = phead;
 
	//ListErase(phead->next);  //以上代码可以用这个封装替换
}
 
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* newnode = CreListNode(x);
	LTNode* prev = pos->prev;
	
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
void ListErase(LTNode* pos)
{
	assert(pos);
	
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
 
	free(pos);
 
	prev->next = next;
	next->prev = prev;
}
 
int ListSize(LTNode* phead)
{
	assert(phead);
	int size = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
 
	return size;
}
 
bool isListEmpty(LTNode* phead)
{
	assert(phead);
 
	return phead->next == phead;
}
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162