java.util?
類 LinkedList<E>
java.lang.Objectjava.util.AbstractCollection<E>java.util.AbstractList<E>java.util.AbstractSequentialList<E>java.util.LinkedList<E>List?接口的鏈接列表實現。實現所有可選的列表操作，并且允許所有元素（包括?null）。
除了實現?List?接口外，LinkedList?類還為在列表的開頭及結尾?get、remove?和?insert?元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。
此類實現?Deque?接口，為?add、poll?提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。
所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。
操作效率：大部分效率都是o(n)的
同步：
注意，此實現不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須?保持外部同步。（結構修改指添加或刪除一個或多個元素的任何操作；僅設置元素的值不是結構修改。）這一般通過對自然封裝該列表的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用?Collections.synchronizedList?方法來“包裝”該列表。最好在創建時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));iterator ：
此類的?iterator?和?listIterator?方法返回的迭代器是快速失敗?的：在迭代器創建之后，如果從結構上對列表進行修改，除非通過迭代器自身的?remove?或?add?方法，其他任何時間任何方式的修改，迭代器都將拋出?ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。
注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出?ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。
?
?
| 構造方法摘要 | |
|---|---|
LinkedList()???????????構造一個空列表。 | |
LinkedList(Collection<? extends?E>?c)???????????構造一個包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。 | |
| 方法摘要 | ||
|---|---|---|
?boolean | add(E?e)???????????將指定元素添加到此列表的結尾。 | |
?void | add(int?index,?E?element)???????????在此列表中指定的位置插入指定的元素。 | |
?boolean | addAll(Collection<? extends?E>?c)???????????添加指定 collection 中的所有元素到此列表的結尾，順序是指定 collection 的迭代器返回這些元素的順序。 | |
?boolean | addAll(int?index,?Collection<? extends?E>?c)???????????將指定 collection 中的所有元素從指定位置開始插入此列表。 | |
?void | addFirst(E?e)???????????將指定元素插入此列表的開頭。 | |
?void | addLast(E?e)???????????將指定元素添加到此列表的結尾。 | |
?void | clear()???????????從此列表中移除所有元素。 | |
?Object | clone()???????????返回此?LinkedList?的淺表副本。 | |
?boolean | contains(Object?o)???????????如果此列表包含指定元素，則返回?true。 | |
?Iterator<E> | descendingIterator()???????????返回以逆向順序在此雙端隊列的元素上進行迭代的迭代器。 | |
?E | element()???????????獲取但不移除此列表的頭（第一個元素）。 | |
?E | get(int?index)???????????返回此列表中指定位置處的元素。 | |
?E | getFirst()???????????返回此列表的第一個元素。 | |
?E | getLast()???????????返回此列表的最后一個元素。 | |
?int | indexOf(Object?o)???????????返回此列表中首次出現的指定元素的索引，如果此列表中不包含該元素，則返回 -1。 | |
?int | lastIndexOf(Object?o)???????????返回此列表中最后出現的指定元素的索引，如果此列表中不包含該元素，則返回 -1。 | |
?ListIterator<E> | listIterator(int?index)???????????返回此列表中的元素的列表迭代器（按適當順序），從列表中指定位置開始。 | |
?boolean | offer(E?e)???????????將指定元素添加到此列表的末尾（最后一個元素）。 | |
?boolean | offerFirst(E?e)???????????在此列表的開頭插入指定的元素。 | |
?boolean | offerLast(E?e)???????????在此列表末尾插入指定的元素。 | |
?E | peek()???????????獲取但不移除此列表的頭（第一個元素）。 | |
?E | peekFirst()???????????獲取但不移除此列表的第一個元素；如果此列表為空，則返回?null。 | |
?E | peekLast()???????????獲取但不移除此列表的最后一個元素；如果此列表為空，則返回?null。 | |
?E | poll()???????????獲取并移除此列表的頭（第一個元素） | |
?E | pollFirst()???????????獲取并移除此列表的第一個元素；如果此列表為空，則返回?null。 | |
?E | pollLast()???????????獲取并移除此列表的最后一個元素；如果此列表為空，則返回?null。 | |
?E | pop()???????????從此列表所表示的堆棧處彈出一個元素。 | |
?void | push(E?e)???????????將元素推入此列表所表示的堆棧。 | |
?E | remove()???????????獲取并移除此列表的頭（第一個元素）。 | |
?E | remove(int?index)???????????移除此列表中指定位置處的元素。 | |
?boolean | remove(Object?o)???????????從此列表中移除首次出現的指定元素（如果存在）。 | |
?E | removeFirst()???????????移除并返回此列表的第一個元素。 | |
?boolean | removeFirstOccurrence(Object?o)???????????從此列表中移除第一次出現的指定元素（從頭部到尾部遍歷列表時）。 | |
?E | removeLast()???????????移除并返回此列表的最后一個元素。 | |
?boolean | removeLastOccurrence(Object?o)???????????從此列表中移除最后一次出現的指定元素（從頭部到尾部遍歷列表時）。 | |
?E | set(int?index,?E?element)???????????將此列表中指定位置的元素替換為指定的元素。 | |
?int | size()???????????返回此列表的元素數。 | |
?Object[] | toArray()???????????返回以適當順序（從第一個元素到最后一個元素）包含此列表中所有元素的數組。 | |
| toArray(T[]?a)???????????返回以適當順序（從第一個元素到最后一個元素）包含此列表中所有元素的數組；返回數組的運行時類型為指定數組的類型。 | |
?
?
package java.util;
import java.util.function.Consumer;
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;/*** 無參構造方法*/public LinkedList() {}/*** 通過一個集合初始化，元素順序有這個集合的迭代器返回順序決定* * @param c* 其元素將被放入此列表中的集合* @throws NullPointerException* 如果指定的集合是空的*/public LinkedList(Collection<? extends E> c) {// 調用無參構造this();// 添加所有的元素addAll(c);}/*** 頭插，內部使用*/private void linkFirst(E e) {// 當前首結點final Node<E> f = first;// 構建新節點final Node<E> newNode = new Node<>(null, e, f);// 將newNode作為首節點first = newNode;// 如果原首節點為null，即原鏈表為null，則鏈表尾節點也設置為newNodeif (f == null)last = newNode;else // 否則，原首節點的prev設置為newNodef.prev = newNode;size++; // 長度+1modCount++; // 修改次數+1}/*** 尾插*/void linkLast(E e) {// 獲取尾結點final Node<E> l = last;// 構建新節點final Node<E> newNode = new Node<>(l, e, null);// newNode作為尾節點last = newNode;// 如果原尾節點為null，即原鏈表為null，則鏈表首節點也設置為newNodeif (l == null)first = newNode;else // 否則，原尾節點的next設置為newNodel.next = newNode;size++;modCount++;}/*** 在非空節點succ前插入節點值e*/void linkBefore(E e, Node<E> succ) {final Node<E> pred = succ.prev;// 構建新節點final Node<E> newNode = new Node<>(pred, e, succ);// 設置newNode為succ的前節點succ.prev = newNode;// 如果succ.prev為null，即succ為首節點，則將newNode設置為首節點if (pred == null)first = newNode;else // 如果succ不是首節點pred.next = newNode;size++;modCount++;}/*** 刪除首結點，返回存儲的元素，內部使用*/private E unlinkFirst(Node<E> f) {// 獲取首結點存儲的元素final E element = f.item;// 獲取首結點的后繼結點final Node<E> next = f.next;// 刪除首結點f.item = null;f.next = null; // 便于垃圾回收// 首結點后繼結點設為首結點first = next;// 如果原來首結點的后繼結點為空，則尾結點設為null// 否則，原來首結點的后繼結點的前驅結點設為nullif (next == null)last = null;elsenext.prev = null;size--;modCount++;// 返回原來首結點存儲的元素return element;}/*** 刪除尾結點，返回存儲的元素，內部使用*/private E unlinkLast(Node<E> l) {// 獲取尾結點存儲的元素final E element = l.item;// 獲取尾結點的前驅結點final Node<E> prev = l.prev;// 刪除尾結點l.item = null;l.prev = null; // help GC// 原來尾結點的前驅結點設為尾結點last = prev;// 如果原來尾結點的前驅結點為空，則首結點設為null// 否則，原來尾結點的前驅結點的后繼結點設為nullif (prev == null)first = null;elseprev.next = null;size--;modCount++;// 返回原來尾結點存儲的元素return element;}/*** 刪除指定非空結點，返回存儲的元素*/E unlink(Node<E> x) {// 獲取指定非空結點存儲的元素final E element = x.item;// 獲取指定非空結點的后繼結點final Node<E> next = x.next;// 獲取指定非空結點的前驅結點final Node<E> prev = x.prev;/*** 如果指定非空結點的前驅結點為空，則指定非空結點的后繼結點設為首結點 * 否則，指定非空結點的后繼結點設為指定非空結點的前驅結點的后繼結點，* 指定非空結點的前驅結點設為null*/if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}/*** 如果指定非空結點的后繼結點為空，則指定非空結點的前驅結點設為尾結點 * 否則，指定非空結點的前驅結點設為指定非空結點的后繼結點的前驅結點，* 指定非空結點的后繼結點設為null*/if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}// 指定非空結點存儲的元素設為nullx.item = null;size--;modCount++;// 返回指定非空結點存儲的元素return element;}/*** 獲取首結點存儲的元素* * @return 首結點存儲的元素* @throws NoSuchElementException* 如果鏈表為空*/public E getFirst() {// 獲取首結點引用final Node<E> f = first;// 如果首結點為空，則拋出無該元素異常if (f == null)throw new NoSuchElementException();// 返回首結點存儲的元素return f.item;}/*** 獲取尾結點存儲的元素* * @return 尾結點存儲的元素* @throws NoSuchElementException* 如果鏈表為空*/public E getLast() {// 獲取尾結點引用final Node<E> l = last;// 如果尾結點為空，則拋出無該元素異常if (l == null)throw new NoSuchElementException();// 返回尾結點存儲的元素return l.item;}/*** 刪除首結點，返回存儲的元素* * @return 首結點存儲的元素* @throws NoSuchElementException* 如果鏈表為空*/public E removeFirst() {// 獲取首結點引用final Node<E> f = first;// 如果首結點為空，則拋出無該元素異常if (f == null)throw new NoSuchElementException();// 刪除首結點，返回存儲的元素return unlinkFirst(f);}/*** 刪除尾結點，返回存儲的元素* * @return 尾結點存儲的元素* @throws NoSuchElementException* 如果鏈表為空*/public E removeLast() {// 獲取尾結點引用final Node<E> l = last;// 如果尾結點為空，則拋出無該元素異常if (l == null)throw new NoSuchElementException();// 刪除尾結點，返回存儲的元素return unlinkLast(l);}/*** 頭部插入指定元素* * @param e* 要添加的元素*/public void addFirst(E e) {// 通過頭插法來插入指定元素linkFirst(e);}/*** 尾部插入指定元素，該方法等價于add()* * @param e* the element to add*/public void addLast(E e) {linkLast(e);}/*** 判斷是否包含指定元素* * @param o* 判斷鏈表是否包含的元素* @return {@code true} 如果鏈表包含指定的元素*/public boolean contains(Object o) {// 返回指定元素的索引位置，不存在就返回-1，然后比較返回bool值return indexOf(o) != -1;}/*** 獲取元素數量* * @return 元素數量*/public int size() {return size;}/*** 插入指定元素，返回操作結果,默認添加到末尾作為最后一個元素* * @param e* 要添加到此鏈表中的元素* @return {@code true} (as specified by {@link Collection#add})*/public boolean add(E e) {// 通過尾插法來插入指定元素linkLast(e);return true;}/*** 刪除指定元素，默認從first節點開始，刪除第一次出現的那個元素* * @param o* 要從該列表中刪除的元素（如果存在）* @return {@code true} 如果這個列表包含指定的元素*/public boolean remove(Object o) {// 會根據是否為null分開處理。若值不是null，會用到對象的equals()方法if (o == null) {// 遍歷鏈表，查找到指定元素后刪除該結點，返回truefor (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}// 查找失敗return false;}/*** 將集合插入到鏈表尾部* * @param c* 包含要添加到此鏈表中的元素的集合* @return {@code true} 如果該鏈表因添加而改變* @throws NullPointerException* 如果指定的集合是空的*/public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}/*** 將集合從指定位置開始插入* * @param index* 在哪個索引處前插入指定集合中的第一個元素* @param c* 包含要添加到此鏈表中的元素的集合* @return {@code true} 如果該鏈表因添加而改變* @throws IndexOutOfBoundsException* {@inheritDoc}* @throws NullPointerException* 如果指定的集合是空的*/public boolean addAll(int index, Collection<? extends E> c) {// 檢查索引是否正確（0<=index<=size）checkPositionIndex(index);// 得到元素數組Object[] a = c.toArray();// 得到元素個數int numNew = a.length;// 沒有元素，返回falseif (numNew == 0)return false;// succ指向當前需要插入節點的位置，pred指向其前一個節點Node<E> pred, succ;// 末尾開始添加，當前節點后一個節點為null，前一個節點為尾節點if (index == size) {succ = null;pred = last;} else { //當前位置的節點為指定位置的節點，前一個節點為要添加的節點的前一個節點succ = node(index);pred = succ.prev;}// 遍歷數組并添加到列表中for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;// “封裝”一個新節點Node<E> newNode = new Node<>(pred, e, null);// 原鏈表為null，新插入的節點作為鏈表首節點if (pred == null)first = newNode;elsepred.next = newNode; // 存在前節點，前節點向后指向新加的節點pred = newNode; // pred指針向后移動}// 從最后開始添加，則新節點成為尾節點if (succ == null) {last = pred;} else {pred.next = succ; // 新節點向后指向之前得到的后續第一個節點succ.prev = pred; // 后續的第一個節點也應改為向前指向最后一個添加的節點}size += numNew;modCount++;return true;}/*** 刪除所有元素*/public void clear() {// 遍歷鏈表，刪除所有結點,方便gc回收垃圾for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x.prev = null;x = next;}// 首尾結點置空first = last = null;// 元素數量置0size = 0;modCount++;}// 位置訪問操作/*** 獲取指定位置的元素* * @param index* 要返回的元素的索引* @return 該鏈表中指定位置的元素* @throws IndexOutOfBoundsException* {@inheritDoc}*/public E get(int index) {// 判斷指定位置是否合法checkElementIndex(index);// 返回指定位置的元素return node(index).item;}/*** 修改指定位置的元素，返回之前元素* * @param index* 要替換的元素的索引* @param element* 要存儲在指定位置的元素* @return 之前在指定位置的元素* @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;}/*** 在指定位置前插入指定元素* 頭插法* @param index* 指定元素將被插入的索引* @param element* 要插入的元素* @throws IndexOutOfBoundsException* {@inheritDoc}*/public void add(int index, E element) {// 判斷指定位置是否合法checkPositionIndex(index);// 如果指定位置在尾部，則通過尾插法來插入指定元素if (index == size)linkLast(element);else // 如果指定位置不是尾部，則添加到指定位置前linkBefore(element, node(index));}/*** 刪除指定位置的元素，返回之前元素* * @param index* 要刪除的元素的索引* @return 之前在指定位置的元素* @throws IndexOutOfBoundsException* {@inheritDoc}*/public E remove(int index) {// 判斷指定位置是否合法checkElementIndex(index);// 刪除指定位置的結點，返回之前元素return unlink(node(index));}/*** 判斷指定位置是否合法*/private boolean isElementIndex(int index) {return index >= 0 && index < size;}/*** 判斷迭代器遍歷時或插入元素時指定位置是否合法*/private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}/*** 獲取越界異常信息*/private String outOfBoundsMsg(int index) {return "Index: " + index + ", Size: " + size;}/*** 判斷指定位置是否合法* * @param index*/private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 判斷指定位置是否合法* * @param index*/private void checkPositionIndex(int index) {if (!isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/*** 獲取指定下標的結點*/Node<E> node(int 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;}}// 查詢操作/*** 獲取首次出現指定元素的位置 -1表示不存在* 同樣是根據是否為null進行區分* @param o* 要查找的元素* @return the index of the first occurrence of the specified element in* this list, or -1 if this list does not contain the element*/public int indexOf(Object o) {int index = 0;if (o == null) {// 遍歷鏈表，順序查找指定元素for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}/*** 獲取逆序下首次出現指定元素的位置 -1表示不存在* * @param o* 要查找的元素* @return the index of the last occurrence of the specified element in this* list, or -1 if this list does not contain the element*/public int lastIndexOf(Object o) {int index = size;if (o == null) {// 遍歷鏈表，逆序查找指定元素for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;}// 隊列操作/*** 出隊（從前端），獲得第一個元素，不存在會返回null，不會刪除元素（節點） 獲取首元素* * @return the head of this list, or {@code null} 如果鏈表為空* @since 1.5*/public E peek() {final Node<E> f = first;// 如果首結點為空，則返回null// 否則，返回首結點存儲的元素return (f == null) ? null : f.item;}/*** 出隊（從前端），不刪除元素，若為null會拋出異常而不是返回null 獲取首元素* * @return the head of this list* @throws NoSuchElementException* 如果鏈表為空* @since 1.5*/public E element() {// 返回首結點存儲的元素return getFirst();}/*** 出隊（從前端），如果不存在會返回null，存在的話會返回值并移除這個元素（節點） 獲取并刪除首元素* * @return the head of this list, or {@code null} 如果鏈表為空* @since 1.5*/public E poll() {// 獲取首結點引用final Node<E> f = first;// 如果首結點為空，則返回null// 否則，刪除首結點，返回首結點存儲的元素return (f == null) ? null : unlinkFirst(f);}/*** 出隊（從前端），如果不存在會拋出異常而不是返回null，存在的話會返回值并移除這個元素（節點） 獲取并刪除首元素* * @return the head of this list* @throws NoSuchElementException* 如果鏈表為空* @since 1.5*/public E remove() {// 刪除首結點，返回首結點存儲的元素return removeFirst();}/*** 入隊（從后端），始終返回true* * 鏈表不會溢出* @param e* the element to add* @return {@code true} (as specified by {@link Queue#offer})* @since 1.5*/public boolean offer(E e) {// 通過尾插法插入指定元素，返回操作結果return add(e);}// 雙端隊列操作/*** 入隊（從前端），始終返回true* * @param e* 要插入的元素* @return {@code true} (as specified by {@link Deque#offerFirst})* @since 1.6*/public boolean offerFirst(E e) {// 通過頭插法來插入指定元素addFirst(e);return true;}/*** 入隊（從后端），始終返回true* * @param e* 要插入的元素* @return {@code true} (as specified by {@link Deque#offerLast})* @since 1.6*/public boolean offerLast(E e) {// 通過尾插法來插入指定元素addLast(e);return true;}/*** 出隊（從前端），獲得第一個元素，不存在會返回null，不會刪除元素（節點）* * @return the first element of this list, or {@code null} 如果鏈表為空* @since 1.6*/public E peekFirst() {// 獲取首結點引用final Node<E> f = first;// 如果首結點為空，則返回null// 否則，返回首結點存儲的元素return (f == null) ? null : f.item;}/*** 出隊（從后端），獲得最后一個元素，不存在會返回null，不會刪除元素（節點）* * @return the last element of this list, or {@code null} 如果鏈表為空* @since 1.6*/public E peekLast() {// 獲取尾結點引用final Node<E> l = last;// 如果尾結點為空，則返回null// 否則，返回尾結點存儲的元素return (l == null) ? null : l.item;}/*** 出隊（從前端），獲得第一個元素，不存在會返回null，會刪除元素（節點）* * @return the first element of this list, or {@code null} if this list is* empty* @since 1.6*/public E pollFirst() {// 獲取首結點引用final Node<E> f = first;// 如果首結點為空，則返回null// 否則，刪除首結點，返回首結點存儲的元素return (f == null) ? null : unlinkFirst(f);}/*** 出隊（從后端），獲得最后一個元素，不存在會返回null，會刪除元素（節點）* * @return the last element of this list, or {@code null} if this list is* empty* @since 1.6*/public E pollLast() {// 獲取尾結點引用final Node<E> l = last;// 如果尾結點為空，則返回null// 否則，刪除尾結點，返回尾結點存儲的元素return (l == null) ? null : unlinkLast(l);}/*** 入棧，從前面添加* * @param e* the element to push* @since 1.6*/public void push(E e) {// 通過頭插法來插入指定元素addFirst(e);}/*** 出棧，返回棧頂元素，從前面移除（會刪除）* * @return the element at the front of this list (which is the top of the* stack represented by this list)* @throws NoSuchElementException* 如果鏈表為空* @since 1.6*/public E pop() {// 刪除首結點，返回首結點存儲的元素return removeFirst();}/*** 刪除順序下首次出現的指定元素，返回操作結果* * @param o* 要從該列表中刪除的元素（如果存在）* @return {@code true} 如果鏈表包含指定的元素* @since 1.6*/public boolean removeFirstOccurrence(Object o) {// 刪除順序下首次出現的指定元素對應的結點，返回操作結果return remove(o);}/*** 刪除逆序下首次出現的指定元素，返回操作結果* * @param o* 要從該列表中刪除的元素（如果存在）* @return {@code true} 如果鏈表包含指定的元素* @since 1.6*/public boolean removeLastOccurrence(Object o) {// 由于LinkedList中允許存放null，因此下面通過兩種情況來分別處理if (o == null) {// 遍歷鏈表，從尾結點開始查找指定元素// 如果查找成功，刪除該結點，返回truefor (Node<E> x = last; x != null; x = x.prev) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = last; x != null; x = x.prev) {if (o.equals(x.item)) {unlink(x);return true;}}}// 查找失敗return false;}/*** Returns a list-iterator of the elements in this list (in proper* sequence), starting at the specified position in the list. Obeys the* general contract of {@code List.listIterator(int)}.* <p>* <p>* The list-iterator is <i>fail-fast</i>: if the list is structurally* modified at any time after the Iterator is created, in any way except* through the list-iterator's own {@code remove} or {@code add} methods,* the list-iterator will throw a {@code 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.* * @param index* index of the first element to be returned from the* list-iterator (by a call to {@code next})* @return a ListIterator of the elements in this list (in proper sequence),* starting at the specified position in the list* @throws IndexOutOfBoundsException* {@inheritDoc}* @see List#listIterator(int)*/public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public boolean hasNext() {return nextIndex < size;}public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}public boolean hasPrevious() {return nextIndex > 0;}public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();lastReturned = next = (next == null) ? last : next.prev;nextIndex--;return lastReturned.item;}public int nextIndex() {return nextIndex;}public int previousIndex() {return nextIndex - 1;}public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;}public void set(E e) {if (lastReturned == null)throw new IllegalStateException();checkForComodification();lastReturned.item = e;}public void add(E e) {checkForComodification();lastReturned = null;if (next == null)linkLast(e);elselinkBefore(e, next);nextIndex++;expectedModCount++;}public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);lastReturned = next;next = next.next;nextIndex++;}checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}/*** 節點的數據結構，包含前后節點的引用和當前節點* * @param <E>*/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;}}/*** 返回迭代器* * @since 1.6*/public Iterator<E> descendingIterator() {return new DescendingIterator();}/*** 因為采用鏈表實現，所以迭代器很簡單*/private class DescendingIterator implements Iterator<E> {private final ListItr itr = new ListItr(size());public boolean hasNext() {return itr.hasPrevious();}public E next() {return itr.previous();}public void remove() {itr.remove();}}/*** 父類克隆方法*/@SuppressWarnings("unchecked")private LinkedList<E> superClone() {try {return (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}}/*** 克隆，淺拷貝* * 淺拷貝時，若存儲的是對象的引用，拷貝時，對象本身的改變將表現到副本中，而深拷貝不會。* @return a shallow copy of this {@code LinkedList} instance*/public Object clone() {LinkedList<E> clone = superClone();// 鏈表初始化clone.first = clone.last = null;clone.size = 0;clone.modCount = 0;// 插入結點for (Node<E> x = first; x != null; x = x.next)clone.add(x.item);// 返回克隆后的對象引用return clone;}/*** 返回新的數組，數組含有列表中所有元素*/public Object[] toArray() {Object[] result = new Object[size];int i = 0;for (Node<E> x = first; x != null; x = x.next)result[i++] = x.item;return result;}/*** Returns an array containing all of the elements in this list in proper* sequence (from first to last element); the runtime type of the returned* array is that of the specified array. If the list fits in the specified* array, it is returned therein. Otherwise, a new array is allocated with* the runtime type of the specified array and the size of this list.* <p>* <p>* If the list fits in the specified array with room to spare (i.e., the* array has more elements than the list), the element in the array* immediately following the end of the list is set to {@code null}. (This* is useful in determining the length of the list <i>only</i> if the* caller knows that the list does not contain any null elements.)* <p>* <p>* Like the {@link #toArray()} method, this method acts as bridge between* array-based and collection-based APIs. Further, this method allows* precise control over the runtime type of the output array, and may, under* certain circumstances, be used to save allocation costs.* <p>* <p>* Suppose {@code x} is a list known to contain only strings. The following* code can be used to dump the list into a newly allocated array of* {@code String}:* <p>* * <pre>* String[] y = x.toArray(new String[0]);* </pre>* * <p>* Note that {@code toArray(new Object[0])} is identical in function to* {@code toArray()}.* * @param a* the array into which the elements of the list are to be* stored, if it is big enough; otherwise, a new array of the* same runtime type is allocated for this purpose.* @return an array containing the elements of the list* @throws ArrayStoreException* if the runtime type of the specified array is not a supertype* of the runtime type of every element in this list* @throws NullPointerException* if the specified array is null*/@SuppressWarnings("unchecked")public <T> T[] toArray(T[] a) {if (a.length < size)a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);int i = 0;Object[] result = a;for (Node<E> x = first; x != null; x = x.next)result[i++] = x.item;if (a.length > size)a[size] = null;return a;}private static final long serialVersionUID = 876323262645176354L;/*** 序列化*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// 默認序列化s.defaultWriteObject();// 寫入元素數量s.writeInt(size);// 遍歷鏈表，寫入所有元素for (Node<E> x = first; x != null; x = x.next)s.writeObject(x.item);}/*** 反序列化*/@SuppressWarnings("unchecked")private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// 默認反序列化s.defaultReadObject();// 讀取元素數量int size = s.readInt();// 遍歷鏈表，讀取所有元素并尾部插入for (int i = 0; i < size; i++)linkLast((E) s.readObject());}/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* list.* <p>* <p>* The {@code Spliterator} reports {@link Spliterator#SIZED} and* {@link Spliterator#ORDERED}. Overriding implementations should document* the reporting of additional characteristic values.* * @return a {@code Spliterator} over the elements in this list* @implNote The {@code Spliterator} additionally reports* {@link Spliterator#SUBSIZED} and implements {@code trySplit} to* permit limited parallelism..* @since 1.8*/@Overridepublic Spliterator<E> spliterator() {return new LLSpliterator<E>(this, -1, 0);}/*** A customized variant of Spliterators.IteratorSpliterator*/static final class LLSpliterator<E> implements Spliterator<E> {static final int BATCH_UNIT = 1 << 10; // batch array size incrementstatic final int MAX_BATCH = 1 << 25; // max batch array size;final LinkedList<E> list; // null OK unless traversedNode<E> current; // current node; null until initializedint est; // size estimate; -1 until first neededint expectedModCount; // initialized when est setint batch; // batch size for splitsLLSpliterator(LinkedList<E> list, int est, int expectedModCount) {this.list = list;this.est = est;this.expectedModCount = expectedModCount;}final int getEst() {int s; // force initializationfinal LinkedList<E> lst;if ((s = est) < 0) {if ((lst = list) == null)s = est = 0;else {expectedModCount = lst.modCount;current = lst.first;s = est = lst.size;}}return s;}public long estimateSize() {return (long) getEst();}public Spliterator<E> trySplit() {Node<E> p;int s = getEst();if (s > 1 && (p = current) != null) {int n = batch + BATCH_UNIT;if (n > s)n = s;if (n > MAX_BATCH)n = MAX_BATCH;Object[] a = new Object[n];int j = 0;do {a[j++] = p.item;} while ((p = p.next) != null && j < n);current = p;batch = j;est = s - j;return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);}return null;}public void forEachRemaining(Consumer<? super E> action) {Node<E> p;int n;if (action == null) throw new NullPointerException();if ((n = getEst()) > 0 && (p = current) != null) {current = null;est = 0;do {E e = p.item;p = p.next;action.accept(e);} while (p != null && --n > 0);}if (list.modCount != expectedModCount)throw new ConcurrentModificationException();}public boolean tryAdvance(Consumer<? super E> action) {Node<E> p;if (action == null) throw new NullPointerException();if (getEst() > 0 && (p = current) != null) {--est;E e = p.item;current = p.next;action.accept(e);if (list.modCount != expectedModCount)throw new ConcurrentModificationException();return true;}return false;}public int characteristics() {return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;}}}?
-概述)
-信息論基礎)
-tar,find,grep,xargs)