### LinkedList LinkedList基于雙向鏈表機制實現； 雙向鏈表就是集合中的每個元素都知道其前一個元素和后一個元素的位置 【知識點】 * 順序訪問會非常高效，而隨機訪問效率比較低 * LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。 * LinkedList 實現 List 接口，能對它進行隊列操作。 * LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。 * LinkedList 實現了Cloneable接口，即覆蓋了函數clone\(\)，能克隆。 * LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。 * LinkedList 是非同步的 ### LinkedList屬性 ``` public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ //當前有多少個節點 transient int size = 0; //第一個節點 transient Node<E> first; //最后一個節點 transient Node<E> last; //省略內部類和方法。。 } ``` ### API * **add\(E e\)** 該方法直接將新增的元素放置鏈表的最后面，然后鏈表的長度（size）加1，修改的次數（modCount）加1 ``` public boolean add(E e) { linkLast(e); return true; } 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++; } ``` * **add\(int index, E element\)** 指定位置往數組鏈表中添加元素 1. 檢查添加的位置index 有沒有小于等于當前的長度鏈表size，并且要求大于0 2. 如果是index是等于size，那么直接往鏈表的最后面添加元素，相當于調用add\(E e\)方法 3. 如果index不等于size，則先是索引到處于index位置的元素，然后在index的位置前面添加新增的元素 ``` public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { // assert succ != null; 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++; } ``` * **get\(int 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; } } ```