在使用List的 时候经常是ArrayList和LinkedList他们两个各有千秋，根据自己的业务使用情况来使用，现在咱们看看LinkedList的底层是如何实现各种操作的。 首先咱先看看他的继承和实现类：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable,java.io.Serializable

他继承了AbstractSequentialList，AbstractSequentialList又继承了 AbstractList，而ArrayList是直接继承了AbstractList，看AbstractSequentialList的源码发现他内部实现的方法是直接操作public abstract ListIterator<E> listIterator(int index);是直接操作ListIterator，关于他的内容咱们之后再看。

 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;

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

LinkedList内定义的参数都是transient 类型的。他的first、last都是Node类型的，可以看出LinkedList底层是根据Node来进行操作的（LinkedList是个链，各个节点就是链上的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;
    }
}

Node类包含三个参数，item本Node的参数，next指向下一个Node节点，prev指向上一个Node节点，这个和C语言的指针操作相类似了。LinkedList的所有操作最后都是操作特定的Node，在添加和删除相关操作就比ArrayList的效率快，查询的操作就次之了。 先看LinkedList的add相关的操作：

public boolean add(E e) {
    linkLast(e);
    return true;
}

很简单直接调用了一个linkLast（E e）进行添加：

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

在这里面向原有的List里面添加新的e，从中先创建Node因为他是从List的尾部添加所以他的next是Null，本身记载的LinkedList的尾部last和头部next，将最新的数据e添加到以前的last数据后面。进行一个Node的添加。 在指定位置上添加新的数据：

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

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

在制定位置上添加首先判断这个index是否越界，然后进行添加，如果是添加尾部就使用的是之前介绍的linkLast方法，如果不是将会使用linkBefor的方法进行插入。 判断index：

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

进行位置插入：

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

知道Node的各个意思之后，代码就非常简单易懂了。

addAll方法最终使用的是一种方法：

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

在全量添加的两种方法中，最后还是调用的是addAll(index,Object)方法，所有指定位置添加都会判断index是否越界的问题，然后把将要插入的点的前后节点指向succ、pred之后循环把要插入的数组写入到pred的后面，最后再指定一下succ和pred的头尾就完成了。 LinkedList的add比ArrayList多两个：分别是addFirst和addLast，一个是从链表头部添加，一个是从链表尾部添加，从尾部添加展示过了，现在看一下从头部添加的代码：

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

offer(e),offerFirst(e),offerLast(e)这三个也是添加数据：

public boolean offer(E e) {
    return add(e);
}
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

add相关的代码就写完了，之后将是其他的代码。