上一篇Java Collection之ArrayList源码分析我们对ArrayList做了一个分析。我们知道了它内部是基于数组来实现的，也从源码分析出它的增、删都涉及到数组的copy，都会对数据位置进行移动，造成增、删缓慢的问题。那么LinkedList就会解决这一问题。
经常面试会问到这两者之间的优缺点和不同之处。我们大多数人可能也会答得出来，但是在一多问可能就露馅了。所以我们要深入了解，这样才能不被问住，平时开发中也更能灵活运用。
LinkedList内部结构是一个双向链表，对于链表我们知道每个元素有一个数据域和指针域，而指针域是指向下一个元素的地址。所以双向链表的意思就是把单链表的指针域进行扩充，让它也能指向前一个元素。
我们还是按以往的惯例，从我们平时的使用习惯开始分析。平时的使用当然是先调用构造方法，一般如下：

private LinkedList<String> linkedList=new LinkedList<>();

那么我们开始进入构造方法的源码：

 /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

 public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

额。。。这有点尴尬了，两个构造方法，第一个空参，第二个还看不懂。好吧，不管了，我现在要用它，我们还是从增、删、改、查来找突破口吧。

增

首先我们看添加方法：

    /**
     * 将元素添加到list最后,就像addLast方法
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 在该列表中的指定位置插入指定元素。
     * 移动当前位置（如果有的话）右边的后续元素（向索引添加一个元素）。
     */
    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    /**
     *list最前插入
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     *list末尾插入
     */
    public void addLast(E e) {
        linkLast(e);
    }

我们看第一个add方法，调用了linkLast(e);方法。

/**
     * Links e as last element.将e链入最后的位置
     */
    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++;
    }

这里我又看不懂了，这个Node是啥？到这里我们停下，先看看这个Node是什么鬼。

transient Node<E> first;//Pointer to first node.指向第一个节点的指针
transient Node<E> last;//Pointer to last 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;
        }
    }

我们看到它是一个静态内部类，会先加载。同时结合我们LinkedList源码官方的介绍其实现方式是双向链表。我们知道这个Node就是一个节点。有关链表这里做一个简单介绍：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
更多关于链表的知识，请自行百度。
现在我们就能很清晰的知道，Node在LinkedList里就是作为了链表的节点。里面包含了当前节点的值，也包含了前一个和后一个节点，这就实现了双向链表。现在我们回到linkLast(E e)方法

        //尾节点，我们这里第一次调用 l=last=null;
        final Node<E> l = last;
        //新的节点，包含了上一个节点 l，当前节点e，和下一个节点null
        final Node<E> newNode = new Node<>(l, e, null);
        //把新的节点作为尾节点，也是把新的节点放在链表的尾部
        last = newNode;
        if (l == null)
            //第一次时，新的节点也是首节点
            first = newNode;
        else
            //如果已经有了很多元素 ，前一个元素已经作为了尾部元素，将新节点赋值给前一个元素的next。
            //也就是前一个元素的下一个指向的是这个新节点
            l.next = newNode;
        //list存储数量依次+1
        size++;
        //与上一篇ArrayList中提到过的一样，这里我们不去关心
        modCount++;

下面我们看看添加两个元素各阶段的，我们使用debug方式来直观的体验一下，当调用linkedList.add("new one");

第一次插值.jpg
当我们调用linkedList.add("new two");插入第二个值：
第二次插值.jpg

我们可以直观的看到，当插入第一个值时，add方法会构建一个内部维护的Node，item是当前真正的存放的值，prev是指向了前一个为空的Node对象，next指向了下一个添加进来的值构建的Node对象，这个对象也为空。当第二次插值，当前list的最后一个元素就是第一次插入的值，这时候通过linkLast就能建立两个Node之间的关系。

---

接下来我们看看第二个插入的方法add(int index, E element)其中checkPositionIndex(index);是为了index在正常范围内。接下来如果要插入的位置刚好等于现在的元素个数index==size那么我们就调用linkLast方法将数据添加到末尾，因为这个方法会新建一个节点并作为尾节点。如果是要在中间插入数据，就调用linkBefore(element, node(index));方法。这里有一个新的方法node(index)我们先看它

Node<E> node(int index) {
        // assert isElementIndex(index);
        //size>>1可以理解为size/2
        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;
        }
    }

通过分析该方法，查找第index个节点，我们将列表一分为二，如果在前半段就从第一个开始依次查找下一个元素，如果是后半段就从最后依次查找前一个元素，直到满足条件为止。如果这样难以理解，我们笨的人就用笨的方法吧，举个实际的例子。因为现在我们的场景是在一个列表的中间某个位置插入值。我们看下面的图示，

node(int index).png 所以这个方法的作用就是通过index找到要插入的位置节点。然后我们再回过头去看linkBefore(E e, Node<E> succ)e是我们要插入的值，Node是我们找到的第index个节点，通过这个节点就能调整前后的指向关系。里面的操作和linkLast差不多，唯一不同的是，这里插入值是将值插入到index这个节点之前的。这一点其实通过方法名就能看出来。
还有两个方法，addFirst(E e) addLast(E e)分别是将元素插入列表头，和列表尾。其实现方法和add类似，这里就不在具体分析。

删

接下来我们在看删除方法，这里可能使用广泛的就这四个，其他方法的原理也是大同小异。

//该方法移除列表中第一次出现的该元素，如果元素不存在，将不会发生任何改变
public boolean remove(Object o) {
        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) {
                if (o.equals(x.item)) {
                  //如果元素的值相等，就执行断掉链接关系
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }
//删除第一个元素
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
//删除最后一个元素
public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

我们先看第一个方法，先遍历每个元素，也就是节点，找到和该值相等的然后执行删除操作。

/**
     * Unlinks non-null node x.
     */
    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 {
            //前一个节点的next指向当前节点的next
            prev.next = next;
            //然后将当前节点的prev置空
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            //当前节点的下一个节点的prev，指向当前节点的prev
            next.prev = prev;
            //然后将当前节点的next 置空
            x.next = null;
        }
        //将当前节点的值置空
        x.item = null;
        size--;
        modCount++;
        return element;
    }

通过以上代码的分析，结合注释我们很容易理解remove(Object o)方法实际上就是将该节点Node的前一个节点和后一个节点建立链接关系，任何将该节点所有属性置空进行回收。这样就达到了删除的目的。
第二个根据remove(int index)方法，（这里要注意的是，其实这个index不是真正的位置信息，不想数组是一段连续的内存，这里只是它的添加顺序。）是先通过我们前面分析过的通过node()方法找到第index个节点，然后调用unLink进行删除。
第三个removeFirst第四个removeLast方法就更简单了，因为我们定义的全局变量first last就是我们需要删除的节点，这样就直接调整相应的prev和next然后置空就行了，这里不再过多解释。

---

改

改动的方法和ArrayList一样也只有一个，通过index查找到节点，然后对其值进行从新赋值即可。

public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

查

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

很简单的通过index查找到节点，然后获取item就是我们要的值。
至于getFirst和getLast就更简单了，成员变量直接获取。

---

总结

到这里我们有关于LinkedList的分析就结束了。通过这样的学习，现在我们就能自己说出来他们各自的优缺点了，再也不用死记硬背了。我们来具体看看他们的优缺点，我们还是按照我们的流程来，从构造方法说起，再到数据的操作。

对比项目	ArrayList	LinkedList
实现方式	数组	双向链表
构造方法	初始化空数组	---
增	始终在末尾，有index参数的涉及到数组的移动copy	首尾方便，中间涉及大量折半遍历
删	会有大量数组copy	首尾方便，中间涉及大量折半遍历
改	很方便只需通过下标从新赋值	首尾方便，中间涉及大量折半遍历
查	很方便只需通过下标获取	首尾方便，中间涉及大量折半遍历