LinkedList源码解析

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

List list = Collections.synchronizedList(new LinkedList(...));

// 容量
transient int size = 0;

/**
 * 首节点
 * 不变的情况: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 尾节点
 * 不变的情况: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * 默认构造
 */
public LinkedList() {
}

/**
 * 通过一个集合初始化LinkedList,元素的顺序由集合的迭代器返回顺序决定
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

/**
 * 添加元素作为第一个元素
 * @param e the element to add
 */
@Override
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 内部方法:使用对应参数作为第一个节点元素
 */
private void linkFirst(E e) {
    // 得到首节点
    final Node<E> f = first;
    // 创建新节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 设置新的首节点
    first = newNode;
    // 如果之前的首节点为空(即size==0),则尾节点与首节点为同一个
    // 如果之前的首节点不为空,将之前的首节点的向前指向链接到新的首节点上
    if (f == null) {
        last = newNode;
    } else {
        f.prev = newNode;
    }
    // 长度+1
    size++;
    // 修改次数 + 1
    modCount++;
}

/**
 * 添加元素作为最后一个元素
 * @param e the element to add
 */
@Override
public void addLast(E e) {
    linkLast(e);
}
/**
 * 链接一个元素作为尾节点
 */
void linkLast(E e) {
    // 得到尾节点
    final Node<E> l = last;
    // 新建节点元素
    final Node<E> newNode = new Node<>(l, e, null);
    // 设置新的尾节点
    last = newNode;
    // 如果之前的尾节点为空(即size==0),则尾节点与首节点为同一个
    // 如果之前的尾节点不为空,将之前的尾节点的向后指向链接到新的尾节点上
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
    modCount++;
}

/**
 * 添加一个元素,默认添加到末尾作为最后一个元素
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
@Override
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 列表的指定位置插入指定的元素
 * - 当前位置如果有元素,则向右移动元素(对应索引加1),由linkBefore体现
 * @param index 待插入元素的索引
 * @param element 待插入元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
@Override
public void add(int index, E element) {
    checkPositionIndex(index);
    // 如果指定位置为最后,则添加到链表最后
    // 如果指定位置不是最后,则添加到指定元素前
    if (index == size) {
        linkLast(element);
    } else {
        linkBefore(element, node(index));
    }
}

/**
 * 在指定节点前插入节点,节点succ不能为空
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 获取前一个节点
    final Node<E> pred = succ.prev;
    // 创建一个新的节点,向前指向pred(前一个节点),向后指向succ(当前节点)
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 在pred.next 和 succ.prev之间链接上新的节点
    // 如果succ当前节点的前一个节点为空,则新节点为首节点
    succ.prev = newNode;
    if (pred == null) {
        first = newNode;
    } else {
        pred.next = newNode;
    }
    size++;
    modCount++;
}

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);

/**
 * 从指定的位置插入指定集合的所有元素
 * - 如果当前位置有元素存在,将该位置的元素移动到右边
 * - 新的元素按照指定集合的迭代器顺序放置
 * @param index 插入第一个元素的索引
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
@Override
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查索引是否正确 (0<=index<=size)
    checkPositionIndex(index);
    // 得到元素数组
    Object[] a = c.toArray();
    // 新添加的元素个数
    int numNew = a.length;
    // 若没有元素添加则直接返回false
    if (numNew == 0) {
        return false;
    }
    // 记录要插入的左右节点信息
    Node<E> pred, succ;
    /*
     * 如果插入位置为链表末尾
     * - 让当前元素前一节点链接原有的尾节点,后一节点链接null
     * 否则查找出指定位置的节点,在这节点之前链接上元素
     * - 前一节点为旧节点的前一节点,后一节点为旧节点
     */
    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);
        // 插入位置的前一节点为null,新节点设置为首节点
        // 插入位置的前一节点不为null,前一节点的下一节点设置为新节点
        if (pred == null) {
            first = newNode;
        } else {
            pred.next = newNode;
        }
        // pred设置为新节点,即插入位置后移
        pred = newNode;
    }

    // 如果succ为null,即一直在最后位置添加,让前一个节点成为最后节点
    // 如果succ不为null,已经没有元素可以链接,则将pred和succ闭合起来
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));

/**
 * 删除第一个元素并返回删除的元素
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
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;
    // 便于垃圾回收清理
    f.item = null;
    f.next = null; // help GC
    // 下一节点设置为首节点
    first = next;
    // 如果不存在下一个节点:则首尾都为null(空表)
    // 如果存在下一节点:它的向前指向为null,
    if (next == null) {
        last = null;
    } else {
        next.prev = null;
    }
    size--;
    modCount++;
    return element;
}

/**
 * 删除最后一个元素并返回删除的值
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E removeLast() {
    // 获取尾节点,如果为空则抛出异常
    final Node<E> l = last;
    if (l == null) {
        throw new NoSuchElementException();
    }
    return unlinkLast(l);
}
/**
 * 内部方法:删除尾节点并返回删除的前尾节点的值
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 获取尾节点的值
    final E element = l.item;
    // 得出此尾节点的前一节点
    final Node<E> prev = l.prev;
   // 清空尾节点的值和 前一节点(隔断/孤立尾节点) 便于垃圾回收清理
    l.item = null;
    l.prev = null; // help GC
    // 前一节点设置为尾节点
    last = prev;
    // 如果不存在前一个节点:则首尾都为null(空表)
    // 如果存在前一个节点:则它的向后指向为null
    if (prev == null) {
        first = null;
    } else {
        prev.next = null;
    }
    size--;
    modCount++;
    return element;
}

/**
 * 出队(从前端)
 * - 如果不存在会抛出异常而不是返回null,存在的话会返回值并移除这个元素(节点)
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E remove() {
    return removeFirst();
}
/**
 * 删除列表指定位置的元素
 * - 向左移动剩余子元素(对应索引减1)
 * - 返回列表上被移除的值
 * @param index 被移除元素的索引
 * @return 指定位置之前的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
@Override
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;

    // 如果前一节点为null,即当前节点为首节点,让下一节点成为首节点
    // 如果前一节点不为null,断开当前节点的前一节点链接(下方断开后一节点链接)
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果后一节点为null,即当前节点为尾节点,让前一节点成为尾节点
    // 如果后一节点不为null,断开当前节点的后一节点链接
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    // 方便gc回收,当前的值置为null
    x.item = null;
    size--;
    modCount++;
    return element;
}
/**
 * 删除指定元素
 * - 从first节点开始第一个出现的元素
 * - 如果列表中不包含此元素,就不改变
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
@Override
public boolean remove(Object o) {
    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;
}

/**
 * 清空表:方便gc回收
 */
@Override
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++;
}

/**
 * 用指定位置的元素替换指定位置的元素
 * @param index 代替指定位置的元素
 * @param element 指定位置被存储的元素
 * @return 指定位置之前的元素值
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
@Override
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

/**
 * 获取第一个元素
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E getFirst() {
    // 获取到首节点,判断首节点为空则抛出异常
    final Node<E> f = first;
    if (f == null) {
        throw new NoSuchElementException();
    }
    return f.item;
}

/**
 * 获取最后一个元素
 * @return the last element in this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E getLast() {
    // 获取尾节点,如果为空则抛出异常
    final Node<E> l = last;
    if (l == null) {
        throw new NoSuchElementException();
    }
    return l.item;
}

/**
 * 获取指定索引的节点值
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
@Override
public E get(int index) {
    // 检查元素索引:0<=index<=size
    checkElementIndex(index);
    return node(index).item;
}

/**
 * 检查是否包含某个元素
 * @param o element whose presence in this list is to be tested
 * @return {@code true} if this list contains the specified element
 */
@Override
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

/**
 * 获取指定元素第一次出现的索引,不存在就返回-1
 * - 不能二分查找了,所以通常根据索引获得元素的速度比下方通过元素获得索引的速度快
 * @param o 待索引的元素
 * @return
 */
@Override
public int indexOf(Object o) {
    int index = 0;
    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;
}

/**
 * 获取指定元素从last开始第一次出现的索引,不存在就返回-1
 * @param o 待索引的元素
 * @return
 */
@Override
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);
    // 先来一次二分,减少遍历查找的次数
    if (index < (size >> 1)) {
        // index==0时不会循环,直接返回first 下方同理
        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;
    }
}

/**
 * 出队(从前端)获得第一个元素,不存在返回null,不会删除元素(节点)
 * @return 头部元素没有则返回null
 */
@Override
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 出队(从前端)获取第一个元素,若为null抛出异常而不是返回null
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E element() {
    return getFirst();
}

/**
 * 出队(从前端)
 * - 如果不存在返回null,存在的话会返回值并删除这个元素(节点)
 * @return
 */
@Override
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 出队(从前端)
 * - 如果不存在会抛出异常而不是返回null,存在的话会返回值并移除这个元素(节点)
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 */
@Override
public E remove() {
    return removeFirst();
}

/**
 * 入队(从后端)
 * - 始终返回true
 * @param e the element to add
 * @return
 */
@Override
public boolean offer(E e) {
    return add(e);
}

Iterator iter = list.iterator();
while (iter.hasNext()) {
    System.out.println(iter.next());
}

ListIterator<String> lIter = list.listIterator();
//顺向遍历
while(lIter.hasNext()) {
　　System.out.println(lIter.next());
}
//逆向遍历
while(lIter.hasPrevious()) {
　　System.out.println(lIter.previous());
}

for(String str:list) {
    System.out.println(str);
}

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