###链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但物理存储单元上非连续、
非顺序的存储结构，是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer),。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内
存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了
结点的指针域，空间开销比较大。
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分
(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点
存储地址的部分指向空值。
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次
访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提
供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除
一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。
对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾
节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个
对尾节点的引用，那么会简单很多。
前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也
可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），
另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。
在有序链表中插入和删除某一项最多需要O(N)次比较，平均需要O(N/2)次，因为必须沿着链
表上一步一步走才能找到正确的插入位置，然而可以最快速度删除最值，因为只需要删除表头
即可，如果一个应用需要频繁的存取最小值，且不需要快速的插入，那么有序链表是一个比较
好的选择方案。比如优先级队列可以使用有序链表来实现。
比如有一个无序数组需要排序，前面我们在讲解冒泡排序、选择排序、插入排序这三种简单的
排序时，需要的时间级别都是O(N2)。
现在我们讲解了有序链表之后，对于一个无序数组，我们先将数组元素取出，一个一个的插入
到有序链表中，然后将他们从有序链表中一个一个删除，重新放入数组，那么数组就会排好序
了。和插入排序一样，如果插入了N个新数据，那么进行大概N2/4次比较。但是相对于插入排
序，每个元素只进行了两次排序，一次从数组到链表，一次从链表到数组，大概需要2*N次移
动，而插入排序则需要N2次移动，
效率肯定是比前面讲的简单排序要高，但是缺点就是需要开辟差不多两倍的空间，而且数
组和链表必须在内存中同时存在，如果有现成的链表可以用，那么这种方法还是挺好的。
单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。
也可以用双向链表来实现双端队列。
上面我们讲了各种链表，每个链表都包括一个LinikedList对象和许多Node对象，
LinkedList对象通常包含头和尾节点的引用，分别指向链表的第一个节点和最后一个节点。
而每个节点对象通常包含数据部分data，以及对上一个节点的引用prev和下一个节点的引用
next，只有下一个节点的引用称为单向链表，两个都有的称为双向链表。next值为null则
说明是链表的结尾，如果想找到某个节点，我们必须从第一个节点开始遍历，不断通过next
找到下一个节点，直到找到所需要的。栈和队列都是ADT，可以用数组来实现，也可以用链表
实现。