概述

ArrayList和LinkedList可以说是List接口的两种不同的实现。

• ArrayList底层是数组实现的，所以增删效率低，但是改查效率高。
• 而LinkedList底层是链表实现的，所以增删由于不需要移动底层数组数据，只需要修改链表节点指针，所以效率较高。而改查，都需要先定位到目标节点，所以效率较低。

概括的说：LinkedList是线程不安全的，允许元素为null的双向链表。

其底层数据结构是链表，它实现List<E>, Deque<E>,Cloneable,java.io.Serializable接口，

它实现了Deque<E>，所以它也可以作为一个双端队列。和ArrayList相比，没有实现RandomAccess接口，所以随机访问元素的速度较慢。

RandomAccess接口

public interface RandomAccess {
}

• 存在的目的：空接口，用来标记这个类是支持快速随机访问。
• 在对列表进行访问的时候，可以有随机访问和连续访问（之后会用代码进行演示），自然，这两种访问方式是有效率上的区别的，对一个支持随机访问的列表应该要使用一个随机访问算法，反而言之，一个适用于连续访问的列表就应该用连续访问的算法。那么问题来了，你怎么知道要被遍历的列表到底是支持那种访问的？这个接口就是为了区分这个点。

随机访问：可以访问该数据结构中的任意一个节点，比如一个数据有10个元素，你可以直接通过下标来访问第6个元素。

连续访问：对于链表，如果存在10个节点，要访问第6个节点，那么只能从链表的头，依次遍历相邻的每一个节点。

因其底层数据结构是链表，所以它的增删只需要移动指针即可，故时间效率较高。不需要批量扩容，也不需要预留空间，所以空间效率比ArrayList高

缺点是需要随机访问元素时，时间效率很低，虽然底层根据下标查询Node的时候，会根据index判断目标Node在前半段还是后半段，然后决定是顺序还是逆序查询，以提高时间效率。

字段

// 集合元素数量
transient int size = 0;

// 链表头结点
transient Node<E> first;

// 链表尾节点
transient Node<E> last;

构造方法

public LinkedList() {
}

// 调用 public boolean addAll(Collection<? extends E> c) 将集合c所有元素插入链表中
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

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

可以看出，这是一个双向链表。

增加

1 插入多个节点 addAll

// addAll ，在尾部批量添加
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c); // 以size为插入下标，插入集合c中所有元素
}

// 以index为插入下标，插入集合c中所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // 检查越界[0,size] 闭区间 ----------------------------->checkPositionIndex

    Object[] a = c.toArray(); // 拿到目标集合数组
    int numNew = a.length; // 新增元素的数量
    if (numNew == 0) // 如果新增元素数量为0，则不增加，并返回false
        return false;

    Node<E> pred, succ; // pred:index节点的前置节点，succ:index节点的后置节点
    if (index == size) { // 在链表尾部追加数据
        succ = null; // size节点（队尾）的后置节点一定是null
        pred = last; // 前置节点就是队尾
    } else {
        succ = node(index); // 取出index节点，作为后置节点 ----------------------------------->node
        pred = succ.prev; // 前置节点是，index节点的前一个节点
    }

    // 链表批量增加，是靠for循环遍历原数组，依次执行插入节点的操作。
    for (Object o : a) { // 遍历要添加的节点
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); // 以前置节点 和 元素值e，构建new一个新节点
        if (pred == null) // 如果前置节点是null，说明是头结点
            first = newNode; // 更新头结点first为新节点newNode
        else // 否则 前置节点的后置节点设置为新节点
            pred.next = newNode;
        pred = newNode; // 当前节点为前置节点，为下次添加新节点做准备
    }

    if (succ == null) { // 循环结束后，如果后置节点succ是null，说明此时是在队尾追加的
        last = pred; // 则设置尾节点为pred
    } else {// 否则 是在队中插入的节点，更新前置节点 后置节点
        pred.next = succ;  // 设置pred的后置节点为succ
        succ.prev = pred;  // 后置节点succ的前置节点为pred
    }

    size += numNew; // 修改size
    modCount++; // 修改modCount
    return true;
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
}

// 根据index，查询出Node
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 通过下标获取某个node的时候 （增、查），会根据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;
    }
}

小结：

• 链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的
• 通过下标获取某个node的时候（添加、查找），会根据index处于前半段还是后半段进行一个折半，以提升查询效率、

2 插入单个节点 add

在尾部添加节点

// 在尾部插入一个节点 addpublic boolean add(E e) {    linkLast(e);    return true;}// 生成新节点 并插入到 链表尾部，更新last/first节点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++;//修改size    modCount++; // 修改modCount}

在指定下标插入节点

// 在指定下标，index处，插入一个新节点public void add(int index, E element) {    checkPositionIndex(index); // 检查下标是否越界[0,size]    if (index == size) // 在尾节点后插入        linkLast(element);    else // 在中间插入        linkBefore(element, node(index));}// 在succ节点前，插入一个新节点evoid linkBefore(E e, Node<E> succ) {    // assert succ != null;    // 保存后置节点的前置节点    final Node<E> pred = succ.prev;    // 以前置节点pred 后置节点succ 和 元素值e 构建一个新节点    final Node<E> newNode = new Node<>(pred, e, succ);    // 新节点newNode是原节点succ的前置节点    succ.prev = newNode;    if (pred == null) // 如果之前的前置节点是空，说明succ是原头结点，所以新节点就是现在的头结点        first = newNode;    else // 否则构建前置节点的后置节点为new        pred.next = newNode;    size++; // 修改数量    modCount++; // 修改modCount}

// 从链表尾追加节点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;}// 等价于 addFirstpublic void push(E e) {    addFirst(e);}

删除 remove

// 删：remove目标index的节点public E remove(int index) {     checkElementIndex(index); // 检查是否越界 下标[0,size) 左闭右开 ---------------------->checkElementIndex    return unlink(node(index)); // 通过node方法找到index处节点，调用unlink方法删除}// 从链表上删除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) { // 如果前置节点为null，说明x是头结点        first = next; // 更新头结点为x的后置节点    } else {         prev.next = next; // 将前置节点pre的后置节点设为next节点        x.prev = null; // 将当前节点的前置节点置空    }    if (next == null) { // 如果后置节点为空（说明当前节点是原尾节点）        last = prev; // 则 尾节点为前置节点    } else {         next.prev = prev; // x的后置节点next的前置节点设为pre        x.next = null; // 将x的后置节点置空    }    x.item = null; // 将当前元素置空，方便GC    size--; // 修改数量    modCount++; // 修改modCount    return element; // 返回取出的元素值}

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

删除链表中的指定节点

// 因为要考虑null元素，需要分情况遍历public boolean remove(Object o) {    // 如果要删除的是null节点（从remove和add 里可以看出，允许元素为null）    // 遍历每个节点 对比    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;}

删除也一定会修改modCount。

按下标删，也是先根据index找到Node，然后去链表上unlink掉这个node。

按元素删，会先去遍历链表寻找是否有该Node，考虑到允许null，需要分情况遍历，然后再去unlink这个节点。如果有多个相同元素，会删除第一个碰到的元素。

修改 set

public E set(int index, E element) {    checkElementIndex(index); // 检查越界[0,size)    Node<E> x = node(index); // 取出对应的Node    E oldVal = x.item; // 保存旧item，供返回    x.item = element; // 用新值覆盖旧值    return oldVal; // 返回旧值}

修改也是先根据index找到Node，然后替换值，不修改modCount。

查找 get

按下标index查找节点

public E get(int index) {    checkElementIndex(index);// 检查越界[0,size)    return node(index).item; // 调用node()方法 取出Node节点}

按元素值从头到尾查找下标

// 根据节点对象 查询下标public int indexOf(Object o) {    int index = 0;    if (o == null) {  // 如果o是null        // 遍历链表，找到第一个item是null的节点，返回index        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else { // 遍历链表        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    // 若没有找到，返回-1    return -1;}

按元素值从尾到头查找下标

// 从尾至头遍历链表，找到目标元素值为o的节点public int lastIndexOf(Object o) {    int index = size;    if (o == null) {        for (Node<E> x = last; x != null; x = x.prev) {            index--;            if (x.item == null)                return index;        }    } else {        for (Node<E> x = last; x != null; x = x.prev) {            index--;            if (o.equals(x.item))                return index;        }    }    return -1;}

查找不修改modCount

toArray()

public Object[] toArray() {    // new 一个新数组，然后遍历链表，将每个元素存在数组里，返回    Object[] result = new Object[size];    int i = 0;    for (Node<E> x = first; x != null; x = x.next)        result[i++] = x.item;    return result;}

其他API

// 判断链表是否包含指定元素public boolean contains(Object o) {    return indexOf(o) != -1;}// 清空链表public void clear() {    // 遍历链表, 删除所有节点, 方便 GC 回收    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;    modCount++;}// 克隆 浅拷贝public Object clone() {    LinkedList<E> clone = superClone();    // 置为空链表    clone.first = clone.last = null;    clone.size = 0;    clone.modCount = 0;    // 添加链表的所有元素    for (Node<E> x = first; x != null; x = x.next)        clone.add(x.item);    return clone;}