链表定义

链表是一种线性表数据结构；
从底层存储结构上看，链表不需要一整块连续的存储空间，而是通过“指针”将一组零散的内存块串联起来使用；
链表中的每个内存块被称为链表的“结点”，每个结点除了要存储数据外，还需要记录上(下)一个结点的地址。

链表特点

插入、删除数据效率高，只需要考虑相邻结点的指针改变，不需要搬移数据，时间复杂度是 O(1)。
随机查找效率低，需要根据指针一个结点一个结点的遍历查找，时间复杂度为O(n)。
与内存相比，链表的空间消耗大，因为每个结点除了要存储数据本身，还要储存上(下)结点的地址。

常用的链表类型

链表结构五花八门，常用的有三种：单链表、循环链表、双向链表和双向循环链表。
单链表

如图所示：
单链表的每个节点只包含一个后继指针；
单链表的头结点和尾结点比较特殊，头结点用来记录链表的基地址，是链表遍历的起点，尾结点的后继指针不指向任何结点，而是指向一个空地址NULL。
单链表的插入、删除操作时间复杂度为O(1)，随机查找时间复杂度为O(n)。

循环链表
循环列表是一种特殊的单链表，它跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点，首尾相连，形成了一个环，所以叫做循环链表。

与单链表相比，循环链表的优点是从链尾到链首比较方便，适用于处理具有环形结构的数据问题，比如著名的约瑟夫问题。
双向链表
双向链表中的每个结点具有两个方向指针，后继指针(next)指向后面的结点，前驱指针(prev)指向前面的结点。
双向链表也有两个特殊结点，首节点的前驱指针和尾结点的后继指针均指向空地址NULL。

与单链表相比，储存同样的数据，双向链表会占用更多的内存空间。虽然多占用了空间，但是双向链表在处理根据已知结点查找上一节点、有序链表查找等问题上，都表现的更灵活高效。
双向循环链表

链表&数组对比

数组缺点
数组必须占用整块、连续的内存空间，如果声明数组过大，可能会导致“内存不足”。
数组不够灵活，一旦需要扩容，会重新申请连续整块空间，并需要把原数组的数据全部拷贝到新申请的空间。

链表缺点
内存空间消耗更大，用于储存结点指针信息。
对链表进行频繁的插入、删除操作会导致频繁的内存申请、释放，容易造成内存碎片，如果是JAVA语言，还有可能会导致频繁的GC（Garbage Collection，垃圾回收）。

参考文档：
http://www.chinacion.cn/article/4419.html