LinkedList同时实现了List接口和Deque对口，也就是它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（stack）。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable //... }
当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（只是一个接口的名字）。
关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）更好的性能。
LinkedList 没有实现 RandomAccess 接口其底层基于链表结构，无法向 ArrayList 那样随机访问指定位置的元素。LinkedList 查找过程要稍麻烦一些，需要从链表头结点（或尾节点）向后(向前)查找，时间复杂度为 O(N)。这是因为 LinkedList 存储数据的内存地址是不连续的，所以不支持随机访问。
【1】类与数据结构
① 类继承
如下所示其继承自AbstractSequentialList，实现了List、Deque、Cloneable以及Serializable。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable //... }
实现了Cloneable以及Serializable标明其是可以克隆及序列化的。实现了List、Deque标明其是可以作为链表或者队列使用。那么AbstractSequentialList是什么呢、
从实现上，AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。
AbstractSequentialList 实现顺序访问是通过listIterator实现的，如下get方法。
public E get(int index) { try { return listIterator(index).next(); } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); } }
LinkedList实现了父类AbstractSequentialList 的抽象方法listIterator。
public abstract ListIterator<E> listIterator(int index);
② 数据结构
LinkedList 的数据结构示意图
核心属性如下所示，first和last是两个指针结点，分别表示第一个和最后一个结点。
// 元素个数 transient int size = 0; //头指针 transient Node<E> first; //尾指针 transient Node<E> last;
与ArrayList不同，这里没有数组。而是通过一个个Node关联起来。如下所示，Node中包含了next和prev，形成了双向链表。
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; } }
【2】核心方法
① 添加元素
默认添加到链表末尾。
public boolean add(E e) { linkLast(e); return true; }
linkLast方法会对first和last进行初始化，然后把元素追加到链表后面，更新size和modCount。
void linkLast(E e) { //第一次其是null final Node<E> l = last; // Node(Node<E> prev, E element, Node<E> next) //实例化新结点 prev-> l ,next->null final Node<E> newNode = new Node<>(l, e, null); //newNode作为last last = newNode; if (l == null) //newNode也作为first first = newNode; else l.next = newNode; //元素数量+1 size++; // 结构变化计数器+1 modCount++; }
② 指定位置添加元素
如果索引位置等于size，那么直接追加到链表末尾。这种情况比较高效，否则就需要遍历链表找到index位置，插入数据element。
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
checkPositionIndex同样是用来检测index是否合法的。
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; }
node(index)
用来检索目标位置的结点，返回结果是Node。如果index 小于size的一半，则从first开始正向检索，否则反向检索。
Node<E> node(int index) { // assert isElementIndex(index); //如果index 小于size的一半，则从first开始正向检索 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //否则从last开始反向检索 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
linkBefore(E e, Node succ)是将元素e插入到结点succe前面。
// Node<E> succ是索引位置的元素，E e是将要插入的元素 void linkBefore(E e, Node<E> succ) { // assert succ != null; //获取当前结点的头结点 final Node<E> pred = succ.prev; //将e实例化结点 Node(Node<E> prev, E element, Node<E> next) final Node<E> newNode = new Node<>(pred, e, succ); //当前结点prev指向新结点 succ.prev = newNode; if (pred == null)//判断是否为第一个元素 first = newNode; else //非第一个元素那么当前结点的前一个结点.next指向新结点，完成结点的插入 pred.next = newNode; //更新size modCount size++; modCount++; }
③ 获取指定位置元素
其首先判断index，然后基于node(index)方法实现查找。
public E get(int index) { checkElementIndex(index); return node(index).item; } //checkElementIndex用来判断index是否合法，[0,size) private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; }
④ 移除元素remove()
不指定的情况下，默认移除链表的第一个元素。
public E remove() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
⑤ unlinkFirst
unlinkFirst也就是把头结点从链表中隔断。
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; //获取结点f的下一个结点 final Node<E> next = f.next; //f.prev本身就是null，这里等于将first置为null，帮助垃圾回收 f.item = null; f.next = null; // help GC //把头结点指向f的下一个结点 first = next; if (next == null)//说明目前链表只有一个结点，那么first=last=null last = null; else next.prev = null;//否则把当前头结点的prev指向null //更新size modCount size--; modCount++; return element; }
⑥ 移除指定位置元素
checkElementIndex不再赘述，node(index)用来检索目标位置的结点。
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
这里实际上交给了unlink(Node x)来处理。
unlink(Node)
这里核心思想是让当前结点的前后结点形成双向绑定关系，然后将当前结点的item、next 、 prev置为null帮助GC。
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; //更新size modCount size--; modCount++; //返回移除的结点中的元素 return element; }
⑦ 移除指定对象
remove(Object o)的核心思想就是从first开始遍历，找到期望的结点然后交给unlink(x)完成结点移除操作。
public boolean remove(Object o) { // 当 o 为null时，使用 == 判断 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { // 当 o 不为null，使用equals判断 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
【3】实现Deque接口的几个方法
① poll
获取并移除链表的头结点。如下所示，LinkedList交给了unlinkFirst来实现。
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
pollFirst等价于poll，检索并移除头结点
public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
pollLast则是检索并移除尾结点
public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); }
② peek
这个方法与element()方法一样，都是获取链表的头结点(并不移除哦)。
// 返回头结点中的item，也就是element public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } public E element() { return getFirst(); }
peekFirst等价于peek，都是获取头结点的元素。
public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; }
peekLast获取尾结点的元素。
public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; }
③ pop
从该链表表示的堆栈中弹出一个元素。在LinkedList其实也就是移除并返回链表的头结点(中的element)与removeFirst()方法等价。
public E pop() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
④ push
对于LinkedList来说，其是向头结点插入数据。
public void push(E e) { addFirst(e); } public void addFirst(E e) { linkFirst(e); }
linkFirst
private void linkFirst(E e) { final Node<E> f = first; // Node(prev,item,next) final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null)//判断是否只有一个结点 last = newNode; else f.prev = newNode; //更新size modCount size++; modCount++; }
⑤ offer
向链表尾部追加结点，等价于offerLast方法。
public boolean offer(E e) { return add(e); }
对应的同样有offerFirst和offerLast，分别等价于linkFirst和linkLast。
//其实就是 linkFirst(e); public boolean offerFirst(E e) { addFirst(e); return true; } //其实就是linkLast public boolean offerLast(E e) { addLast(e); return true; }
