一口气搞懂「链表」，就靠这20+张图了 _链表

文章插图
作者 | 李肖遥
来源 | 技术让梦想更伟大（ID：TechDreamer）

说真的，任何说起嵌入式软件怎么入门啊？需要学些什么东西啊，我差不多一致的回答都是：软件方面C语言和数据结构加上一些简单常用的算法，这些需要学好。

借着自己的回顾学习，我也写一些基础的数据结构知识，多画图，少打字，与大家一起学习数据结构。

顺序存储和链式存储
数组—顺序存储数组作为一个顺序储存方式的数据结构，可是有大作为的，它的灵活使用为我们的程序设计带来了大量的便利；
但是，但是，数组最大的缺点就是我们的插入和删除时需要移动大量的元素，所以呢，大量的消耗时间，以及冗余度难以接受了。
以C语言数组插入一个元素为例，当我们需要在一个数组 {1,2,3,4} 的第1个元素后的位置插入一个’A’时，我们需要做的有：

将第1个元素后的整体元素后移，形成新的数组 {1,2,2,3,4}；
再将第2个元素位置的元素替换为我们所需要的元素’A’；
最终形成我们的预期，这需要很多的操作喔。

文章插图
上图可以看出，使用数组都有这两大缺点：

插入删除操作所需要移动的元素很多，浪费算力。
必须为数组开足够的空间，否则有溢出风险。

链表—链式存储由于数组的这些缺点，自然而然的就产生链表的思想了。
链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。
链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互串联，就形成了链表。

文章插图
其中 DATA 为自定义的数据类型，NEXT 为指向下一个链表结点的指针，通过访问 NEXT，可以引导我们去访问链表的下一个结点。
对于一连串的结点而言，就形成了链表如下图：

文章插图
上文所说的插入删除操作只需要修改指针所指向的区域就可以了，不需要进行大量的数据移动操作。如下图：

文章插图
相比起数组，链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现。

链表概述包含单链表，双链表，循环单链表，实际应用中的功能不同，但实现方式都差不多。

文章插图

单链表就像是美国男篮，一代一代往下传；
双链表像是中国男足，你传球给我，我传球给你，最终传给了守门员；
循环链表就像是中国男篮，火炬从姚明传给王治郅，王治郅传给易建联，现在易建联伤了，又传给了姚明。

单链表
单链表概念和简单的设计单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的，每个结点由元素和指针构成。
元素表示数据元素的映象，就是存储数据的存储单元；指针指示出后继元素存储位置，就是连接每个结点的地址数据。
以结点的序列表示的线性表称作线性链表，也就是单链表，单链表是链式存取的结构。
对于链表的每一个结点，我们使用结构体进行设计，其主要内容有：
其中，DATA数据元素，可以为你想要储存的任何数据格式，可以是数组，可以是int，甚至可以是结构体（这就是传说中的结构体套结构体）
NEXT为一个指针，其代表了一个可以指向的区域，通常是用来指向下一个结点，链表的尾部NEXT指向（空），因为尾部没有任何可以指向的空间了
故，对于一个单链表的结点定义，可以代码描述成：
//定义结点类型
typedef struct Node {
int data; //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
struct Node *next; //单链表的指针域
} Node,*LinkedList;
//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型