链表是线性表的一种。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中除了第一个和最后一个元素之外，所有元素是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。
数组是典型的顺序存储结构，而链式存储结构中两个元素在内存中可能不是相邻的，m诶个元素都有个指针域，存储着指向下一个元素的指针。这种存储方式的优点是定点插入和定点删除d 时间复杂度都是O(1)，不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存。缺点也很明显，即访问的时间复杂度是O(n)。
链表是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等。
- 双向链表JDK实现
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Dummy node是链表问题中一个重要的技巧，中文译作“哑节点”。
Dummy node是一个虚拟节点，也可以认为是标杆节点。它在单链表的表头head前加一个节点指向head，即dummy -> head。Dummy node解决单链表没有前向指针的问题，保证链表的head不会在删除操作中丢失。
快慢指针也是一个可以用于很多问题的技巧。所谓快慢指针中的快慢指的是指针向前移动的步长较大为快，步长较小为慢，常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1.快慢指针都从链表表头开始遍历，于是快指针到达链表末尾的时候慢指针刚好到达中间位置，于是可以得到中间元素的值。快慢指针在链表相关问题中主要由两个应用：
- 快速找出未知长度单链表的中间节点：设置两个指针
*fast、*slow都指向单链表的头结点，其中*fast的移动速度是*slow的2倍，当*fast指向末尾节点的时候，*slow正好就在中间了。 - 判断单链表是否有环：利用快慢指针的原理，同样设置两个指针
*fast、*slow都指向单链表的头结点，其中*fast的移动速度是*slow的2倍。如果*fast=NULL，说明该单链表以NULL结尾，不是循环链表；如果*fast=*slow，则快指针追上慢指针，说明该链表是循环链表。
TODO ///有相当一部分算法是根据基于数组的链表算法及实现的思路扩展的，掌握链表元素跳转关系，是否可求解此类问题呢？