背景

对于数据结构，其实学过C语言的都不陌生，无外乎就队列、栈、二叉树等等这些。但其实对于初学者最困惑的不是数据结构是怎么样的，而是数据结构有什么用？我自己也是工作好几年后才体验到数据结构的快乐。所以本系列文章重点从应用场景切入，让大家理解数据结构的好处。

简介

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由于在物理存储上可以以非连续状态存在，使得链表变得极其灵活。同时，链表就是C语言指针最完美的表现形式之一。常见的链表形式有两种，单向链表和双向链表。

• 单向链表

一个节点数据带一个链接信息，如下图所示，链路方向只有一个，只能一直往后链，查找方式也只能从头到尾地遍历，无法反向查找。

• 双向链表

一个节点数据带两个链接信息，一个用于链接下个节点，一个用于链接上个节点，这种结构使得可以从任意一个节点找到另个一个节点的数据。



单向链表和双向链表，其实这只是链表在顺序队列中结合的体现，实际链表的应用远不止这两种，它可以跟任意一种数据结构结合，比如树，二叉树的应用很大程度依赖于链表的实现。还有一些散列表，也可以由链表实现。

应用场景

链表应用面极为广泛，上面已经教你学会1+1=2，接下来要开始来做微积分了。举个GUI设计的场景，假设现在让你做一个显示屏，用户可通过拉取按键组件自己编辑界面内容，而你要做的，就是把用户编辑的内容显示出来，那应该怎么做？我们先用普通方式来实现。

#include <stdint.h>

/* 定义按键创建的最大个数 */
#define BUTTON_MAX_NUM			100

/* 按键的内置信息 */
struct tagButtonPrv
{
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

/* 首先得有个按键的结构对象 */
struct tagButtonCB
{
	struct tagButtonPrv Member[BUTTON_MAX_NUM];
	uin32_t Num;
};

struct tagButtonCB Button;

/* 用户创建按键信息 */
void CreateButton(struct tagButtonPrv data)
{
	Button.Member[Button.Num].StartX = data.StartX;
	Button.Member[Button.Num].StartY = data.StartY;
	Button.Member[Button.Num].EndX = data.EndX;
	Button.Member[Button.Num].EndY = data.EndY;
	…………
	
	Button.Num++;
}

/* 根据按键信息显示按键 */
void DisplayButton(struct tagButtonPrv* data)
{
	/* 显示的相关操作，这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	struct tagButtonPrv data;
	data.StartX = 0;
	data.StartY = 0;
	data.EndX = 100;
	data.EndY = 100;
	…………

	CreateButton(data);
	
	while(1)
	{
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (uint32_t i = 0; i < Button.Num; i++)
		{
			DisplayButton(&Button.Member[i]);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码，重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

上面这种实现方式有个很明显的问题，就是按键数量的上限是固定的，如果此时用户想要编写一个庞大的工程时，100个按键可能完全不够用。所以这里动态分配空间的方式来实现，再加上一个指针的链接信息，就可以组成一个链表。

#include <stdint.h>

/* 按键的内置信息 */
struct tagButtonPrv
{
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

struct tagButton
{
	struct tagButtonPrv Member;
	struct tagButton *Next;			/* 链接信息 */
};

struct tagButton *ButtonHead = NULL;

/* 用户创建按键信息 */
void CreateButton(struct tagButton *data)
{
	struct tagButton *i = ButtonHead;
	
	/* 查找到链表的尾部，把信息添加进去 */
	for (; i != NULL; i = i->Next);
	i = data;
}

/* 根据按键信息显示按键 */
void DisplayButton(struct tagButton* data)
{
	/* 显示的相关操作，这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	while(1)
	{
		/* 用户配置了按键后执行动作 */
		if (xxx)
		{
			struct tagButtonPrv *data = malloc(sizeof(struct tagButtonPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			…………
		
			CreateButton(data);
		}
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (struct tagButton *i = ButtonHead; i != NULL; i = i->Next)
		{
			DisplayButton(i);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码，重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

那再如果，现在要显示的不止是按键，还有文本框、图片等组件，此时作为不同组件封装的结构和所占空间大小是不一样的，如果要把它们都链接到同一个链里，以上面这种链表包含数据信息的写法是无法满足的，这里我们再来提一种实现方式，也是Linux操作系统里的经典链表应用，在数据信息里添加单独的链信息。

#include <stdint.h>

/* 链接信息单独封装 */
struct tagLink
{
	struct tagLink *Next;
};

/* 文本框的内置信息 */
struct tagTextPrv
{
	struct tagLink *Next;	/* 数据中插入链信息，要放在数据前面，方便后面操作 */
	
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	int8_t *Str;		/* 显示的文本内容 */
	…………
};

/* 按键的内置信息 */
struct tagButtonPrv
{
	struct tagLink *Next;	/* 数据中插入链信息，要放在数据前面，方便后面操作 */
	
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

/* 定义一个链头 */
struct tagLink *LinkHead = NULL;

/* 用户创建组件信息 */
void CreateComponent(void *data)
{
	struct tagLink *i = LinkHead;
	
	/* 查找到链表的尾部，把信息添加进去 */
	for (; i != NULL; i = i->Next);
	i = (struct tagLink *)data;
}

/* 根据组件信息显示组件 */
void DisplayComponent(void* data)
{
	/* 显示的相关操作，这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	while(1)
	{
		/* 用户配置了按键后执行动作 */
		if (xxx)
		{
			struct tagButtonPrv *data = malloc(sizeof(struct tagButtonPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			…………
		
			CreateComponent((void *)data);
		}

		/* 用户配置了文本框后执行动作 */
		if (xxx)
		{
			struct tagTextPrv *data = malloc(sizeof(struct tagTextPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			data->Str = "Hello!!";
			…………
		
			CreateComponent((void *)data);
		}
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (struct tagLink *i = LinkHead; i != NULL; i = i->Next)
		{
			DisplayComponent((void *)i);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码，重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

这里可能有人会问了，上面两个例子不都是实现功能了么，那两者有什么区别？第一种是链表中包含数据，而第二种是数据里面添加链接信息，所以可以任意给定链表中的数据长度。而且第二种方式，链表是可以单独封装成模块的，具体可以参考Linux内核里链表的实现。

总结

1. 链表一般由链接信息和数据两部分组成。
2. 在数据不连续且个数不确定的情况，可使用链表进行链接。
3. 根据不同的使用情况，链接信息可以有多个。所以链表可以与队列、树、图等其他数据结构结合使用。
4. 缺点：需要多一些空间用于存储链接信息，所以对于有序连续的数据，就没必要使用链表。

相关链接

队列

、栈、树、图、散列表