一、简介

面试时候的一大经典问题：你知道ArrayList和LinkedList的区别吗？（不，我不知道）。基本上看过面经的都知道，ArrayList是数组结构，LinkedList是链表结构。但如果这时候再问，它们的源码有读过吗？凉凉夜色为你思念成河～
LinkedList存储数据确实是链表结构，其数据存储字段为：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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;
....
}

first即为链表的头节点，last的为尾节点。Node中，有记录前驱节点和后继节点,以及数据item:

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存储数据使用的是双向链表数据结构。在接下来的部分，我们再来看一下LinkedList的查询、增加和删除方法，即get、add、remove方法。

二、get方法

get方法传入的是index，即第几个元素（下标从0开始）。虽然这是链表结构吧，但get方法的参数与ArrayList类似。

/**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

检查一下index是否超过了size，然后返回node(index)的item。node方法如下：

/**
     * Returns the (non-null) Node at the specified element 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;
        }
    }

可以看到，如果index小于size>>1，即要查找的元素在链表前半部分，则从first节点往后查找，否则从last节点往前查找。

三、 add方法

add方法就主要看add(index,element)这个方法，毕竟这也包括了add(element)的情况，即添加在链表末尾的情况。

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

1.检查一下index是否合法
2.如果index==size即要插入到链表末尾

    /**
     * Links e as last element.
     */
    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++;
    }

很简单了，新建一个前驱节点为l，element为e，后继节点为null的节点，并且修改原尾指针的后继节点，再将尾指针指向插入的节点。
3.如果index < size，插入到链表中间，调用linkBefore(element, node(index))。

    /**
     * Inserts element e before non-null Node succ.
     */
    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++;
    }

传入的参数为要插入的元素e和后继节点succ。插入逻辑也挺简单，先得到后继节点的前驱节点pred，创建前驱节点为pred，后继节点为succ的新节点，再修改前驱的后继和后继的前驱即可。

四、remove方法

移除的话主要看remove(int index)和remove(Object o)方法。
移除对象的时候，就是在链表中找到o，然后调用unlink方法：

    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;
    }

remove(index)也是类似，找到对象后调用unlink方法：

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

接下来看看殊途同归的unlink方法：

/**
     * 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 {
            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;
    }

其实就是先看看要删除的节点的前驱和后继，修改前驱的next为指针为后继，后继的prev指针为前驱，碰到头节点或尾节点的情况分类讨论即可。

五、与ArrayList对比

1.ArrayList中存在扩容，在扩容时还有拷贝操作，而LinkedList没有扩容。
2.ArrayList中增加删除元素时，都得调用System.arraycopy，即拷贝操作，而LinkedList主要得先找到插入/删除的节点。不清楚System.arraycopy的源码和性能，笔者也不知道怎么比较，反正平均复杂度应该都是O(n)的。LinkedList要插入/删除的元素在链表中间而链表又长时，应该是比较慢的。
3.ArrayList的查找是O(1)的，LinkedList的查找是O(n)的。
(ps:LinkedList的增删查比ArrayList好懂多了，面试的时候如果要说源码可以说LinkedList)