经常为了面试要记住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（）方法终于是我们熟悉的背影了，主要逻辑就在这里了。