[Java]-LinkedList源码分析
LinkedList源码分析
概述
源码中对LinkedList这个类给出了详细了概述，大概意思为
List接口跟Deque接口的双向链表实现，实现了所有可选的list操作，而且允许所有的类型存储，包括null
所有操作的执行都是在双向链表的结构上。通过索引进入list的操作会通过从链表头或者链表尾往另一端遍历来找到指定索引的位置然后进行操作，至于从头还是尾开始遍历，就要看指定的索引位置离头更近还是离尾更近
LinkedList这个实现类并不是同步的，如果有多线程并发地访问了一个LinkedList，且至少有一个线程修改了list的就饿狗，那它就必须在外部进行同步(添加或删除元素才属于对list结构的修改，不包括对某个元素的值进行修改)。这通常是通过在能自然封装list的某个对象上进行同步来实现的
如果没有这样的对象，那么list应该使用Collections.synchronizedList方法进行包装：
List list = Collections.synchronizedList(new LinkedList(…));
该类的迭代器iterator及listIterator是支持fast-fail机制的
在下面的具体方法分析中，可以看到有的方法实际上是在调用类中其它的方法，如offer方法实际上是在调用add方法，offerFirst方法实际上是在调用addFirst方法，这是由于LinkedList既实现了List接口，也实现了Deque，所以有一部分方法是针对List设计的，一部分是针对Deque设计的，而这两部分方法中，又有一些方法是相同作用的，所以就直接调用了
链表节点Node
链表的每个节点的类型采用的是内部类Node
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; }}主要成员变量
transient int size = 0;/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */transient Node<E> first;/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */transient Node<E> last;size表示当前LinkedList中存储的元素个数
first以及last分别指向双向链表的头节点跟尾结点，而且存在这样的恒成立关系：要么first跟last都为null，要么first节点有存值且前驱节点为null，以及last节点有存值且其后续节点为null，分别对应LinkedList为空表以及有存元素两种情况
构造函数
public LinkedList() {}//根据传入的Collection集合来创建public LinkedList(Collection<? extends E> c) { this(); addAll(c);}私有的操作
LinkedList设置了几个私有的修改链表结构的方法，其它对用户提供的操作方法都是直接或间接地调用这些操作，在这些操作中，要注意的是，由于是双向链表，每对一个元素进行增或删操作时，要注意其与前驱节点以及后继节点的联系(引用关系)，特别是操作前链表是不是空表，操作后链表会不会是空表：
//在链表头新增一个元素private void linkFirst(E e) { final Node<E> f = first; //新增的节点就会成为新的头节点 final Node<E> newNode = new Node<>(null, e, f); first = newNode; //f为null说明原来是个空表，现在有了第一个节点，last也要指向它 if (f == null) last = newNode; else f.prev = newNode; size++; modCount++;}//在链表尾新增一个元素void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++;}//在链表中指定节点的前面插入一个新元素，该节点必须存值链表中void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++;}//删除链表头节点，所传参数必须为链表的头节点private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; //将相关的引用置为null才可以让GC进行内存回收 f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element;}//删除链表尾结点private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element;}//删除链表中指定的节点，且指定的节点必须不为nullE 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++; return element;}添加元素
addFirst
public void addFirst(E e) { linkFirst(e);}在链表头部添加元素，直接调用linkFirst方法完成
addLast
public void addLast(E e) { linkLast(e);}在链表尾部添加元素，直接调用linkLast方法完成
add
public boolean add(E e) { linkLast(e); return true;}上面的add方法是在在链表尾部添加元素，就是说它的作用跟addLast是一样的。除此之外还有一个在指定索引位置添加元素的重载方法:
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index));}要在指定索引对应的地方添加一个元素，首先要判断这个索引所在的位置是不是允许元素存放。由于当前链表中共有size个元素，那么索引就是[0,size - 1]，除此之外可以在链表尾添加一个元素，所以索引值等于size也是可以的，接下来进入checkPositionIndex方法看它的判断条件是不是这样：
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}继续查看isPositionIndex：
private boolean isPositionIndex(int index) { returnindex >= 0 && index <= size;}可以看到其判断条件与前面认为的一致。判断索引合法就回到add方法中，当index值等于size时，直接调用linkLast方法将元素添加到链表尾；否则调用linkBefore方法将元素添加到原来index对应的节点的前面
以下操作就是面向Deque设置的操作
offer
public boolean offer(E e) { return add(e);}offer方法实际上是在调用add方法，即在链表尾添加元素
offerFirst
public boolean offerFirst(E e) { addFirst(e); return true;}offerFirst方法实际上是调用addFirst方法，即在链表头添加元素
offerLast
public boolean offerLast(E e) { addLast(e); return true;}offerLast实际上是调用addLast方法，即在链表尾添加元素
push
public void push(E e) { addFirst(e);}push方法实际上是调用addFirst方法
删除元素
removeFirst
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f);}删除链表中第一个元素，即删除链表中第一个节点
removeLast
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l);}删除链表中最后一个元素，即删除链表中最后一个节点
以下操作就是面向Deque设置的操作
remove
//从头结点向后遍历，删除第一个所存元素值为o的节点public boolean remove(Object o) {//可能有节点所存元素值就为null if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { //经过测试，像这里这样调用equals并不是根据Object类中定义的一样根据地址是否一样来判断 //而是根据o跟x.item是什么类型(即该LinkedList的泛型)来使用其类中自己重写的equals方法，如String类 //当然，如果泛型就是Object，那还是会按照Object类中定义的一样使用内存地址是否一样来做判断 if (o.equals(x.item)) { unlink(x); return true; } } } return false;}除此之外还有一个删除指定索引位置节点的重载方法：
public E remove(int index) { checkElementIndex(index); return unlink(node(index));}poll
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f);}删除链表头节点，同时返回其所存元素的值
pop
public E pop() { return removeFirst();}pop方法实际上是调用removeFirst方法，所以在头节点为null的时候会抛出异常，这也是跟poll方法的区别所在，如果头节点为null，poll方法会返回null而不会抛出异常
获取元素值
getFirst
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item;}获取链表中第一个元素的值，即头节点所存元素的值，若不存在头节点会抛出异常
getLast
public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item;}获取链表中最一个元素的值，即尾节点所存元素的值，若不存在尾节点会抛出异常
get
get方法用于返回指定索引位置上链表节点的元素值
public E get(int index) { checkElementIndex(index); return node(index).item;}查找前要先判断索引对当前链表来说是否合法，合法的条件应该是0 <= index < size
借助checkElementIndex方法
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}继续看isElementIndex方法
private boolean isElementIndex(int index) { return index >= 0 && index < size;}发现判断条件确实是0 <= index < size。如果索引合法，就调用node(int index)方法获取这个索引对应的节点，最后获取节点上的元素值
Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}在概述的时候说过，“通过索引进入list的操作会通过从链表头或者链表尾往另一端遍历来找到指定索引的位置然后进行操作，至于从头还是尾开始遍历，就要看指定的索引位置离头更近还是离尾更近”，所以根据index是否小于size的二分之一，判断index所对应的节点离头节点更近还是离尾结点更近。如果index小于size的二分之一，说明index所对应的节点离头节点更近，所以从头节点开始往尾结点遍历查找第index个节点
在头尾结点中选取更近的节点开始遍历是为了尽可能地减少查找节点所花费的时间，因为LinkedList是链表结构，只要是查找操作都避免不了要进行O(n)的遍历链表操作，既然避免不了，那就只能尽可能地减少
peek
public E peek() { finalNode<E> f = first; return (f == null) ? null : f.item;}返回链表头节点所存元素值，若头节点为null则返回null
总结
LinkedList既可以在链表头进行增删，也可以在链表尾进行增删，所以可以使用它来作为队列或者栈进行使用
ArrayList的增删一定比LinkedList慢吗
- 如果增删是在末尾进行操作，ArrayList可能不需要移动和复制数组，这时增删的速度是会比LinkedList快的
- 如果增删是在列表之间进行，由于LinkedList的时间花费主要是在遍历上，而ArrayList的时间花费主要是在删除元素后移动和复制数组上(即调用native方法System.arraycopy)，LinkedList的遍历速度是要慢于ArrayList的复制速度的，如果数据量是百万级，还是ArrayList要快