朱岩松博客

导读：本文通过举出现实生活中的例子和代码实现的程序帮助你更好的理解链表（链式存储结构实现的线性表）

数据结构中，线性表的实现方式有两种：顺序存储方式和链式存储方式。我们今天讨论学习的是链式存储方式实现的线性表。

链式存储结构的线性表称为链表，链表主要有单链表、循环单链表和双向循环链表三种，其中，单链表是最经常使用的链表。

链式存储结构的主要概念：

单链表中，构成链表的结点只有一个指向直接后继结点的指针域。

如果你想要理解这句话的意思，那你先要弄清楚链表的大致概念。我们都知道顺序表（顺序存储结构实现的线性表）是由连续地址的内存空间构成的，而链表（链式存储结构实现的线性表）是由不连续地址的内存空间构成的，这就使得我们不能直接通过访问下一个内存空间来访问下一个数据。我们就需要让它指出下一个内存空间的地址，这样我们才可以去找到它的下一个内存空间的地址。

听起来好像很复杂吧，但是它其实并不难而且对比顺序表他的删除和插入是非常快的，这是因为顺序在插入和删除数据时需要将被操作的位置后的所有数据均往后或往前移动一个位置，所以他要动用的资源是很庞大的。而链表则只需要在插入或删除操作后更改这个位置要链接到的下一个位置。

打个比方，顺序表就好比幼儿园的小朋友排队，如果老师要从中间拉走或者挤进去一个小朋友，那么这个小朋友后面的所有人都需要往前走一步或者往后退一步。而链表则好比幼儿园的小朋友手拉手围成一个大圈做游戏，这些课余游戏大家可能也还真玩过。如果需要加入一个人或者退出一个人，只需要加入或者退出的哪个位置的两个小朋友换一个拉手的对象而已。这就是链表的概念。

而什么是单链表呢？

单链表就是这群手拉手的小朋友只知道自己下一个要拉手的对象是谁，而不知道自己上一个要拉手的对象是谁。但是仅知道下一个要拉手的对象是谁就可以将他们串在一起了。这就是单链表的概念。

而什么是循环单链表呢？

循环单链表就是在单链表的基础上，最后一个拉手的小朋友拉手的对象是他们第一个开始拉手的同学，这就使得他们整体变成了一个可以进行无限传递的结构。这就是循环单链表的概念。

单链表和循环单链表的区别是什么？

单链表是有结束标记的，而循环单链表则是最后一个位置链接到整个链表的首个位置取。比如我丢一个花球让第一个同学一直往后传，单链表的例子中传到最后一个同学就结束了，因为他后面没有人了，这就是单链表的结束标记。而循环单链表的例子中则没有结束标记。而是整个链表的第一个结点。

什么是头结点，什么是头指针？

存放第一个元素的结点称为第一个元素结点，而头结点则是在这个元素结点之前，它不存放任何数据，仅仅指向第一个元素结点。而指向这个结点的指针称为头指针。鉴于链表的特性，知道了头指针便可访问整个链表，因此头指针是必须存在的。而头结点并不一定必须存在。

而头结点存在可以使得头指针的地址总是不变的。例如我们需要再在链表的第一个位置插入一个数据进去，如果没有头结点，我们的头指针的位置便会由于这个数据的插入变成这个结点，而有了头结点，头指针的位置永远不会改变。

这就好比我们大家手拉手站成一排举行活动，为了方便校长区分班级，老师在第一排放个班牌作为标识，即便排头的人变换，班牌总是不变的，校长一眼便能知道是哪个班级。但如果没有班牌，即便校长记住了每个班级第一个人长什么样子，但这个班级的第一个人出现变化，它的标识便也会随之改变，校长也就不认识咯。

什么是双向循环链表？

单链表是每个数据结点指向下一个数据结点的位置，而双向链表则是每个结点除了指向后一个数据结点位置，还指向前一个结点的位置。双向链表也有循循环和非循环的两种结构，相对于上面的例子，双向循环链表就是每个站队拉手的小朋友不仅知道后一个要拉的是谁，也知道前一个要拉的人是谁。单链表的例子中，每个小朋友要知道后面一个人是谁很容易，但是要想知道前一个人是谁就不得不从第一个人的位置（头结点）重新往后查找。而双向链表则可以很好的解决这个问题。双向循环链表就是在双向链表的基础上最后一个结点指向第一个结点。

以上就是链表的概念，理解了概念后，我们就可以使用代码实现。

单链表的操作实现

由于链表的特性，每个结点是需要时才会向系统申请的，这称作动态内存空间申请。注意：动态申请的内存空间，当不再需要时，必须由申请者自己释放。

C语言中，动态申请内存空间的函数为malloc(unsigned size) malloc的作用是向系统动态申请大小为size字节的内存空间，返回值为申请内存空间的首地址。

malloc函数需要给定参数size，即所需要申请内存空间的大小。因此我们需要知道我们的链表结点类型占用的内存大小，使用C语言提供的sizeof()运算符，它可以返回给出的已定数据类型占用的字节个数。

单链表的节点定义

struct Node{
int data;
struct LsNode *next;
}LsNode;

这里是