詳解Java 集合系列（三）—— LinkedList

/**
  * 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;        // 將當(dāng)前最后一個(gè)元素寄存在 l
  final Node<E> newNode = new Node<>(l, e, null);  // new 一個(gè)新節(jié)點(diǎn)：pre的引用為l；存儲(chǔ)元素為e；next的引用為null
  last = newNode;          // 將新節(jié)點(diǎn)引用覆蓋成員變量 last
  if (l == null)          
   first = newNode;        // 若l為null，說(shuō)明之前鏈表為空，此時(shí)新節(jié)點(diǎn)為首個(gè)元素
  else
   l.next = newNode;        // 否則，更新l的next引用
  size++;            // size+1
  modCount++;           // 非查詢操作 modCount 都會(huì) +1
 }

/**
  * Inserts the specified element at the specified position in this list.
  * Shifts the element currently at that position (if any) and any
  * subsequent elements to the right (adds one to their indices).
  *
  * @param index index at which the specified element is to be inserted
  * @param element element to be inserted
  * @throws IndexOutOfBoundsException {@inheritDoc}
  */
 public void add(int index, E element) {
  checkPositionIndex(index); // 檢查 index 是否大于 size

  if (index == size)
   linkLast(element);  // 直接在鏈表末尾追加
  else
   linkBefore(element, node(index)); // 插入index 節(jié)點(diǎn)前面
 }
 
 
 // 檢查 index 是否超出范圍 超出則拋出 IndexOutOfBoundsException
 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;
 }
 
 
 
 /**
  * 根據(jù) index 查找 node
  * 該方法利用了雙向鏈表的特性，index 距離哪個(gè)鏈表頭近就從哪邊開始開始遍歷
  * 時(shí)間復(fù)雜度為 O(n/2)；
  * 當(dāng) index 接近 size 的中間值時(shí)，效率最低
  * Returns the (non-null) Node at the specified element index.
  */
 Node<E> node(int index) {
  // assert isElementIndex(index);

  if (index < (size >> 1)) {   // size 右移一位（除以2）
   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;
  }
 }