java之LinkList、ListIterator、ArrayList學習

1：LinkedList學習

  LinkedList類是連結清單節點各種操作的實作，LinkedList類實作了一個帶有頭尾引用的通用型雙向連結清單。

注意，此實作不是同步的。如果多個線程同時通路清單，而其中至少一個線程從結構上修改了該清單，則它必須 保持外部同步。（結構修改指添加或删除一個或多個元素的任何操作；僅設定元素的值不是結構修改。）這一般通過對自然封裝該清單的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法來“包裝”該清單。最好在建立時完成這一操作，以防止對清單進行意外的不同步通路，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));

此類的 iterator 和 listIterator 方法傳回的疊代器是快速失敗 的：在疊代器建立之後，如果從結構上對清單進行修改，除非通過疊代器自身的 remove 或 add 方法，其他任何時間任何方式的修改，疊代器都将抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不冒将來不确定的時間任意發生不确定行為的風險。

注意，疊代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發修改時，不可能作出任何硬性保證。快速失敗疊代器盡最大努力抛出 ConcurrentModificationException。是以，編寫依賴于此異常的程式的方式是錯誤的，正确做法是：疊代器的快速失敗行為應該僅用于檢測程式錯誤。

 常見函數

ListIterator<E> listIterator() 
          傳回清單中元素的清單疊代器（以正确的順序）。 
 ListIterator<E> listIterator(int index) 
          傳回清單中元素的清單疊代器（以正确的順序），從清單的指定位置開始。      

boolean removeAll(Collection<?> c) 
          從清單中移除指定 collection 中包含的所有元素（可選操作）。 從表中删除所有屬于c的元素，如果成功删除就傳回true，如果c為空，則抛出NullPointerException
 boolean retainAll(Collection<?> c) 
          僅在清單中保留指定 collection 中所包含的元素（可選操作）。 從表中删除所有不屬于c的元素，如果成功删除就傳回true，如果c為空，則抛出NullPointerException      

List<E> subList(int fromIndex, int toIndex) 
          傳回清單中指定的 fromIndex（包括 ）和 toIndex（不包括）之間的部分視圖。 傳回從formIndex到toIndex-1位置之間的所有元素      

Object[] toArray() 
          傳回以正确順序包含清單中的所有元素的數組。 
<T> T[] 
 toArray(T[] a) 
          傳回以正确順序包含清單中所有元素的數組；傳回數組的運作時類型是指定數組的運作時類型。      

LinkedList是一個雙向連結清單，并且有頭節點和尾節點，從下面方法中可以看出：

void addFirst(E o) 
          将給定元素插入此清單的開頭。 
 void addLast(E o) 
          将給定元素追加到此清單的結尾。      

E getFirst() 
          傳回此清單的第一個元素。 
 E getLast() 
          傳回此清單的最後一個元素。      

E removeFirst() 
          移除并傳回此清單的第一個元素。 
 E removeLast() 
          移除并傳回此清單的最後一個元素。      

Object[] toArray() 
          以正确順序傳回包含此清單中所有元素的數組。 
<T> T[]  toArray(T[] a) 
          以正确順序傳回包含此清單中所有元素的數組；傳回數組的運作時類型即為指定數組的類型。      

2：ListIterator學習

public interface ListIterator<E>

extends

​​Iterator​​<E>

系清單疊代器，允許程式員按任一方向周遊清單、疊代期間修改清單，并獲得疊代器在清單中的目前位置。ListIterator 沒有目前元素；它的光标位置 始終位于調用 previous() 所傳回的元素和調用 next() 所傳回的元素之間。在長度為 n 的清單中，有 n+1 個有效的索引值，從 0 到 n（包含）。

Element(0) Element(1) Element(2) ... Element(n)

^ ^ ^ ^ ^

Index: 0 1 2 3 n+1

注意，​​remove()​​​ 和 ​​set(Object)​​ 方法不是 根據光标位置定義的；它們是根據對調用 ​​next()​​​ 或 ​​previous()​​ 所傳回的最後一個元素的操作定義的。

void add(E o) 
          将指定的元素插入清單（可選操作）。 
 boolean hasNext() 
          以正向周遊清單時，如果清單疊代器有多個元素，則傳回 true（換句話說，如果 next 傳回一個元素而不是抛出異常，則傳回 true）。 
 boolean hasPrevious() 
          如果以反向周遊清單，清單疊代器有多個元素，則傳回 true。 
 E next() 
          傳回清單中的下一個元素。 
 int nextIndex() 
          傳回對 next 的後續調用所傳回元素的索引。 
 E previous() 
          傳回清單中的前一個元素。 
 int previousIndex() 
          傳回對 previous 的後續調用所傳回元素的索引。 
 void remove() 
          從清單中移除由 next 或 previous 傳回的最後一個元素（可選操作）。 
 void set(E o) 
          用指定元素替換 next 或 previous 傳回的最後一個元素（可選操作）。      

3：ArrayList

     是連結清單的數組實作，在實際應用中它和Vector是等價的，除了Vector類的方法是同步的，而ArrayList類則不是。與向量相似的是，數組連結清單也是一個靈活的數組，在插入操作需要時可以自動伸展。

public class ArrayList<E>

extends

​​AbstractList​​​<E>

implements

​​​List​​​<E>,

​​​RandomAccess​​​,

​​​Cloneable​​​,

​​​Serializable​​

List 接口的大小可變數組的實作。實作了所有可選清單操作，并允許包括 null 在内的所有元素。除了實作 List 接口外，此類還提供一些方法來操作内部用來存儲清單的數組的大小。（此類大緻上等同于 Vector

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時間運作。add 操作以分攤的固定時間 運作，也就是說，添加 n 個元素需要 O(n) 時間。其他所有操作都以線性時間運作（大體上講）。與用于 LinkedList

每個 ArrayList 執行個體都有一個容量。該容量是指用來存儲清單元素的數組的大小。它總是至少等于清單的大小。随着向 ArrayList 中不斷添加元素，其容量也自動增長。并未指定增長政策的細節，因為這不隻是添加元素會帶來分攤固定時間開銷那樣簡單。

在添加大量元素前，應用程式可以使用 ensureCapacity 操作來增加 ArrayList

注意，此實作不是同步的。如果多個線程同時通路一個 ArrayList 執行個體，而其中至少一個線程從結構上修改了清單，那麼它必須 保持外部同步。（結構上的修改是指任何添加或删除一個或多個元素的操作，或者顯式調整底層數組的大小；僅僅設定元素的值不是結構上的修改。）這一般通過對自然封裝該清單的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList

List list = Collections.synchronizedList(new ArrayList(...));

此類的 iterator 和 listIterator 方法傳回的疊代器是快速失敗的：在建立疊代器之後，除非通過疊代器自身的 remove 或 add 方法從結構上對清單進行修改，否則在任何時間以任何方式對清單進行修改，疊代器都會抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險。

注意，疊代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗疊代器會盡最大努力抛出 ConcurrentModificationException。是以，為提高這類疊代器的正确性而編寫一個依賴于此異常的程式是錯誤的做法：疊代器的快速失敗行為應該僅用于檢測 bug。

void ensureCapacity(int minCapacity) 
          如有必要，增加此 ArrayList 執行個體的容量，以確定它至少能夠容納最小容量參數所指定的元素數。      

protected  void removeRange(int fromIndex, int toIndex) 
          移除清單中索引在 fromIndex（包括）和 toIndex（不包括）之間的所有元素      

Object[] toArray() 
          傳回一個按照正确的順序包含此清單中所有元素的數組。 
<T> T[] 
 toArray(T[] a) 
          傳回一個按照正确的順序包含此清單中所有元素的數組；傳回數組的運作時類型就是指定數組的運作時類型。 
 void trimToSize() 
          将此 ArrayList 執行個體的容量調整為清單的目前大小。