LinkedList 源码分析

LinkedList实现了List和Deque接口。实现所有可选列表操作，并允许所有元素（包括null ）。
在List接口的实现类中，ArrayList为列表，而LinkedList则为一个双向链表,并且在链表中也没有容量的概念，因为链表是无界的.
LinkedList有个特别，就是它的内部类，Node<E>

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

E item：节点
Node<E> next: 下一个节点
Node<E> prev: 上一个节点
Node表示链表中的一个节点，双向链表就表示每一个节点都会记录我上一个节点是谁，和我下一个节点是谁.就像是手牵手一样，如果我要往队伍中插入一个节点，就直接牵手就行了，删除一个就直接放掉那个节点的手就行了，这可要比ArrayList方便多了吧，哈哈哈~

来看看LinkedList的属性

// 节点数量
transient int size = 0;
// 第一个节点
transient Node<E> first;
// 最后一个节点
transient Node<E> last;

构造器:

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

咱们来看看这个addAll(c)方法吧

public boolean addAll(int index, Collection<? extends E> c) {
    // 校验index
    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;
}

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

add(E e): 添加元素到链表的最后

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

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
        // 上个last节点的下个节点为最新节点的上个节点
        l.next = newNode;
    size++;
    modCount++;
}

add(Integer index,E element):将元素插入到指定位置:

public void add(int index, E element) {
    // 校验index合法性
    checkPositionIndex(index);
    
    // 正常往最后插入
    if (index == size)
        linkLast(element);
    else
        // 从指定索引位置插入
        linkBefore(element, node(index));
}


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;
    // 如果指定索引的上个节点为空，说明该索引为第一个节点，那么需要从新指定first节点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

remove() : 删除第一个节点

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    // 设置节点的item与next为null
    f.item = null;
    f.next = null; // help GC
    // 设置它的下个节点为first node
    first = next;
    // 如果next为空，链表的最后节点也指定为null
    if (next == null)
        last = null;
    else
        // next的上一个节点为null
        next.prev = null;
    size--;
    modCount++;
    return element;
}

remove(int index)：删除指定位置的节点

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

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

其实这玩意原理都是一样的，就是把你要删的上个节点的跟下个节点的关系改变一下，这玩意看代码就行，用不着过多的说什么

clear() : 删除所有节点

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; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

每个节点属性设置为null，size清0

总结：
1.ArrayList和LinkedList都是List接口的实现类，ArrayList为列表，LinkedList为链表
2.ArrayList适合读多写少的场景，因为是根据数组实现，所以可以直接通过index获取元素，而LinkedList适合写多读少的场景，因为linkedList读取数据的话，需要迭代获取
3.在LinkedList中没有容量，因为链表是无界的，没有范围的