// 进栈
public E push(E item) {
    addElement(item);

    return item;
}

// 出栈
public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

// 链尾追加
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++;
}

// 指定节点前插入
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 插入节点，succ为Index的节点，可以看到，是插入到index节点的前一个节点
    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 void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, 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;
}

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

Node<E> node(int index) {
    // 使用了二分法
    if (index < (size >> 1)) { // 如果索引小于二分之一，从first开始遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // 如果索引大于二分之一，从last开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 进队
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

// 出队
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

// 进栈
public void push(E e) {
    addFirst(e);
}

// 出栈，如果为空列表，会抛出异常
public E pop() {
    return removeFirst();
}