LinkedList源码分析
经常为了面试要记住LinkedList和ArrayList的区别，比如存取速度的比较。如果不了解他们的实现方式，不看源码，记住了也是死记硬背，容易忘记，没有太大的意义。这里讲的是LinkedList，暂时不讲ArrayList，从源码了解LinkedList的实现方式以及操作方法的实现，才能更全面了解LinkedList。
LinkedList是基于双向链表的数据结构实现的，所以必须要知道掌握双向链表这种数据结构，如果对双向链表不了解的话得先去学一下，比较容易理解的一种数据结构。学习了双向链表看LinkedList的源码会更轻松一些，从 源码了解LinkedList的性质，才能更加了解LinkedList，知道在什么场合更加适合使用LinkedList。别啰嗦了，看源码：
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Queue<E>, Cloneable, Serializable ｛
....
｝
LinkedList可以指定一个泛型（一般我们都会这么做），具有多个实现，源码大部分逻辑都是在实现这些接口的方法，从它们的名字我们可以看出除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。
来看构造函数
//记录LinkedList的大小，即LinkedList有多少个节点（或者说元素）
transient int size = 0;
//一个空的节点
transient Link<E> voidLink;
/**
* Constructs a new instance of {@code LinkedList} that holds all of the
* elements contained in the specified {@code collection}. The order of the
* elements in this new {@code LinkedList} will be determined by the
* iteration order of {@code collection}.
*
* @param collection
* the collection of elements to add.
*/
//这个带参数的构造函数的this()方法是调用下面的那个构造函数，之后将参数collection跟voidLink（一个空节点，在第二个构造函数里创建出来的）
//链接起来，addAll(collection)后面讲解
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
/**
* Constructs a new empty instance of {@code LinkedList}（创建一个空的实例）
*/
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
//创建节点的静态内部类
private static final class Link<ET> {
//ET其实就是E这个泛型，从上面的构造函数可以看出，这个字段就是元素
ET data;
//这两个字段分别是当前节点的头和尾，分布存储的是前一个节点和后一个节点，双向链表数据结构的每个节点都是有这三个东西组成的
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
从第二个构造函数我们知道new出一个LinkedList的时候，这个实例里面只有一个空的节点voidLink ，一般我们会有个add(int location, E object)函数添加元素到指定位置，所以接着看add(E object)函数添加元素到最后一个节点的后面，addAll(int location, Collection<? extends E> collection)函数添加Collection到指定位置，addAll(Collection<? extends E> collection)函数添加Collection到最后一个节点的后面。addFirst(E object)添加元素到第一个节点的前面，addLast(E object)添加元素到最后一个节点后面。这些是所有添加元素的方法。分别看下他们的逻辑，都是相似的。理解了其中一个其他都好理解。
/**
* Inserts the specified object into this {@code LinkedList} at the
* specified location. The object is inserted before any previous element at
* the specified location. If the location is equal to the size of this
* {@code LinkedList}, the object is added at the end.
*上面的意思就是将指定的object 插入到指定的位置，之前位置的object 以及它后面的object 的位置的都会加1
*注意最后一句话的意思是如果这个LinkedList的size等于location ，那么意思就是插入到最后一个位置。不允许location >size,location<0
*
* @param location
* the index at which to insert.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location > size()}
*/
@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
方法注释可以了解到大概，分析代码才能更细节的了解，可以看到location 必须大于等于0且小于等于sise，否则会抛出异常，满足条件后需要创建一个节点引用，先指向voidLink这个空节点，因为我们需要借助voidLink和size才能找到一个目标节点，该目标节点起着关键的作用，先看if和else语句，判断插入位置区域链表的哪一边，如果是左边的话则进入if条件的for循环从第一个位置开始找目标节点，首先我们必须知道voidLink.next永远的是当前的第一个节点，等看完了所有添加元素的函数逻辑的时候就明白了。如果进入else条件，逻辑也是一样的，只是从尾部开始查找目标节点。找到目标节点之后就很简单了，把目标节点的前一个节点的next指向newLink （新插入节点），目标节点的previous 指向newLink ，这样就完成了拼接，目标节点的位置被新节点占据着，着目标节点以及后面的节点的位置都各自加1，此时我们还要加size+1，modCount+1只是一个统计修改的次数。逻辑还是比较简单的，后面的几个添加元素的方法都是大同小异的。
add(E object)在尾部添加节点，更加简单目标节点哦度不用找，因为voidLink.previous就是最后一个节点，跟voidLink.next永远的是当前的第一个节点永远是第一个节点相呼应：
/**
* Adds the specified object at the end of this {@code LinkedList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
其他几个添加元素的函数都是按照这种套路执行的，不必每一个都进行分析了，但每个人都有必要去看一遍的。
与添加对应的方法就是删除了，remove(int location)，removeFirst()，removeLast()，方法名可以看出什么意思了，删除的套路前半部分也是一样的，目标节点，然后根据目标节点找到他前后的节点，让前一个节点的next指向后一个节点，后一个节点的previous指向前一个节点。还有一个remove(Object object)方法收回复杂一些，后面单独讲，先看remove(int location)（removeFirst()，removeLast()与removeFirst()，removeLast()套路相似）
/**
* Removes the object at the specified location from this {@code LinkedList}.
*
* @param location
* the index of the object to remove
* @return the removed object
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}
*/
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
remove(Object object)源码
@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
private boolean removeFirstOccurrenceImpl(Object o) {
Iterator<E> iter = new LinkIterator<E>(this, 0);
return removeOneOccurrence(o, iter);
}
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
while (iter.hasNext()) {
E element = iter.next();
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}
从源码看到的调用到最后removeOneOccurrence(Object o, Iterator<E> iter)函数的iter.remove()防止执行了移除工作，这个方法里面调用了LinkIterator的hasNext()、next()、remove()三个方法，进去看他们的源码看下到底做了什么工作
public boolean hasNext() {
return link.next != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
LinkedList.Link<ET> next = link.next;
if (next != list.voidLink) {
lastLink = link = next;
pos++;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
Link<ET> next = lastLink.next;
Link<ET> previous = lastLink.previous;
next.previous = previous;
previous.next = next;
if (lastLink == link) {
pos--;
}
link = previous;
lastLink = null;
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
hasNext()判断当前节点（就是voidLink，从构造函数看出来的）的下一个节点是否为空，next()返回下一个节点的data，remove（）方法终于是我们熟悉的背影了，主要逻辑就在这里了。
