[数据结构与算法]线性表 :: “有头”单链表的设计与实现（链式存储结构）

线性表 :: “有头”单链表的设计与实现（链式存储结构）

说明：本文属于读书笔记。笔者将以讲述的方式表达全片文章。故文中提到的某些字词是非正式术语，只是笔者本人的理解性词语。

线性表简介：想要了解点击此处

前言：指针的相关操作及理解在链表的设计中是一定会涉及。在本篇文章中，由于是设计“有头”链表，其对指针操作的理解不会太深，因此本篇不会分析指针的使用。相关内容将在无头单链表中叙述。

目录

• 从数组到链表
• 链式存储结构的简介
• 链表的设计
• 链表的实现
• • 结点设置
• • 创建结点
• • 插入新结点（尾插法、头插法、指定插入）
• • 遍历链表
• • 查找链表元素（数据查找）
• • 删除链表元素
• • 修改链表元素
• 结语
• 最终汇总代码

1. 从数组到链表

此前，笔者在前文已经基于数组实现了顺序存储结构。（点此阅读）显然，在我们实现顺序存储结构的过程中，基于性能考虑，增加和删除数据元素时的时间复杂度时O(n)。设想一个夸张的例子，在一个大小为10000，且已存储9000个数据元素，如果我们要在第二个位置增加和删除操作是什么概念？就好比你有10000本书自下而上重叠在一起，此时，你要拿从下往上数的第二本书，额~

上述了例子或许不太恰当，但是我们明确一下我们的目的：能不能让增删的性能，像查改一样简单，或者说能比当前的操作速度更快？

此前，我们实现的顺序存储结构其特点是：用一段 地址连续的存储单元 依次存储线性表的数据元素，且查改时间复杂度为 O(1)。
本篇内容将设计并实现链表，打破使用一段连续的内存单元存储数据，并提高增删的性能。

2. 链式存储结构的简介

2.1 特点

用一组任意的存储单元存储线性表中的数据元素。其中，任意存储单元可以是连续的，也可以是不连续的。说白了，就是数据看也放在内存未被占用的任何位置，只要能让其数据连成“串”即可。（如下图）

3. 链表的设计

3.1 链表结构的特点

链表（如上图所示），就是将一些杂乱摆放的数据连成一个“串”。

3.2 设计思考过程

此时问题来了！这玩意儿用眼睛看肯定是没问题，“串”就完了。那这些数据在内存中的什么位置，我怎么知道。在数组中我们是根据数组首元素地址与偏移量计算得知其他元素的位置，现在没了层关系，咋搞？

设想一个情景，假设原来的数据单元就是一排连续的房子，它的地址就相当于门牌号。只不过门牌号是连续的。在链式存储结构中，此时门牌号不连续了，我们同理只要知道门牌号是多少就可以了。如上图所示，由前一个元素到后一个元素是有一个箭头指向的，说明通过前一个元素，可以去到后一个元素。那在实现链表过程中，我们把后一个元素的地址告诉前一个元素不就OK了吗。

3.3 结构设计

如果要实现同时存储一个元素和另一个元素的地址，怎么做？简单嘛，数组不就完了！建立一个大小为 2 的数组（arr），首元素存储数据元素，次元素存储地址就OK。要打印元素值，访问 arr[0] ，要找其他元素，访问 arr[1]。如下图。

以数组的方式封装元素和地址可行是可行，但是没必要，有个东西叫结构体！！！

4. 链表的实现

4.1 结点设置

单个结点，就是链表中的小房子，分为数据域（存储数据）、指针域（存储地址）

struct Node{
	int data;				/* 数据域 */
	struct Node* next;		/* 指针域 */
};

4.2 创建结点

创建结点无须多言，就是给数据一套房。此时，只需要让数据入住，单个结点的创建不涉及后续结点，故指针域为空！

操作步骤：

1. 动态申请内存空间。（建房）
2. 存储数据。（数据入住）
3. 指针域置空。
4. 返回结点。

struct Node* CreateNode(int data){
	// 1. 动态申请内存空间
	struct Node* pnew = (struct Node*)malloc(sizeof(struct Node));
	// 检验申请失败（一般不会）
	if(NULL == pnew) return;
	// 2. 存储数据
	pnew->data = data;
	pnew->next = NULL;
	// 3. 返回结点
	return pnew;
}

4.3 插入数据

数据插入是链表中的一个难点，推荐大家画图理解！！！
数据的插入方式无非三种：头部插入、尾部插入、指点插入（中间插入）

4.3.1 尾部插入

咱先挑个软柿子捏！

尾部插入（如下图）：当在尾部插入时，我们仅需找到当前链表的尾结点，然后将新结点往上一挂就完了！

情况分析：

1. 如何找到尾结点；

可以通过遍历的方式直接实现！从头结点开始，找到 [ next ] 的指向，即可找到第一个结点；同理，访问第一个结点的 [ next ] 的指向，即可找到第二个结点以此类推！直到 [ next ] 的指向为空，此时说明到达尾部！

2. 如果插入的链表为空，怎么处理？

当链表为空时，此时我们只有一个头结点，且 [ next ] 的指向就是空！那直接挂上去就好了。

3. 参数分析：毋庸置疑，操作对象得知道吧！既然是插入，新数据得有吧！

实现步骤：

1. 创建新结点；
2. 判断链表是否为空；（为了操作方便，下图，引入指针游标。）

小难点：游标指针 ptemp 与 ptemp->next （关系如上图）；说明：当 ptemp 指向某一个结点时，ptemp->next 即可表示当前结点的指针域，又可表示下一个结点。

3. 链表不为空时，遍历寻找尾结点；

难点：如何实现指针移动，思路 传递（联想三个变量实现两个数值交换）看代码！ ！

void appendNode(struct Node* pHead,int data){
	// 1. 创建新节点
	struct Node* pnew = createNode(data);
	// 定义一个游标指针
	struct Node* ptemp = pHead;
	// 2. 判断链表是否为空，为空直接挂上并退出
	if (NULL == ptemp->next){
		ptemp->next = pnew;
		return;
	}
	// 3. 链表不为空时，遍历寻找尾结点
	while(ptemp->next){
		ptemp = ptemp->next;	/* 核心代码！！！ */
	}
	// 4. 挂新结点
	ptemp-next = pnew;
}

上述代码，是根据设计思路按部就班的实现的，不可避免有所瑕疵！！！
仔细看可以发现，我们对尾部的判断有两次（链表为空，头结点就等价于尾结点），同时，新结点的加入也是有两次。完全没必要，直接合并就好了。（实现优化，如下！（说明：后续将不再单独展现按部就班的代码，直接操作优化后的！））

void appendNode(struct Node* pHead,int data){
	// 1. 创建新节点
	struct Node* pnew = createNode(data);
	// 定义一个游标指针
	struct Node* ptemp = pHead;
	// 2. 判断链表是否为空，为空直接挂上并退出
	// 3. 链表不为空时，遍历寻找尾结点
	while(ptemp->next){
		ptemp = ptemp->next;	/* 核心代码！！！ */
	}
	// 4. 挂新结点
	ptemp->next = pnew;
}

4.3.2 头部插入

头插法相较于尾插法多了一个操作，就是 挂点 ，防止链表元素丢失。

例如：山洪暴发后，营救员们发现，激流中的某个石块上有待救人员，于是他们采取用手拉手的方式取营救。在营救过程中发现距离不足，就需要有人加入这个营救链中（如上图中的 J ）。显然，如果 J 先取牵 A ，那 A 需要腾出手与 J 相牵，很明显，如果此时 A 撒手去牵 J ，那在激流中的队友就要噶了，会被冲走。那 J 先去牵 B （ J 在岸上 ），就可以使河中队友不被冲跑，此时， A 再与 J 牵手，J 下河就可以加长营救链了。

上述，瞎掰的例子虽然不切实际，额~，懂大概的意思就行。就是在链表处于非空状态时，新插入的结点的链接方式。J 新结点 应先链接 B 结点，再与 A 结点相连，从而实现数据不丢失。（代码实现如下（步骤见代码中注释！）。）

void addNode(struct Node* pHead,int data){
	// 1. 申请新结点
	struct Node* pnew = createNode(data);
#if 0
	// 2. 链表为空直接返回
	if(NULL == pHead->next) return;
#else
	// 2. 链表为空，直接挂上（此方案可以不要）
	if(NULL == pHead->next) {
		pHead->next = pnew;
		printf("链表为空！自动将新结点置于第一个结点！\n");
		return;
	}
#endif
	// 3. 链表不为空，执行营救行动！
	pnew->next = pHead->next;
	pHead->next = pnew;
}

4.3.3 指定插入

指定插入的特殊之处就是指定位置！！！

假设指定位置尾 i ：
i <= 1：即头插法；
i >= 链表长度：即尾插法；
i = 其他：即中间插入

思路步骤看代码注释！！！

void posNode(struct Node* pHead,int pos,int data){
	// 1. 判断链表是否为空
	if(NULL == pHead->next) return;
	// 2. 创建新结点
	struct Node* pnew = createNode(data);
	// 3. 寻找插入位置
	for(int i = 0; i < pos-1; i++){
		// 如果循环过程中发现到达尾结点就直接挂新结点并退出
		if(NULL == pHead->next) break;
		pHead = pHead->next;	
	}
	// 4. 挂结点（营救思路）
	pnew->next = pHead->next;
	pHead->next = pnew;
}

4.4 遍历链表

在此前的实现过程中起始已经有了！这里直接给出代码。

//遍历链表
void travel(struct Node* pHead){
	if (NULL == pHead) {
		printf("链表为空！\n");
		return;
	}
	struct Node* ptemp = pHead->next;//略过头
	printf("List:");
	while (ptemp){
		printf("%d ", ptemp->data);
		ptemp= ptemp->next;//指向下一个节点
	}
	printf("\n");
}

4.5 查找链表元素（数据查找）

说明：本篇仅实现数据查找并返回，不实现数据查找（匹配），该功能将在 LeetCode 算法系列 中实现。

查找指定元素，在此由于元素可能出现重复，此处仅实现返回第一个查找到的元素。（实现思路和步骤见代码注释！）

struct Node* findNode(struct Node* pHead, int findData){
	// 1. 判断链表是否为空
	if (NULL == pHead) return NULL;
	// 2. 略过头节点（使用游标）
	pHead = pHead->pNext;
	// 3. 寻找指定值（找到就返回地址，没找到就返回null）
	while (pHead){
		if (findData == pHead->data) return pHead;
		pHead = pHead->pNext;
	}
	return NULL;
}

4.6 删除链表元素

删除又是链表操作中的一个难点！！！

1. 得找删除元素（前文中已实现）；
2. 删除与添加有所区别！！！
   由于找到的是删除的目标结点，理论上我们还需要找到目标结点的前后结点，便于链接，防止数据丢失！

实现思路和步骤见代码注释！

void deleteNode(struct Node* pHead,int aimdata){
	// 1. 查找到目标值
	struct Node* pDel = findNode(pHead,aimdata);
	// 2. 如果返回为 NULL 即操作目标不在链表中
	if(NULL == pDel) return;
	// 3. 设置游标，目的是找到操作目标的前一个结点
	struct Node* pDel_prev = pHead;	/* 此处注意！！！ */
	while(pDel_prev->next != pDel){
		pDel_prev = pDel_prev->next;
	}
	// 4. 上述循环结束，即找了操作对象
	/*
		此时 pDel_prev 表示删除结点的前一个结点
		pDel_prev->next 可以表示被删除的结点
		pDel 表示被删除的结点
		pDel->next 表示被删除结点的后一个结点
		链接思路：被删除的前一个结点先链接被删除结点的后一个结点，再释放被删除结点！！！
	*/
	pDel_prev->next = pDel->next;
	free(pDel);
	printf("删除成功！\n");
}

4.7 修改链表元素

修改结点元素，无操作难度，因为前文已经实现了查找元素，找到了以后干就完了。（实现思路和步骤见代码注释！）

void changeNode(struct Node* pHead,int changedata,int aimdata){
	// 1. 查找到目标值
	struct Node* pChange = findNode(pHead,aimdata);
	// 2. 如果返回为 NULL 即操作目标不在链表中
	if(NULL == pChange ) return;
	// 3. 直接复制覆盖即可
	pChange->data = changedata;
	printf("修改成功!\n");
}

5. 结语

1. 链表的性能，与顺序存储或者说数组的性能恰恰相反。
2. 数组与链表都只是众多数据结构中的一种，都不是“万能”高效的，还是不得不说不要为了使用链表而用链表，应根据具体的数据与操作方式来定。比如，一个程序中，当查询修改的次数非常多，而增加删除较少时，当然选择用数组；反之，用链表呗。（当然还有其他的数据类型结构可选择。）
3. 链表在以后的实际操作中一般不会让你现敲，最多再面试（可能只是校内实验室的，企业级的别想了，太 low ），或者刷算法题时使用，因此本文主要是因重在理解设计过程和实现时优化代码的一种思路。链表嘛，写过的人那么多，人家搞好了，封装好了直接用就完了。（当然本文只是笔者根据自己的理解来设计的，不可能会适合所有人理解，甚至说我的理解都可能是有问题的，只不过能写出代码并运行。）
4. 本篇只是简单的实现链表的基础操作，而实际中我们可能对链表的操作还包括元素匹配、排序等情形！这些功能的实现将会在后续更新并收纳在 LeetCode 算法系列 中和微信公众号。

无头单链表的设计与实现
双链表的设计与实现

实操系列与功能补充指引！（待更新）

1. 计数功能的实现。相关文章地址 => 双链表的设计与实现

6. 最终汇总代码

#include<stdio.h>

typedef int DataType; 	/* 实现便利修改操作的数据类型 */
// 结点构造
struct Node{
	DataType data;				/* 数据域 */
	struct Node* next;		/* 指针域 */
};

struct Node* createNode(DataType);
void appendNode(struct Node*,DataType);
void addNode(struct Node*,DataType);
void travel(struct Node*);
struct Node* findNode(struct Node*, DataType);
void deleteNode(struct Node*,DataType);
void changeNode(struct Node*,DataType,DataType);
void posNode(struct Node*, int, DataType);

// 主函数
int main()
{
	// 测试演示代码
	struct Node* plist = NULL; 	/* 创建指针 */
	/* 初始化头结点，数据任意，操作过程中不会访问 */
	plist = createNode(0);		
	addNode(plist, 555);
	travel(plist);
	for (int i = 0; i < 5; i++)
	{
		appendNode(plist, i * 2);
		travel(plist);
	}
	addNode(plist, 666);
	travel(plist);
	posNode(plist, 0, 111);
	travel(plist);
	posNode(plist, 1, 1111);
	travel(plist);
	posNode(plist, 2, 222);
	travel(plist);
	posNode(plist, 1000, 10000);
	travel(plist);
	while (1);
	return 0;
}

// 创建结点
struct Node* createNode(DataType data){
	// 1. 动态申请内存空间
	struct Node* pnew = (struct Node*)malloc(sizeof(struct Node));
	// 检验申请失败（一般不会）
	if(NULL == pnew) return;
	// 2. 存储数据
	pnew->data = data;
	pnew->next = NULL;
	// 3. 返回结点
	return pnew;
}

// 尾插法
void appendNode(struct Node* pHead,DataType data){
	// 1. 创建新节点
	struct Node* pnew = createNode(data);
	// 定义一个游标指针
	struct Node* ptemp = pHead;
	// 2. 判断链表是否为空，为空直接挂上并退出
	// 3. 链表不为空时，遍历寻找尾结点
	while(ptemp->next){
		ptemp = ptemp->next;	/* 核心代码！！！ */
	}
	// 4. 挂新结点
	ptemp->next = pnew;
}

// 头插法
void addNode(struct Node* pHead,DataType data){
	// 1. 链表为空直接返回
	if(NULL == pHead->next) return;
	// 2. 申请新结点
	struct Node* pnew = createNode(data);
	// 3. 链表不为空，执行营救行动！
	pnew->next = pHead->next;
	pHead->next = pnew;
}

// 指定插入
void posNode(struct Node* pHead,int pos,DataType data){
	// 1. 判断链表是否为空
	if(NULL == pHead->next) return;
	// 2. 创建新结点
	struct Node* pnew = createNode(data);
	// 3. 寻找插入位置
	for(int i = 0; i < pos-1; i++){
		// 如果循环过程中发现到达尾结点就直接挂新结点并退出
		if(NULL == pHead->next) break;
		pHead = pHead->next;	
	}
	// 4. 挂结点（营救思路）
	pnew->next = pHead->next;
	pHead->next = pnew;
}

// 遍历链表
void travel(struct Node* pHead){
	if (NULL == pHead) {
		printf("链表为空！\n");
		return;
	}
	struct Node* ptemp = pHead->next;//略过头
	printf("List:");
	while (ptemp){
		printf("%d ", ptemp->data);
		ptemp= ptemp->next;//指向下一个节点
	}
	printf("\n");
}

// 查找元素
struct Node* findNode(struct Node* pHead, DataType findData){
	// 1. 判断链表是否为空
	if (NULL == pHead) return NULL;
	// 2. 略过头节点（使用游标）
	pHead = pHead->next;
	// 3. 寻找指定值（找到就返回地址，没找到就返回null）
	while (pHead){
		if (findData == pHead->data) return pHead;
		pHead = pHead->next;
	}
	return NULL;
}

// 删除结点
void deleteNode(struct Node* pHead,DataType aimdata){
	// 1. 查找到目标值
	struct Node* pDel = findNode(pHead,aimdata);
	// 2. 如果返回为 NULL 即操作目标不在链表中
	if(NULL == pDel) return;
	// 3. 设置游标，目的是找到操作目标的前一个结点
	struct Node* pDel_prev = pHead;	/* 此处注意！！！ */
	while(pDel_prev->next != pDel){
		pDel_prev = pDel_prev->next;
	}
	// 4. 上述循环结束，即找了操作对象
	/*
		此时 pDel_prev 表示删除结点的前一个结点
		pDel_prev->next 可以表示被删除的结点
		pDel 表示被删除的结点
		pDel->next 表示被删除结点的后一个结点
		链接思路：被删除的前一个结点先链接被删除结点的后一个结点，再释放被删除结点！！！
	*/
	pDel_prev->next = pDel->next;
	free(pDel);
	printf("删除成功！\n");
}

// 修改链表元素
void changeNode(struct Node* pHead,DataType changedata,DataType aimdata){
	// 1. 查找到目标值
	struct Node* pChange = findNode(pHead,aimdata);
	// 2. 如果返回为 NULL 即操作目标不在链表中
	if(NULL == pChange ) return;
	// 3. 直接复制覆盖即可
	pChange->data = changedata;
	printf("修改成功!\n");
}

运行截图