LinkedList 源码分析（jdk1.8）

类继承关系：

(*=>：接口实现)

java.lang.Object 
  –java.util.AbstractCollection =>Collection 
    –java.util.AbstractList =>List 
      –java.util.AbstractSequentialList 
        –java.util.LinkedList =>List, Deque,Serializable(), Cloneable 
LinkedList

       LinkedList采用的是双向链表结构，对比ArrayList，在随机访问上效率不如ArrayList（ArrayList是基于数组，通过定位获取元素，LinkedList需要Node()方法来循环查找，下面将详细解释），而在添加删除操作用效率高于ArrayList（ArrayList需要移动数据，除非你只插在最后面），在顺序访问上LinkedList也很高效。

LinkedList数据结构

在JDK1.7之前LinkedList还是双向循环链表，1.7之后为更新为双向链表，感兴趣的可以去看看。

源码分析：

1.类继承实现

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    //方法....
}

实现了Deque 双端队列接口。Cloneable，Serializabl，可克隆，可序列化（在ArrayList篇已提到http://blog.csdn.net/qq_23830637/article/details/78979628）。

2.成员变量

/**
 * linkedlist的大小即元素个数
 */
transient int size = 0;

/**
 * linkedList的首节点
 */
transient Node<E> first;

/**
 * linkedList的尾节点
 */
transient Node<E> last;

3.Node节点

/**
 * Node节点是LinkedList中的内部类
 */
private static class Node<E> {
    E item; //向linkedList中存储的元素
    Node<E> next; //当前元素的下一个节点
    Node<E> prev; //当前元素的上一个节点

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

4.主要方法

构造方法

LinkedList提供了2种构造方法

1.

public LinkedList() {
}
2.

/**
 * 创建一个和传入集合元素一样的LinkedList
 */
public LinkedList(Collection<? extends E> c) {
    //调用自身无参构造方法
    this();
    //执行添加集合所有元素的方法，allAll()方法下面会介绍
    addAll(c);
}

获取元素

/**
 *
 */
public E get(int index) {
    //检查索引
    checkElementIndex(index);
    //返回指定元素索引中的节点。
    return node(index).item;
}

/**
 * 检查是否越界
 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 告知参数是否为现有元素的索引
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

/**
 * 返回指定元素索引中的（非空）节点。
 * 二分查找 降低了时间复杂度
 */
Node<E> node(int index) {
    //当索引小于linkedList长度的一半时，从头查找
    if (index < (size >> 1)) {//右移一位 相当于/2
        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;
    }
}

添加元素

添加元素至尾部

/**
 * 将指定元素添加到链表尾部
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 元素E作为最后一个元素。
 */
void linkLast(E e) {
    //获取当前链表尾节点
    final Node<E> l = last;
    //创建一个节点，item为当前添加元素，前节点prev为last(当前尾节点，后节点next为null)
    final Node<E> newNode = new Node<>(l, e, null);
    //修改last（链表尾节点）为当前新添加创建的节点newNode
    last = newNode;
    //如果l为空，即当前链表尾节点为null，当前列表为空链表
    if (l == null)
        first = newNode;//链表首节点修改为newNode
    else//不是空链表
        l.next = newNode;//原尾节点的next指向新添加的节点
    size++;//长度++
    modCount++;//操作次数++
}

链表添加元素至尾部时结构图： 
（当列表不为空链表时） 

添加元素至头部

/**
 * 在列表的开头插入指定的元素。
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 元素E作为第一元素。
 */
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++;
}

与上面的方法相反，添加至头部，就不做解释了。 
除此之外还有从双端队列Deque中实现的添加方法push()（入栈，首部添加）,offer()（尾部添加）,offerFirst()（头部添加）,offerLast()（尾部添加）原理与上面一样。

指定位置添加元素

/**
 * 在列表中指定的位置插入指定的元素
 */
public void add(int index, E element) {
    checkPositionIndex(index);//检查索引是否正确

    if (index == size) //指定位置与linkedList的size相等时，直接添加到尾部即可
        linkLast(element);
    else
        //在指定节点位置前插入元素
        linkBefore(element, node(index));
}

/**
 * 在指定节点位置前插入元素
 */
void linkBefore(E e, Node<E> succ) {
    //获取指定节点的前一节点
    final Node<E> pred = succ.prev;
    //创建新节点的prev指向pred（指定节点的前一节点），尾部next指向succ（指定节点）
    final Node<E> newNode = new Node<>(pred, e, succ);
    //指定节点的prev指向修改为newNode
    succ.prev = newNode;
    //如果pred（指定节点的前一节点）为null，说明succ（指定节点）为链表的首节点
    if (pred == null)
        first = newNode;//修改首节点为newNode
    else//succ（指定节点）不是链表的首节点
        pred.next = newNode;//pred（指定节点的前一节点）的next指向修改为newNode
    size++;
    modCount++;
}

批量添加元素

/**
 * 添加指定集合的所有元素
 */
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;
    //如果新添加的数组长度为0，就是个空的 直接返回false
    if (numNew == 0)
        return false;

    //pred：要插入的当前元素的前一个节点（要插入元素的prev）
    //succ：要插入的当前元素的后一个节点（要插入元素的next）
    Node<E> pred, succ;
    //添加位置与size相等时，添加至尾部
    if (index == size) {
        succ = null;//后节点为null
        pred = last;//前节点为当前链表的尾节点
    } else {//在中间添加时
        succ = node(index);//后节点为插入位置的节点
        pred = succ.prev;//前节点为后节点（位置的节点）的prev
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        //如果pred为空
        if (pred == null)
            //新添加的节点为首节点
            first = newNode;
        else
            pred.next = newNode;//pred的next指向修改为newNode
        pred = newNode;//修改为newNode
    }

    //如果succ为空
    if (succ == null) {
        //说明从尾部添加节点，链表的last（尾节点）修改为pred（新添加的节点）
        last = pred;
    } else {
        //pred的next指向修改为succ
        pred.next = succ;
        //succ的prev指向修改为pred
        succ.prev = pred;
    }

    size += numNew;//size增加新添加的数量
    modCount++;//操作次数++
    return true;
}

移除元素

/**
 * 在列表中指定位置删除元素
 * 后续元素左（下标减1）
 * 返回从列表中移除的元素
 */
public E remove(int index) {
    //检查是否越界
    checkElementIndex(index);
    //删除节点并返回该节点
    return unlink(node(index));
}

/**
 * 删除节点并返回该节点
 */
E unlink(Node<E> x) {
    final E element = x.item;//获得当前节点
    final Node<E> next = x.next;//当前节点的下一个节点
    final Node<E> prev = x.prev;//当前节点的上一个节点

    //当上一个节点为null，说明当前结点为首节点，需要删除的节点为首节点
    if (prev == null) {
        //将首节点修改为当前结点的下一个节点
        first = next;
    } else {//当前结点不是首节点
        //当前节点的上一个节点的next指向 由当前节点 修改为 当前节点的下一个节点
        prev.next = next;
        x.prev = null;//置空 垃圾回收
    }

    //当下一个节点为null，说明当前结点为尾节点，需要删除的节点为尾节点
    if (next == null) {
        //将首节点修改为当前结点的上一个节点
        last = prev;
    } else {//当前结点不是尾节点
        //当前节点的下一个节点的prev指向 由当前节点 修改为 当前节点的上一个节点
        next.prev = prev;
        x.next = null;//置空 垃圾回收
    }

    x.item = null;//置空 垃圾回收
    size--;//长度-1
    modCount++;//操作次数+1
    return element;//返回该元素
}

链表删除元素时结构图： 
（当删除元素不是首尾节点时） 

/**
 * 删除某个元素
 */
public boolean remove(Object o) {
    //根据删除元素是否为null分开进行遍历
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {//==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;
}

--------------------- 
原文：https://blog.csdn.net/qq_23830637/article/details/78983042