LinkedList

概述 LinkedList 与 ArrayList 一样实现 List 接口，只是 ArrayList 是 List 接口的大小可变数组的实现，LinkedList 是 List 接口基于链表的实现。基于链表实现的方式使得 LinkedList 在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 逊色些。

定义

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

继承自 AbstractSequentialList 类，AbstractSequentialList 类继承自 AbstractList 类，只支持按次序访问，而AbstractList 支持随机访问。

属性

//链表长度
transient int size = 0;
//链表头结点
transient Node<E> first;
//链表尾结点
transient Node<E> last;
/**
 *结点类
 */
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;
    }
}

构造器

public LinkedList() {
}
//把集合内元素按顺序转换为链表
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

第二个构造器接收一个集合，调用默认构造器构建空链表，之后调用 addAll() 方法，将集合内元素按迭代器返回的顺序添加到链表里。

/**
 *将集合内元素按顺序全部添加到链表里
 *@param c 待添加元素集合
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
/**
 *@param index 插入的结点位置
 *@param c 待插入元素的集合
 */
public boolean addAll(int index, Collection<? extends E> c) {
    //检测index是否在范围内 0 <= index <= size
    checkPositionIndex(index);
    //将集合转为数组
    Object[] a = c.toArray();
    //获取（数组大小）元素个数
    int numNew = a.length;
    //空集合，返回false
    if (numNew == 0)
        return false;
    //定义两个结点，前驱结点和后继结点
    Node<E> pred, succ;
    //如果插入位置为当前链表大小，尾插，前驱结点为当前链表尾结点
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        //查找结点，作为后继结点
        succ = node(index);
        //保存该结点的前驱结点
        pred = succ.prev;
    }
    //forEach遍历数组
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //构建新结点，元素为e，前驱结点为pred，后继结点为null
        Node<E> newNode = new Node<>(pred, e, null);
        //如果前驱结点为null，该结点作为该链表的头结点
        if (pred == null)
            first = newNode;
        else
            //否则该结点连接前驱结点的后继结点（往后链接结点）
            pred.next = newNode;
        //新的结点作为前驱结点（指针向后移）
        pred = newNode;
    }
    //遍历完后，如果后继结点为null，即28行的情况，尾插的情况，保存链表新的尾结点
    if (succ == null) {
        last = pred;
    } else {
        //不是尾插，即把后面部分链接起来
        pred.next = succ;
        succ.prev = pred;
    }
    //保存新的链表长度
    size += numNew;
    modCount++;
    return true;
}

addAll方法大概的思路是判断链表添加元素是否是尾插，如果是，直接向链表后链接新结点，原尾结点作为第一次操作的位置；如果是在链表中间执行操作，则用pred，succ保存指定位置分开后待链接的前半部分和后半部分的链，在从pred开始操作完链接操作后，把原后半部分的链链接回去。

插入结点

对于链表来说，向链表中插入元素即是新建一结点，然后对链表进行新结点的插入链接操作。

/**
 *插入元素方法，默认尾插
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
public void addFirst(E e) {
    linkFirst(e);
}
public void addLast(E e) {
    linkLast(e);
}
/**
 *向指定位置插入元素
 *@param index 第几个结点
 */
public void add(int index, E element) {
    //下标范围检查
    checkPositionIndex(index);
    //如果下标为链表大小，尾插，否则头插
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
/**
 *头插，向链表前面插入结点
 */
private void linkFirst(E e) {
    //记录头结点
    final Node<E> f = first;
    //构造新结点，后继结点为当前链表头结点
    final Node<E> newNode = new Node<>(null, e, f);
    //保存新的头结点
    first = newNode;
    //如果当前头结点为null，即空链表，则此时只有一个结点，尾结点也为新结点
    //否则保存前驱结点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    //链表大小++
    size++;
    modCount++;
}
/**
 *尾插，向链表尾部插入结点
 */
void linkLast(E e) {
    //记录尾结点
    final Node<E> l = last;
    //构建新结点，前驱结点为原链表尾结点
    final Node<E> newNode = new Node<>(l, e, null);
    //保存新的尾结点
    last = newNode;
    //如果尾结点为null，空链表，此时只有一个结点，头结点也为新结点
    //否则保存后继结点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //链表大小++
    size++;
    modCount++;
}
/**
 *向链表某个结点前插入结点
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //由index查找到的结点，记录此结点的前驱
    final Node<E> pred = succ.prev;
    //构建新结点，前驱为指定结点的前驱，后继为指定结点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //保存新的前驱结点
    succ.prev = newNode;
    //指定结点前驱为null，头结点
    if (pred == null)
        //记录新的头结点
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

删除结点

/**
 *移除头结点
 */
public E removeFirst() {
    //保存头结点
    final Node<E> f = first;
    //如果链表为空，抛异常
    if (f == null)
        throw new NoSuchElementException();
    //否则调用unlinkFirst()方法
    return unlinkFirst(f);
}
/**
 *移除尾结点，原理同上
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
/**
 *移除链表第一次出现的指定元素的方法
 *@param o 指定元素
 */
public boolean remove(Object o) {
    //如果o为null，移除为数据域null的结点
    if (o == null) {
        //遍历，移除
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
       }
    } else {
        //不为null，移除指定的，遍历，移除
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
/**
 *移除指定下标的结点
 */
public E remove(int index) {
    //检查下标范围
    checkElementIndex(index);
    //调用unlink(node(index))方法
    return unlink(node(index));
}
/**
 *默认移除头结点方法
 */
public E remove() {
    return removeFirst();
}
/**
 *移除链表中第一次出现的指定元素结点
 *@param o 指定元素
 */
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}
/**
 *移除链表最后一次出现指定元素结点
 *@param o 指定元素
 */
public boolean removeLastOccurrence(Object o) {
    //该方法同remove(Object o),只是前者是从前往后遍历，该方法从后往前遍历，相当于从前往后的最后一次
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
 }
/**
 *断链头结点方法
 *@param f 头结点
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //记录头结点的元素值
    final E element = f.item;
    //记录第二个结点
    final Node<E> next = f.next;
    //头结点数据域和后继置null，待GC
    f.item = null;
    f.next = null; 
    //第二个结点为头指针
    first = next;
    //如果第二个指针为null，表明原链表只有一个结点，尾结点也是null
    if (next == null)
        last = null;
    else
        //否则头结点前驱置null
        next.prev = null;
    size--;
    modCount++;
    return element;
}
/**
 *断链尾结点方法
 *@param l 尾结点
 */
private E unlinkLast(Node<E> l) {
    //记录尾结点的元素值
    final E element = l.item;
    //记录倒数第二个结点
    final Node<E> prev = l.prev;
    //置null，待GC
    l.item = null;
    l.prev = null;
    //倒数第二个结点为新的尾结点
    last = prev;
    //若倒数第二个结点为null，即原链表只有一个结点，头结点也置null
    if (prev == null)
        first = null;
    else
        //否则后继置null
        prev.next = null;
    size--;
    modCount++;
    return element;
}
/**
 *断链指定结点
 *@param 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;
    //如果前驱结点为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;
    }
    //置null待GC
    x.item = null;
    size--;
    modCount++;
    return element;
}
/**
 *移除所有元素
 */
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
    for (Node<E> x = first; x != null; ) {
        //遍历链表，循环置null，待GC
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

查找方法

/**
 *获取头结点元素
 */
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;
}

/**
 *获取指定下标结点元素
 */
public E get(int index) {
    //下标范围检查
    checkElementIndex(index);
    return node(index).item;
}

/**
 *返回指定元素首次出现的下标位置，若无返回-1
 *@param o 指定元素
 */
public int indexOf(Object o) {
    int index = 0;
    //遍历链表，index++，找到元素后返回index值
    if (o == null) {
        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++;
        }
    }
    return -1;
}

/**
 *返回指定元素最后一次出现的下标位置，若无返回-1
 *该方法同上，前者从前往后遍历链表，该方法从后往前遍历链表，等同于最后一次
 */
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;
}

/**
 *根据索引寻找结点，
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    //size >> 1 index小于size/2，则前半段遍历，这一操作相当于加速操作，优化了查找速度
    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;
    }
}

优点

• LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据
• 对于新增数据，LinkedList可以动态的分配内存
• 线程安全

缺点

• 对于随机访问方法，LinkedList的效率相较ArrayList会比较低，因为它要从头遍历链表
• LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为

总结： 大多数情况下使用ArrayList；在数据量大且需要频繁读取集合中的元素时，使用ArrayList效率较高，而在插入和删除操作较多时，使用LinkedList效率较高。

• 在数据量少的时候，两者效率相差不大。
• 对于中间插入删除操作，LinkedList效率比ArrayList效率高，因为ArrayList还要进行数据的移动。
• 对于查找操作，ArrayList效率远比LinkedList高，因为LinkedList还要遍历链表。