双向链表的讲解与实现

作者：从前慢现在也慢 | 2024-06-07 17:11:08

踩

双向链表的讲解与实现

一、双向链表的结构
二、顺序表和双向链表的优缺点分析
三、双向链表的实现(使用VS2022)
四、代码优化
五、完整 List.c 源代码

一、双向链表的结构

在这里插入图片描述

带头”跟前面我们说的“头节点”是两个概念，带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。

“哨兵位”存在的意义：遍历循环链表避免死循环。

二、顺序表和双向链表的优缺点分析

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问(时间复杂度)	支持 O(1)	不支持且为 O(N)
任意位置插入或者删除元素	可能需要移动元素，效率为 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储 + 频繁访问	任意位置插入和频繁删除

三、双向链表的实现(使用VS2022)

这里用VS2022的C语言来实现双向链表。

这个结构虽然复杂，但是其中特殊的结构会带来很多优势，代码实现很简单。

双向链表常用的增删改查等接口包括：

1.初始化、销毁、打印、判空

2.尾插尾删、头插头删

3.查找、指定插入、指定删除

在 List.h 中：

#pragma once

#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
} ListNode, * pListNode;

// 初始化、销毁、打印、判空
pListNode ListInit();

void ListDestroy(pListNode phead);

void ListPrint(pListNode phead);

bool ListEmpty(pListNode phead);

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x);

void ListPopBack(pListNode phead);

void ListPushFront(pListNode phead, LTDataType x);

void ListPopFront(pListNode phead);

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x);

void ListInsert(pListNode pos, LTDataType x);

void ListErase(pListNode pos);
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

1.初始化、销毁、打印、判空

// 创建节点封装成函数
pListNode CreateNode(LTDataType x)
{
	pListNode temp = (pListNode)malloc(sizeof(ListNode));
	if (temp == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	temp->data = x;
	temp->prev = NULL;
	temp->next = NULL;

	return temp;
}

// 初始化、销毁、打印、判空
pListNode ListInit()
{
	pListNode temp = CreateNode(-1);
	temp->next = temp;
	temp->prev = temp;

	return temp;
}

void ListDestroy(pListNode phead)
{
	assert(phead);

	pListNode temp = phead->next;
	while (temp != phead)
	{
		pListNode dest = temp->next;
		free(temp);
		temp = dest;
	}
	free(temp);
	temp = phead = NULL;
}

void ListPrint(pListNode phead)
{
	assert(phead);

	for (pListNode temp = phead->next; temp != phead; temp = temp->next)
	{
		printf("%d ", temp->data);
	}
	printf("\n");
}


bool ListEmpty(pListNode phead)
{
	assert(phead);

	return phead == phead->next;
}
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

2.尾插尾删、头插头删

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	pListNode tail = phead->prev;
	pListNode newNode = CreateNode(x);

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

void ListPopBack(pListNode phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	pListNode tail = phead->prev;

	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
	tail = NULL;
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	pListNode newNode = CreateNode(x);
	pListNode first = phead->next;

	newNode->next = first;
	newNode->prev = phead;
	first->prev = newNode;
	phead->next = newNode;
}

void ListPopFront(pListNode phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	pListNode first = phead->next;

	phead->next = first->next;
	first->next->prev = phead;
	free(first);
	first = NULL;
}
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

3.查找、指定插入、指定删除

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x)
{
	assert(phead);

	for (pListNode find = phead->next; find != phead; find = find->next)
	{
		if (find->data == x)
		{
			return find;
		}
	}
	return NULL;
}

void ListInsert(pListNode pos, LTDataType x)
{
	assert(pos);

	pListNode newNode = CreateNode(x);
	pListNode prev = pos->prev;

	newNode->next = pos;
	newNode->prev = prev;
	pos->prev = newNode;
	prev->next = newNode;
}

void ListErase(pListNode pos)
{
	assert(pos);			// 非空时pos不能传入哨兵位，不然删除后会丢失整个链表
	assert(!ListEmpty(pos));

	pListNode prev = pos->prev;
	pListNode next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
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

四、代码优化

指定插入包含尾插头插，指定删除包含尾删头删。可以复用两者，提高代码复用率。

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead, x);
}

void ListPopBack(pListNode phead)
{
	assert(phead);

	ListErase(phead->prev);
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x);
}

void ListPopFront(pListNode phead)
{
	assert(phead);

	ListErase(phead->next);
}
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

五、完整 List.c 源代码

#include "List.h"

// 创建节点封装成函数
pListNode CreateNode(LTDataType x)
{
	pListNode temp = (pListNode)malloc(sizeof(ListNode));
	if (temp == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	temp->data = x;
	temp->prev = NULL;
	temp->next = NULL;

	return temp;
}

// 初始化、销毁、打印
pListNode ListInit()
{
	pListNode temp = CreateNode(-1);
	temp->next = temp;
	temp->prev = temp;

	return temp;
}

void ListDestroy(pListNode phead)
{
	assert(phead);

	pListNode temp = phead->next;
	while (temp != phead)
	{
		pListNode dest = temp->next;
		free(temp);
		temp = dest;
	}
	free(temp);
	temp = phead = NULL;
}

void ListPrint(pListNode phead)
{
	assert(phead);

	for (pListNode temp = phead->next; temp != phead; temp = temp->next)
	{
		printf("%d ", temp->data);
	}
	printf("\n");
}

bool ListEmpty(pListNode phead)
{
	assert(phead);

	return phead == phead->next;
}

// 尾插尾删、头插头删
void ListPushBack(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead, x);
}

void ListPopBack(pListNode phead)
{
	assert(phead);

	ListErase(phead->prev);
}

void ListPushFront(pListNode phead, LTDataType x)
{
	assert(phead);

	ListInsert(phead->next, x);
}

void ListPopFront(pListNode phead)
{
	assert(phead);

	ListErase(phead->next);
}

// 查找、指定插入、指定删除
pListNode ListFind(pListNode phead, LTDataType x)
{
	assert(phead);

	for (pListNode find = phead->next; find != phead; find = find->next)
	{
		if (find->data == x)
		{
			return find;
		}
	}
	return NULL;
}

void ListInsert(pListNode pos, LTDataType x)
{
	assert(pos);

	pListNode newNode = CreateNode(x);
	pListNode prev = pos->prev;

	newNode->next = pos;
	newNode->prev = prev;
	pos->prev = newNode;
	prev->next = newNode;
}

void ListErase(pListNode pos)
{
	assert(pos);				// 非空时pos不能传入哨兵位，不然删除后会丢失整个链表
	assert(!ListEmpty(pos));

	pListNode prev = pos->prev;
	pListNode next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/686303