List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

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

/**
 * 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.
 * 首先获得最后一个元素，新建一个节点newNode，
 * 如果最后一个元素为空，则将newNode赋值给first
 * 否则将newNode赋值给最后一个元素的next
 */
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++;
}


/**
 * Returns the element at the specified position in this list.
 * 
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * 检查index合法性，调用node方法
 */
public E get( int index ) {
    checkElementIndex(index);
    return node(index).item ;
}

/**
 * Returns the (non -null) Node at the specified element index.
 * 采用二分，如果index小于size >> 1(size/2),那么将从第一个元素开始往前推
 * 否则，从最后一个元素往后推
 */
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 ;
    }
}

/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * 检查index合法性，根据index获得对应的Node元素作为参数，调用unlink方法
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Unlinks non -null node x.
 * 获得Node对象的element，前一个节点prev及后一个节点next
 * 处理x的prev节点：
 * 如果移除的元素为首元素(即prev为null)，那么直接将节点next赋给first
 * 否则，将next赋值给prev.next，并将x.prev置空
 * 处理x的next节点：
 * 如果移除的元素为尾元素(即next为null)，那么直接将节点prev赋值给last
 * 否则，将prev赋值给next.prev，并将x.next置空
 */
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 ;
}

/**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer. Any
  * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
  * DEFAULT_CAPACITY when the first element is added.
  * 底层存储数据的数组
  */
private transient Object[] elementData;

/**
  * The size of the ArrayList (the number of elements it contains).
  * 大小
  * @serial
  */
private int size;

  /**
  * Increases the capacity to ensure that it can hold at least the
  * number of elements specified by the minimum capacity argument.
  * 
  * @paramminCapacity the desired minimum capacity
  */
privatevoid grow(int minCapacity) {
    // overflow-conscious code
    intoldCapacity=elementData.length;
    intnewCapacity=oldCapacity+ (oldCapacity>> 1);
    if(newCapacity-minCapacity< 0)
        newCapacity=minCapacity;
    if(newCapacity-MAX_ARRAY_SIZE> 0)
        newCapacity=hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData= Arrays.copyOf(elementData,newCapacity);
 }

/**
  * Appends the specified element to the end of this list.
  *
  *@parame element to be appended to this list
  *@return<tt>true</tt>(as specified by{@link Collection#add})
  */
public boolean add(E e) {
    ensureCapacityInternal(size+ 1); // Increments modCount!!
    elementData[size++] =e;
    returntrue;
 }

private void ensureCapacityInternal(int minCapacity) {
    if(elementData==EMPTY_ELEMENTDATA) {
        minCapacity= Math.max(DEFAULT_CAPACITY,minCapacity);
     }

     ensureExplicitCapacity(minCapacity);
 }

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if(minCapacity-elementData.length> 0)
         grow(minCapacity);
 }

/**
  * Removes the element at the specified position in this list.
  * Shifts any subsequent elements to the left (subtracts one from their
  * indices).
  *
  *@paramindex the index of the element to be removed
  *@returnthe element that was removed from the list
  *@throwsIndexOutOfBoundsException{@inheritDoc}
  */
publicE remove(int index) {
     rangeCheck(index);

    modCount++;
     EoldValue= elementData(index);

    intnumMoved=size-index- 1;
    if(numMoved> 0)
         System.arraycopy(elementData,index+1,elementData,index,
                         numMoved);
    elementData[--size] =null;// clear to let GC do its work

    returnoldValue;
 }

@SuppressWarnings("unchecked")
 E elementData(int index) {
    return (E)elementData[index];
 }

/**
  * Returns the element at the specified position in this list.
  *
  *@param  index index of the element to return
  *@returnthe element at the specified position in this list
  *@throwsIndexOutOfBoundsException{@inheritDoc}
  */
publicE get(int index) {
     rangeCheck(index);

    return elementData(index);
 }