对于数据结构，其实学过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内核里链表的实现。
队列、栈、树、图、散列表