数据结构与算法: 链表_链表适用于随机存取

使用数组包含以下限制：
线性表(数组):可以随机存储,存储密度高.但是要求连续空间,改变容量不方便.

在程序中使用之前，必须事先知道数组的大小。
增加阵列的大小是一个耗时的过程。在运行时扩展数组的大小几乎是不可能的。
数组中的所有元素都需要连续存储在内存中。在数组中插入任何元素都需要移动其所有前置元素。
链表是可以克服数组的所有限制的数据结构。使用链表很有用，因为，它动态分配内存。链表的所有节点都非连续地存储在内存中，并在指针的帮助下链接在一起。
大小不再是问题，因为我们不需要在声明时定义其大小。列表根据程序的需求增长，并限制为可用的内存空间。

头结点、头指针和首元结点

头结点：

有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

头结点和头指针的区别：

头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。