链表是一种逻辑上连续和顺序，但在物理存储时非连续、非顺序的数据结构。
从概念的角度出发，我们可以将链表与数组作比较。数组是在逻辑上和物理上都连续和顺序的数据结构，也就是说，如果我们知道了数组中的元素B在元素A之后一个逻辑单位，那么我们就可以通过A的物理存储位置加上一个物理存储单位(例如，INT8即为8个字节)，即可得到B的物理存储位置。而链表则仅保持了逻辑顺序上的连续，即我们可以通过A得到指向B的指针或者引用，但我们无法直接通过A的物理位置得到B的物理位置。
在链表中，每个元素有两个基本部分，一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。通常命名为
value和next。
图解单向链表
以上定义的链表中一个元素只能推得它的后继next，因此又称为单向链表。
所谓链表，在英文命名中称作Linked List，但我们可以用一种更形象的命名Chained List。后者有何不同呢？我们可以想象一串被铁链串起来的圆环，就可以很形象地理解。所谓Chained，就是被铁链串起来的意思。
图例1.png
但是，只是被铁链串起来，不能充分表示一个单向链表，因为我们能够看见这条铁链上的所有圆环，并且每个圆环的前一个圆环和后一个圆环都被暴露在我们面前，这与单向链表的定义不符。因此，我们引入了两个黑盒，可以将当前圆环以外的其他圆环屏蔽，这样我们就看不到这条圆环链的全貌。此外，定义一个取出方向，使得我们只能从当前圆环遍历到后一个圆环，而不能反向获得前一个圆环。
单向链表.png
题外话：思考一下取出这个圆环链的人和将圆环链放入黑盒的人是同一个人吗？ —— 并不是，放入圆环链的人是数据的生产者，而取出圆环链的人是数据的消费者。为了保证消费一个链表的数据时满足链表的前提（即除了当前的元素，其余元素对消费者应该是不可见的），通常消费者不应是生产者自己。
双向链表
在单向链表的基础之上，通过在元素内部额外维护一个prev成员，我们就可以从当前元素遍历到前一个元素，由此形成的新的链表结构称为双向链表。
上述单向链表的解释中，我们提到了两个黑盒和定义取出方向的作用。现在，如果我们要求用类似的方法实现双向链表呢？很简单，我们只需要允许取出和放回圆环，就可以达到双向遍历的目的。
双向链表.png
循环链表
单向链表的另一个变种，它的特点是最后一个元素的next指针指向了头元素，达到了“循环”的效果。
为了实现循环链表，我们不再需要两个黑盒，只保留一个黑盒来保证循环，并需要引入一个tail圆环表明暴露在外的尾节点。当tail圆环被取出后，下一个被取出的就将是head节点。
循环链表.png
