[源码分析]ArrayList和LinkedList如何实现的？我看你还有机会！（二）

transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;
/**
 * Constructs an empty list.
 */
public LinkedList() {
}

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 E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
 * Returns the (non-null) Node at the specified element index.
 */
// 遍历查找 index 位置的节点信息
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 这里判断 index 是在当前链表的前半部分还是后半部分，然后决定是从
    // first 向后查找还是从 last 向前查找。
    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;
    }
}

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    // 新节点，prev 为当前尾部节点，e为元素值，next 为 null，
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
         // 目前的尾部节点 next 指向新的节点
        l.next = newNode;
    size++;
    modCount++;
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 如果位置就是当前链表尾部，直接尾插
        linkLast(element);
    else
        // 获取 index 位置的节点，插入新的元素
        linkBefore(element, node(index));
}
/**
 * Inserts element e before non-null Node succ.
 */
// 在指定节点处新增元素，修改指定元素的下一个节点为新增元素，新增元素的下一个节点是查找到得 node 的next节点指向，
// 新增元素的上一个节点为查找到的 node 节点，查找到的 node 节点的 next 指向 node 的 prev 修改为新 Node
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;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
/**
 * Unlinks non-null node 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) {
        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;
}

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

Queue<String> queue = new LinkedList<>();
queue.add("a");
queue.add("b");
queue.add("c");
queue.add("d");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
// result：
// a
// b
// c
// d