LinkedList

LinkedList 从实现的角度来分析，它实现了 Deque 接口，所以不仅可以作为队列（FIFO）使用，还可以作为栈（LIFO）使用

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    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;
}

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

ListIterator

LinkedList 有一个方法 listIterator，会拿到迭代器，他与传统的迭代器不同，可以获取上一个元素，和判断上一个元素是否存在，由于 LinkedList 没有实现 RadomAccess 接口，所以他的 for 循环效率低于 iterator

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

LinkedList 由于是链表形式，所以他的 get 的效率很低，因为每次都要进行二分查找，确定位置，然后再进行遍历操作，所以在使用 LinkedList 的时候推荐使用 iterator

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
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;
    }
}