初阶数据结构：链表

1. 引子：什么是链表

经过学习与练习，已经掌握了顺序表的相关知识并且能够自我实现。在这一过程中，通过对其结构的实现，发现顺序表的尾部插入删除数据效率很高，可是，在头部与随机插入的场景下效率低下而且存在扩容消耗等一些问题。而有这样一种数据结构可以很好的解决顺序表存在的这些问题，将琐碎的系统空间充分利用，任意位置的插入删除效率都很高。此种数据结构称为链表，接下来进行对其的学习。

2. 简单数据结构：链表

2.1 链表简介与功能分析

简介：

链表，正如其名，存储其中的数据在物理上是离散的，各个数据间使用一条 “链子” 串联而成（记录下一元素地址的指针）。链表的具体结构存在数种，以是否带头，是否能双向访问，是否循环，这三个特点被简单分为六种，下面，我们先进行其中一种，带头单向不循环链表进行学习。

单向带头不循环链表结构图：

功能分析模块：

数据存储方式：

1. 动态开辟malloc的一块块小内存块。
2. 存储信息为数据值，与记录下一个结点的指针
   以上两点创建的结点结构体

数据管理方式：

1. 增（头插，尾插，随机插入）：push_front，push_back，insert，insertafter
2. 删（头删，尾删，随机删除）：pop_front，pop_back，erase，eraseafter
3. 改（指定数据的修改）：modify
4. 查（指定数据的查询）：find

2.2 单链表的实现

2.2.1 单链表：存储数据的结构体

链表结点的构建：

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType val;
	//声明类型的过程中不能直接使用typedef后的名字
	struct ListNode* next;
}ListNode;

1
2
3
4
5
6
7
8
9

2.2.2 单链表：结点创建与链表数据清理

结点创建：

ListNode* BuyNewNode(ListDataType val)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}

	newnode->val = val;
	newnode->next = NULL;

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

链表销毁：

过程演示：

//链表销毁
void ListDestroy(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;

	ListNode* cout = Phead;

	if (Phead != NULL)
	{
		while (Phead->next != NULL)
		{
			Phead = Phead->next;
			free(cout);
			cout = Phead;
		}

		free(Phead);

		*PPhead = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注：Phead为list的一份值拷贝，因此要想能够改变list（链表头）的值，传参是我们应该采用二重指针传址传参。

2.2.2 单链表插入数据与删除

头插，头删：

头插过程演示：

链表为空时头插：

链表不为空时头插：

头删过程演示：

//头插
void ListPush_Front(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;

	ListNode* newnode = BuyNewNode(val);

	if (Phead == NULL)
	{
		*PPhead = newnode;
	}
	else
	{
		ListNode* next = Phead;
		newnode->next = Phead;
		*PPhead = newnode;
	}
}


//头删
void ListPop_Front(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* next = Phead->next;
	
	free(Phead);
	*PPhead = 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

尾插，尾删：

//尾插
void ListPush_Back(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	
	ListNode* end_node = Phead;
	while (end_node != NULL && end_node->next != NULL)
	{
		end_node = end_node->next;
	}

	ListNode* newnode = BuyNewNode(val);
	if (end_node == NULL)
	{
		*PPhead = newnode;
	}
	else//end_node->next == NULL
	{
		end_node->next = newnode;
	}

}

//尾删
void ListPop_Back(ListNode** PPhead)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* end_node = Phead;
	//特殊情况
	if (end_node->next == NULL)
	{
		free(end_node);
		*PPhead = NULL;
	}
	else//end_node->next != NULL
	{
		//逻辑短路
		while (end_node->next->next != NULL)
		{
			end_node = end_node->next;
		}

		free(end_node->next);
		end_node->next = 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

随机插入与删除：

在指定结点（pos）之前插入：

void ListInsert(ListNode** PPhead, ListNode* pos, ListDataType val)
{
	//不考虑结点不存在的情况
	//与ListFind模块配合使用
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);
	assert(pos);
	
	//复用头插
	if (pos == Phead)
	{
		ListPush_Front(PPhead, val);
	}
	else
	{
		ListNode* search = Phead;
		//寻找pos结点
		while (search->next != pos)
		{
			search = search->next;
		}
		
		//插入
		ListNode* newnode = BuyNewNode(val);
		ListNode* next = search->next;
		
		search->next = newnode;
		newnode->next = 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

在指定结点（pos）之后插入：

void ListInsertAfter(ListNode* pos, ListDataType val)
{
	//结点不能为NULL
	assert(pos);

	ListNode* next = pos->next;

	ListNode* newnode = BuyNewNode(val);

	pos->next = newnode;
	newnode->next = next;
}
1
2
3
4
5
6
7
8
9
10
11
12

删除指定结点（pos）之后的结点：

void ListEraseAfter(ListNode* pos)
{
	assert(pos);
	assert(pos->next);

	ListNode* next = pos->next;
	pos->next = pos->next->next;

	free(next);

	next = NULL;

	pos->next = next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

删除指定结点（pos）：

void ListErase(ListNode** PPhead, ListNode* pos)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);
	assert(pos);
	
	//头删
	if (pos == Phead)
	{
		ListPop_Front(PPhead);
	}
	else
	{
		ListNode* search = Phead;
		while (search->next != pos)
		{
			search = search->next;
		}

		ListNode* next = search->next->next;

		free(search->next);
		search->next = 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

2.2.3 单链表查询与修改

元素查询：

ListNode* ListFind(ListNode** PPhead, ListDataType val)
{
	assert(PPhead);
	ListNode* Phead = *PPhead;
	assert(Phead);

	ListNode* search = Phead;
	while (search != NULL && search->val != val)
	{
		search = search->next;
	}

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

数据修改：

void ListModify(ListNode* Node, ListDataType val)
{
	assert(Node);

	Node->val = val;
}
1
2
3
4
5
6

链表元素打印：

void ListPrint(ListNode* Phead)
{
	while (Phead != NULL)
	{
		printf("%d->", Phead->val);
		Phead = Phead->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9