ArrayList已经在上一个博客文章中解析了，今天我们来看看List下又一个数据结构LinkedList。而它和ArrayList最大的不同在于ArrayList是基于数组实现，而LinkedList的底层是通过一个个的Node节点来实现的,所以它和ArrayList在很多特性上不一样。首先我们来看看他的数据结构：

    private static class Node<E> {
        E item; // 存储实际数据的属性
        Node<E> next; // 指向当前节点的下一个节点引用，没有则为null
        Node<E> prev; // 指向当前节点的上一个节点引用，没有则为null

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
复制代码

我们再来看看LinkedList类的声明有啥特点：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	// 容量
    transient int size = 0;

    // 链表的头结点
    transient Node<E> first;
	// 链表的尾节点
    transient Node<E> last;
    // 默认的无参构造
    public LinkedList() {
    }
	// 带参构造，ArrayList也有类似的构造
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
复制代码

首先我们可以看到LinkedList类的属性并不复杂，我们再来看看他的父类和接口

• AbstractSequentialList类和List接口，说明LinkedList具有集合快速查找相关操作
• Deque说明它具有队列的性质
• Cloneable说明提供了独有的克隆方法
• Serializable说明它支持序列化 但是我们注意到，它没有向ArrayList一样有RandomAccess接口，说明它不能支持快速随机定位查找。还有就是他的size、first、last都用了transient修饰，这个问题我们后续解答。我们来看看它常用的方法源码如何实现的吧！

- 添加元素add(E e)

    // 添加元素的方法调用的是连接最后方法
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
复制代码

我们看到，add()方法调用的是一个叫linkLast的方法，我们进去看看：

    // 添加到链尾
    void linkLast(E e) {
        // 先获取链表的尾结点，如果没有则为null
        final Node<E> l = last;
        // 将参数包装为Node节点，perv就是l，item就是我们的参数数据，next当然为null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将链表的last用用指向自己
        last = newNode;
        // 如果l==null，表名链表为空，此时该newNode既是头结点又是尾结点。否则将l的next节点指向newNode
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        // 容量+1
        size++;
        // 链表结构变化次数+1
        modCount++;
    }
复制代码

顾名思义，linkLast()方法是向链表尾部追加元素，这个过程还是比较简单。

- 插入头节点addFirst(E e)

    // 向链表头部插入节点
    public void addFirst(E e) {
        linkFirst(e);
    }
复制代码

我们可以看到插入头节点调用的是linkFirst()方法：

    // 链表头部插入节点
    private void linkFirst(E e) {
        // 先获取链表的头部节点f,链表为空的时候first和last都是默认值null
        final Node<E> f = first;
        // 将数据封装为Node,prev当时是null因为是头插,item就是我们的数据,next当然使我们开始获取的那个f
        final Node<E> newNode = new Node<>(null, e, f);
        // 将封装好的节点指向链表头部
        first = newNode;
        // 如果链表为空,f为null
        if (f == null)
            // 那么当前我们的node既是头结点又是尾结点,否则将最开始的f节点的prev指向newNode
            last = newNode;
        else
            f.prev = newNode;
        // 容量+1
        size++;
        // 链表结构变化次数+1
        modCount++;
    }
复制代码

- 添加尾结点addLast(E e)

    // 此方法和普通的add方法一致
    public void addLast(E e) {
        linkLast(e);
    }
复制代码

其实也是调用linkLast()方法，此方法在上文中已经有解析。

- 获取头/尾节点

    // 获取链表头部节点
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    // 获取链表尾部节点
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
复制代码

其实就是返回LinkedList的两个内部属性first和last。

- 移除头节点removeFirst()

    // 移除头结点并返回
    public E removeFirst() {
        // 先获取链表的头结点f
        final Node<E> f = first;
        // 集合为空，报错
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
复制代码

我们看到，底层调用的是一个叫unlinkFirst()的方法，我们继续看：

    // 移除链表头节点
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        // 首先获取头结点f的数据
        final E element = f.item;
        // 再获取出头结点f的下一个结点，因为头结点移除，next结点作为新的头结点
        final Node<E> next = f.next;
        // 将传入的头结点的数据和next置为null，f变为不可达对象，进行垃圾回收
        f.item = null;
        f.next = null; // help GC
        // 将next节点置为新的头结点
        first = next;
        // 如果next==null(链表就一个元素，所以next有可能为null)，此时链表移除头结点表明清空链表，头结点和尾结点都清空
        if (next == null)
            last = null;
        else
            // 如果next不为null，next原来的prev指向的是f，但是f被移除，next作为头结点，那他的prev属性当然为null
            next.prev = null;
        // 容量-1
        size--;
        // 链表结构变化次数-1
        modCount++;
        return element;
    }
复制代码

具体步骤就不用详说了吧，我把流程都写在注释里。

- 移除尾节点removeLast()

    // 移除尾结点并返回
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
复制代码

果然，底层调用的是叫一个unlinkLast()的方法：

    // 移除链表尾节点，和unlinkfirst操作一个概念
    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;
    }
复制代码

- 向指定位置插入元素set(int index, E element)

    // 向指定位置set数据(替换)
    public E set(int index, E element) {
        // 检查index和size的大小，防止越界
        checkElementIndex(index);
        // 首先调用node(int i)获取指定索引位置的node节点x
        Node<E> x = node(index);
        // 替换x中的item属性，然后返回原属性，完事儿
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
复制代码

这里出现了一个node(int index)方法，此方法用来查找指定位置上的元素节点：

    // 根据索引获取指定位置的元素
    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 这里并不是直接从头结点开始遍历，而是看index和size大小的偏离程度选择从头还是从尾遍历
        // 因为LinkedList没有和ArrayList一样实现去实现RandomAccess接口，所以LinkedList并不能直接靠index直接定位，而是遍历

        // 将size大小二分，然后判断index和链表中间索引值比较，如果index离头比较近就从头遍历，否则从尾遍历
        if (index < (size >> 1)) {
            // 从头结点开始遍历，首先取出链表的头结点
            Node<E> x = first;
            // 然后for循环遍历，直至到index位置，染回改节点node
            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和size大小的关系决定从头还是从尾遍历，因为LinkedList是一个双向链表，正反都可以遍历。
复制代码

- 向指定位置添加元素add(int index, E element)

    // 和set不一样，set是替换。add是在指定位置添加元素，原index位置的node会变为新node的next
    public void add(int index, E element) {
        // 检查是否越界
        checkPositionIndex(index);

        // 如果index==size表名直接在链尾追加完事儿
        if (index == size)
            linkLast(element);
        else
            // 否则调用linkBefore()方法
            linkBefore(element, node(index));
    }
复制代码

此时如果index==size其实就是在链尾添加，否则它是调用了linkBefore()方法：

    // 在指定元素位置添加元素
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // 获取原来该index位置的节点succ的prev节点
        final Node<E> pred = succ.prev;
        // 将新数据包装为node节点,因为新的node节点是要占据index位置,所以newNode的prev指向pred，
        // item就是数据本身，next当然指向原来index位置上的节点succ，现在succ已经变味next
        final Node<E> newNode = new Node<>(pred, e, succ);
        // newNode节点的属性已经赋值完毕，那么再将原来index位置的节点succ的prev引用改为newNode即可
        succ.prev = newNode;
        // 如果pred==null，代表index就是原来链表的头结点
        if (pred == null)
            // 那么将新节点赋予链表的头结点引用
            first = newNode;
        else
            // 刚刚修改了next节点的属性，现在再来修改prev节点的属性，将pred节点的next引用指向新节点即可。到此完事儿
            pred.next = newNode;
        // 容量+1
        size++;
        // 链表结构变化次数+1
        modCount++;
    }
复制代码

- 溢出指定位置的元素remove(int index)

    // 移除执行位置的节点
    public E remove(int index) {
        // 检查是否越界
        checkElementIndex(index);
        // 调用unlink(）方法移除
        return unlink(node(index));
    }
复制代码

我们来看看unlink()方法吧：

    // 移除指定的节点
    E unlink(Node<E> x) {
        // assert x != null;
        // 首先获取该节点的item数据,prev节点,next节点
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        // 如果prev==null,代表该节点是头结点，删除头结点很简单，直接将头结点的next节点置为头结点即可，然后将next的prev属性置为null
        if (prev == null) {
            first = next;
        } else {
            // 如果prev不为null，将prev的next节点改为next节点即可，这个情况是最简单的
            prev.next = next;
            // 然后将x的prev释放置为null
            x.prev = null;
        }

        // 如果next==null,代表该节点是尾结点，删除尾结点也很简单，将链表的last指向节点的上一个节点prev
        if (next == null) {
            last = prev;
        } else {
            // 如果next不为null，将next节点的prev属性引用prev节点即可
            next.prev = prev;
            // 然后释放此节点的next属性为null
            x.next = null;
        }

        // 最后将自己的数据置为null，到此x节点的三个属性均为null
        x.item = null;
        // 容量-1
        size--;
        // 链表结构变化次数+1
        modCount++;
        return element;
    }
复制代码

- 清空链表clear()

    // 清空链表
    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        // 循环进行遍历，依次将每个node节点的三个属性置为null，等待垃圾回收，直至链表尾部next=null
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        // 清空完链表后，将链表的头结点和尾结点的引用置为null
        first = last = null;
        // 将链表容量置为0
        size = 0;
        // 链表结构的变化次数+1
        modCount++;
    }
复制代码

- 将链表转换为数组输出toArray()

    // 和ArrayList不同，ArrayList是依靠数组的复制。LinkedList是遍历链表然后放入数组中，过程很简单。
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
复制代码

- LinkedList序列化

最后来说说为什么linkedList的size、first、last要用transient修饰，ArrayList之所以用transient修饰element数组是因为内存空间问题，这个在ArrayList博客里已经说了。LinkedList中之所以这样做是为了避免内存地址不一致的问题，linkedList是由多个Node节点组成，每个Node节点都持有前后两个Node节点的引用，如果支持序列化以后，再反序列化回来，Node节点的内存会不一致。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        // 只是将node节点里的值序列化
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }


    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }
复制代码

最后总结一下LinkedList的特点：

• 内存不连续，单个节点占用体积相比于ArrayList略大，但ArrayList的element数组后段有空闲
• 大数据量情况下检索速度不如数组和ArrayList
• 由于特殊的数据结构导致它的添加或删除元素的效率相对较高
• 和ArrayList一样，是线程不安全的类