LinkedList

内部类 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;
    }
}

意味着是双向链表，每个节点都记录着前后节点

基本操作

加

默认添加到末尾，add(E e) 调用 linkLast(E e)

相对于的，就会有 addFirst(E e)、addLast(E e)，就会有 linkFirst(E e)

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * Links e as last element.
 */
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++;
    modCount++;
}
// 等等

---

还有一个 add(int index, E element) 在指定位置插入

先判断下标有没有越界：checkPositionIndex(index)，越界就抛异常了

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

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

// Tells if the argument is the index of a valid position for an iterator or an add operation.
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

会判断是不是插入末尾，要是插中间就会调 void linkBefore(E e, Node<E> succ)，而这个 Node<E> node(int index) 方法就是返回了这个下标处本来的节点

这个 Node<E> node(int index) 方法返回方式是

• 看下标在左半部分还是右半部分，来确定是从左边遍历还是右边遍历

最后再调 void linkBefore(E e, Node<E> succ) 方法

public void add(int index, E element) {
    // 判断下标有没有越界
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}
/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 这个 succ 就是原本下标的元素
    // 前
    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++;
}

---

清空

对于清空 clear()，置空是为了方便 GC

/**
 * Removes all of the elements from this list.
 * The list will be empty after this call returns.
 */
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++;
}

找

int indexOf(Object o) 返回此列表中指定元素首次出现的索引

会分成是不是 null 两种情况

public int indexOf(Object o) {
    int index = 0;
    if (o == null) { // 是 null
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else { // 不是 null
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

删

最基本的方法就是 E unlinkFirst(Node<E> f) 和 E unlinkLast(Node<E> l)