/**

 * Doubly-linked list implementation of the {@code List} and {@code Deque}

 * interfaces.  Implements all optional list operations, and permits all

 * elements (including {@code null}).

 * 双向链表实现了List和Deque接口。实现了List所有的操作,双向链表允许所有元素,包括null

 *

 * <p>All of the operations perform as could be expected for a doubly-linked

 * list.  Operations that index into the list will traverse the list from

 * the beginning or the end, whichever is closer to the specified index.

 * 对于LinkedList所有的操作都是可以被预期的。操作LinkedList将会遍历LinkedList的指针.

 * 解读：通过set(i,e),get(i)访问LinkedList的元素时,要遍历指针,如果i>LinkedList容量的一半,

 * 就从尾部开始遍历.

 *

 * <p><strong>Note that this implementation is not synchronized.</strong>

 * If multiple threads access a linked list concurrently, and at least

 * one of the threads modifies the list structurally, it <i>must</i> be

 * synchronized externally.  (A structural modification is any operation

 * that adds or deletes one or more elements; merely setting the value of

 * an element is not a structural modification.)  This is typically

 * accomplished by synchronizing on some object that naturally

 * encapsulates the list.

 * 注意,LinkedList是线程不同步的.如果多线程同时访问LinkedList,此时如果有一个线程修改LinkedList结构,

 * 那么就必须在外层进行同步操作处理(这里的修改结构包括添加元素,删除元素)。

 * 解读：ArrayList同样有此特性.

 *

 * If no such object exists, the list should be "wrapped" using the

 * {@link Collections#synchronizedList Collections.synchronizedList}

 * method.  This is best done at creation time, to prevent accidental

 * unsynchronized access to the list:<pre>

 *  List list = Collections.synchronizedList(new LinkedList(...));</pre>

 * 考虑线程同步问题,可以用Collections.synchronizedList替代LindedList

 *

 * <p>The iterators returned by this class's {@code iterator} and

 * {@code listIterator} methods are <i>fail-fast</i>: if the list is

 * structurally modified at any time after the iterator is created, in

 * any way except through the Iterator's own {@code remove} or

 * {@code add} methods, the iterator will throw a {@link

 * ConcurrentModificationException}.  Thus, in the face of concurrent

 * modification, the iterator fails quickly and cleanly, rather than

 * risking arbitrary, non-deterministic behavior at an undetermined

 * time in the future.

 * 在迭代一个LinkedList时,任何修改LinkedList的操作,迭代器都会终止,并抛出

 * ConcurrentModificationException异常.

 *

 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

 * as it is, generally speaking, impossible to make any hard guarantees in the

 * presence of unsynchronized concurrent modification.  Fail-fast iterators

 * throw {@code ConcurrentModificationException} on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness:   <i>the fail-fast behavior of iterators

 * should be used only to detect bugs.</i>

 * 快速失败机制,是一种错误检测机制。它只能被用来检测错误，因为JDK并不保证fail-fast机制一定会发生.

 * 参考我的博客 ”Iterator fail-fast“

 *　

 * @author  Josh Bloch

 * @see     List

 * @see     ArrayList

 * @since 1.2

 * @param <E> the type of elements held in this collection

 */

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

 /**

      * Replaces the element at the specified position in this list with the

      * specified element.

      *

      * @param index index of the element to replace

      * @param element element to be stored at the specified position

      * @return the element previously at the specified position

      * @throws IndexOutOfBoundsException {@inheritDoc}

      */

     public E set(int index, E element) {

         checkElementIndex(index);

         Node<E> x = node(index);

         E oldVal = x.item;

         x.item = element;

         return oldVal;

     }

  /**

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

      */

     public E get(int index) {

         checkElementIndex(index);

         return node(index).item;

     }

  /**

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

         }

     }