Java Collection Framework List課件

1、Java Collection Framework : List摘要：List 是 Java Collection Framework的重要成員，具體包括List接口及其所有的實(shí)現(xiàn)類。由于List接口繼承了Collection接口，所以List擁有Collection的所有操作。同時(shí)，又因?yàn)長(zhǎng)ist是列表類型，所以List本身還提供了一些適合自身的方法。ArrayList 是一個(gè)動(dòng)態(tài)數(shù)組，實(shí)現(xiàn)了數(shù)組動(dòng)態(tài)擴(kuò)容，隨機(jī)訪問效率高；LinkedList是一個(gè)雙向鏈表，隨機(jī)插入和刪除效率高，可用作隊(duì)列的實(shí)現(xiàn)。一. 要點(diǎn)List 基礎(chǔ)特性與框架ArrayList ：動(dòng)態(tài)數(shù)組LinkedList ： 雙向循

2、環(huán)鏈表二. List 基礎(chǔ)特性與框架1、List 特色操作List 包括 List接口 以及 List接口的所有實(shí)現(xiàn)類（ArrayList, LinkedList, Vector，Stack）, 其中 Vector 和 Stack 已過時(shí)。因?yàn)?List 接口實(shí)現(xiàn)了 Collection 接口(如代碼 1 所示)，所以 List 接口擁有 Collection 接口提供的所有常用方法，同時(shí)，又因?yàn)?List 是列表類型，所以 List 接口還提供了一些適合于自身的常用方法，如表1所示。/ 代碼 1public interface List extends Collection . 特別地，對(duì)于

3、List而言：AbstractList 給出了 iterator() 方法的通用實(shí)現(xiàn)，其中的 next() 和 remove() 方法底層分別由 get(int index) 和 remove(int index) 方法實(shí)現(xiàn)；對(duì)于 subList 方法， 原list 和 子list 做的 非結(jié)構(gòu)性修改(不涉及到list的大小改變的修改)，都會(huì)影響到彼此; 對(duì)于結(jié)構(gòu)性修改: 若發(fā)生結(jié)構(gòu)性修改的是返回的子list，那么原list的大小也會(huì)發(fā)生變化(modCount與expectedModCount同時(shí)變化，不會(huì)觸發(fā)Fast-Fail機(jī)制) ; 而若發(fā)生結(jié)構(gòu)性修改的是原list（不包括由返回的子li

4、st導(dǎo)致的改變），那么判斷式 l.modCount != expectedModCount 將返回 TRUE ,觸發(fā) Fast-Fail 機(jī)制，拋出 ConcurrentModificationException。因此，若在調(diào)用 sublist 返回了子 list 之后，修改原list的大小，那么之前產(chǎn)生的子list將會(huì)失效；刪除一個(gè)list的某個(gè)區(qū)段: list.subList(from, to).clear(); 2、List 結(jié)構(gòu)下面我們對(duì) List 結(jié)構(gòu)圖中所涉及到的類加以介紹：AbstractList 是一個(gè)抽象類，它實(shí)現(xiàn)List接口并繼承于 AbstractCollection 。

5、對(duì)于“按順序遍歷訪問元素”的需求，使用List的Iterator 即可以做到，抽象類AbstractList提供該實(shí)現(xiàn)；而訪問特定位置的元素（也即按索引訪問）、元素的增加和刪除涉及到了List中各個(gè)元素的連接關(guān)系，并沒有在AbstractList中提供實(shí)現(xiàn)（List 的類型不同，其實(shí)現(xiàn)方式也隨之不同，所以將具體實(shí)現(xiàn)放到子類）；AbstractSequentialList 是一個(gè)抽象類，它繼承于 AbstractList。AbstractSequentialList 通過 ListIterator 實(shí)現(xiàn)了“鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)”。此外，ArrayList 通過 Syst

6、em.arraycopy(完成元素的挪動(dòng)) 實(shí)現(xiàn)了“順序表中，根據(jù)index索引值操作順序表的全部函數(shù)”；ArrayList, LinkedList, Vector, Stack 是 List 的 4 個(gè)實(shí)現(xiàn)類；ArrayList 是一個(gè)動(dòng)態(tài)數(shù)組。它由數(shù)組實(shí)現(xiàn)，隨機(jī)訪問效率高，隨機(jī)插入、隨機(jī)刪除效率低；LinkedList 是一個(gè)雙向鏈表（順序表）。LinkedList 隨機(jī)訪問效率低，但隨機(jī)插入、隨機(jī)刪除效率高，?？梢员划?dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作；Vector 是矢量隊(duì)列，和ArrayList一樣，它也是一個(gè)動(dòng)態(tài)數(shù)組，由數(shù)組實(shí)現(xiàn)。但ArrayList是非線程安全的，而Vector是線程

7、安全的；Stack 是棧，它繼承于Vector。它的特性是：先進(jìn)后出(FILO, First In Last Out).3、List 特性：Java 中的 List 是對(duì)數(shù)組的有效擴(kuò)展，它是這樣一種結(jié)構(gòu)：如果不使用泛型，它可以容納任何類型的元素，如果使用泛型，那么它只能容納泛型指定的類型的元素。和數(shù)組（數(shù)組不支持泛型）相比，List 的容量是可以動(dòng)態(tài)擴(kuò)展的；List 中的元素是“有序”的。這里的“有序”，并不是排序的意思，而是說我們可以對(duì)某個(gè)元素在集合中的位置進(jìn)行指定，包括對(duì)列表中每個(gè)元素的插入位置進(jìn)行精確地控制、根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素和搜索列表中的元素；List 中的元

8、素是可以重復(fù)的，因?yàn)槠錇橛行虻臄?shù)據(jù)結(jié)構(gòu)；List中常用的集合對(duì)象包括：ArrayList、Vector和LinkedList，其中前兩者是基于數(shù)組來進(jìn)行存儲(chǔ)，后者是基于鏈表進(jìn)行存儲(chǔ)。其中Vector是線程安全的，其余兩個(gè)不是線程安全的；List中是可以包括 null 的，即使使用了泛型；List 接口提供了特殊的迭代器，稱為 ListIterator，除了允許 Iterator 接口提供的正常操作外，該迭代器還允許元素插入和替換，以及雙向訪問。三. ArrayList1、ArrayList 基礎(chǔ)ArrayList 實(shí)現(xiàn)了 List 中所有可選操作，并允許包括 NULL 在內(nèi)的所有元素。除了實(shí)現(xiàn)

9、 List 接口外，此類還提供一些方法來操作其支撐數(shù)組的大小。ArrayList 是基于數(shù)組實(shí)現(xiàn)的，是一個(gè)動(dòng)態(tài)數(shù)組，其容量能自動(dòng)增長(zhǎng)，并且用 size 屬性來標(biāo)識(shí)該容器里的元素個(gè)數(shù)，而非這個(gè)被包裝數(shù)組的大小。每個(gè) ArrayList 實(shí)例都有一個(gè)容量，該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小,并且它總是至少等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動(dòng)增長(zhǎng)。自動(dòng)增長(zhǎng)會(huì)帶來數(shù)據(jù)向新數(shù)組的重新拷貝。因此，如果可預(yù)知數(shù)據(jù)量的多少，可在構(gòu)造ArrayList時(shí)指定其容量。在添加大量元素前，應(yīng)用程序也可以使用 ensureCapacity 操作來增加 ArrayList 實(shí)例的容

10、量，這可以減少遞增式再分配的數(shù)量。注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè) ArrayList 實(shí)例，而其中至少一個(gè)線程從結(jié)構(gòu)上修改(結(jié)構(gòu)上的修改是指任何添加或刪除一個(gè)或多個(gè)元素的操作，或者顯式調(diào)整底層數(shù)組的大??；僅僅設(shè)置元素的值不是結(jié)構(gòu)上的修改.)了列表，那么它必須保持外部同步。ArrayList 實(shí)現(xiàn)了 Serializable 接口，因此它支持序列化，能夠通過序列化傳輸。閱讀源碼可以發(fā)現(xiàn)，ArrayList內(nèi)置的數(shù)組用 transient 關(guān)鍵字修飾，以示其不會(huì)被序列化。當(dāng)然，ArrayList的元素最終還是會(huì)被序列化的，在序列化/反序列化時(shí)，會(huì)調(diào)用 ArrayList 的 wr

11、iteObject()/readObject() 方法，將該 ArrayList中的元素（即0size-1下標(biāo)對(duì)應(yīng)的元素） 和 容量大小 寫入流/從流讀出。這樣做的好處是，只保存/傳輸有實(shí)際意義的元素，最大限度的節(jié)約了存儲(chǔ)、傳輸和處理的開銷。ArrayList 實(shí)現(xiàn)了 RandomAccess 接口， 支持快速隨機(jī)訪問，實(shí)際上就是通過下標(biāo)序號(hào)進(jìn)行快速訪問(于是否支持get(index)訪問不同)。RandomAccess 接口是 List 實(shí)現(xiàn)所使用的標(biāo)記接口，用來表明其支持快速（通常是固定時(shí)間）隨機(jī)訪問。此接口的主要目的是允許一般的算法更改其行為，從而在將其應(yīng)用到隨機(jī)或連續(xù)訪問列表時(shí)能提供良

12、好的性能。特別地，在對(duì)List的遍歷算法中，要盡量來判斷是屬于 RandomAccess(如ArrayList) 還是 SequenceAccess(如LinkedList），因?yàn)檫m合RandomAccess List的遍歷算法，用在SequenceAccess List上就差別很大，即對(duì)于實(shí)現(xiàn)了RandomAccess接口的類實(shí)例而言，此循環(huán) for (int i=0, ilist.size(); i+) list.get(i);的運(yùn)行速度要快于以下循環(huán)： for (Iterator i=list.iterator(); i.hasNext(); ) i.next();所以，我們?cè)诒闅vLis

13、t之前，可以用 if( list instanceof RamdomAccess ) 來判斷一下，選擇用哪種遍歷方式。ArrayList 實(shí)現(xiàn)了Cloneable接口，能被克隆。Cloneable 接口里面沒有任何方法，只是起一個(gè)標(biāo)記作用，表明當(dāng)一個(gè)類實(shí)現(xiàn)了該接口時(shí)，該類可以通過調(diào)用clone()方法來克隆該類的實(shí)例。ArrayList不是線程安全的，只能用在單線程環(huán)境下，多線程環(huán)境下可以考慮用 Collections.synchronizedList(List l) 函數(shù)返回一個(gè)線程安全的ArrayList類，也可以使用 concurrent 并發(fā)包下的 CopyOnWriteArrayLi

14、st 類。2、ArrayList在JDK中的定義我們可以從 ArrayList 的源碼看到，其包括 兩個(gè)域 和 三個(gè)構(gòu)造函數(shù) , 源碼如下：private transient Object elementData ： 支撐數(shù)組private int size ： 元素個(gè)數(shù)public ArrayList(int initialCapacity) ： 給定初始容量的構(gòu)造函數(shù)；public ArrayList() ： Java Collection Framework 規(guī)范-默認(rèn)無參的構(gòu)造函數(shù) (初始容量指定為10)；public ArrayList(Collectionc) ： Java Col

15、lection Framework 規(guī)范-參數(shù)為指定容器的構(gòu)造函數(shù)public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable private static final long serialVersionUID = 8683452581122892189L; /* * The array buffer into which the elements of the ArrayList are stored.（ArrayList 支撐數(shù)組） *

16、The capacity of the ArrayList is the length of this array buffer.（ArrayList 容量的定義） */ private transient Object elementData; / 瞬時(shí)域 /* * The size of the ArrayList (the number of elements it contains).（ArrayList 大小的定義） */ private int size; /* * Constructs an empty list with the specified initial capaci

17、ty */ public ArrayList(int initialCapacity) / 給定初始容量的構(gòu)造函數(shù) super(); if (initialCapacity 0) throw new IllegalArgumentException(Illegal Capacity: + initialCapacity); this.elementData = new ObjectinitialCapacity; / 泛型與數(shù)組不兼容 /* * Constructs an empty list with an initial capacity of ten. */ public ArrayLi

18、st() / Java Collection Framework 規(guī)范：默認(rèn)無參的構(gòu)造函數(shù) this(10); /* * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collections * iterator. */ public ArrayList(Collection c) / Java Collection Framework 規(guī)范：參數(shù)為指定容器的構(gòu)造函數(shù) elementData = c.toArray();

19、 size = elementData.length; / c.toArray might (incorrectly) not return Object (see 6260652) if (elementData.getClass() != Object.class) elementData = Arrays.copyOf(elementData, size, Object.class); 3、ArrayList 基本操作的保證邊界檢查（即檢查 ArrayList 的 Size）：涉及到 index 的操作/ 邊界檢查private void RangeCheck(int index) if

20、 (index = size) throw new IndexOutOfBoundsException( Index: +index+, Size: +size); 調(diào)整數(shù)組容量（增加容量）：向 ArrayList 中增加元素/ 調(diào)整數(shù)組容量 public void ensureCapacity(int minCapacity) modCount+; int oldCapacity = elementData.length; if (minCapacity oldCapacity) Object oldData = elementData; int newCapacity = (oldCapa

21、city * 3)/2 + 1; if (newCapacity minCapacity) newCapacity = minCapacity; / minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); 向 ArrayList 中增加元素時(shí)，都要去檢查添加后元素的個(gè)數(shù)是否會(huì)超出當(dāng)前數(shù)組的長(zhǎng)度。如果超出，ArrayList 將會(huì)進(jìn)行擴(kuò)容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴(kuò)容通過一個(gè) public 方法 ensureCapacity(in

22、t minCapacity) 來實(shí)現(xiàn) : 在實(shí)際添加大量元素前，我也可以使用 ensureCapacity 來手動(dòng)增加 ArrayList 實(shí)例的容量，以減少遞增式再分配的數(shù)量。 ArrayList 進(jìn)行擴(kuò)容時(shí)，會(huì)將老數(shù)組中的元素重新拷貝一份到新的數(shù)組中，每次數(shù)組容量的增長(zhǎng)為其原容量的 1.5 倍 + 1。這種操作的代價(jià)是很高的，因此在實(shí)際使用時(shí)，我們應(yīng)該盡量避免數(shù)組容量的擴(kuò)張。當(dāng)我們可預(yù)知要保存的元素的多少時(shí)，要在構(gòu)造ArrayList實(shí)例時(shí)，就指定其容量，以避免數(shù)組擴(kuò)容的發(fā)生?；蛘吒鶕?jù)實(shí)際需求，通過調(diào)用 ensureCapacity 方法來手動(dòng)增加ArrayList實(shí)例的容量。在 ensu

23、reCapacity 的源代碼中有這樣一段代碼：Object oldData = elementData; /為什么要用到oldData乍一看，后面并沒有用到oldData，這句話顯得多此一舉！但是這牽涉到了一個(gè)內(nèi)存管理的問題. 而且，為什么這一句還在 if 的內(nèi)部? 這是跟 elementData = Arrays.copyOf(elementData, newCapacity); 這句是有關(guān)系的，在下面這句 Arrays.copyOf 的實(shí)現(xiàn)時(shí)，新創(chuàng)建了 newCapacity 大小的內(nèi)存，然后把老的 elementData 放入。這樣，由于舊的內(nèi)存的引用是elementData， 而 e

24、lementData 指向了新的內(nèi)存塊，如果有一個(gè)局部變量 oldData 變量引用舊的內(nèi)存塊的話，在copy的過程中就會(huì)比較安全，因?yàn)檫@樣證明這塊老的內(nèi)存依然有引用，分配內(nèi)存的時(shí)候就不會(huì)被侵占掉。然后，在copy完成后，這個(gè)局部變量的生命周期也過去了，此時(shí)釋放才是安全的。否則的話，在 copy 的時(shí)候萬(wàn)一新的內(nèi)存或其他線程的分配內(nèi)存侵占了這塊老的內(nèi)存，而 copy 還沒有結(jié)束，這將是個(gè)嚴(yán)重的事情。調(diào)整數(shù)組容量（減少容量）：將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小在使用 ArrayList 過程中，由于 elementData 的長(zhǎng)度會(huì)被拓展，所以經(jīng)常會(huì)出現(xiàn) size 很小但 ele

25、mentData.length 很大的情況，造成空間的浪費(fèi)。 ArrayList 通過 trimToSize 方法返回一個(gè)新的數(shù)組給 elementData ，其中：元素內(nèi)容保持不變，length 和size 相同。public void trimToSize() modCount+; int oldCapacity = elementData.length; if (size oldCapacity) elementData = Arrays.copyOf(elementData, size); Fail-Fast機(jī)制動(dòng)機(jī)： 在 Java Collection 中，為了防止在某個(gè)線程在對(duì) C

26、ollection 進(jìn)行迭代時(shí)，其他線程對(duì)該 Collection 進(jìn)行結(jié)構(gòu)上的修改。換句話說，迭代器的快速失敗行為僅用于檢測(cè)代碼的 bug。 本質(zhì)： Fail-Fast 是 Java 集合的一種錯(cuò)誤檢測(cè)機(jī)制。 作用場(chǎng)景： 在使用迭代器時(shí)，Collection 的結(jié)構(gòu)發(fā)生變化，拋出 ConcurrentModificationException 。當(dāng)然，這并不能說明 Collection對(duì)象 已經(jīng)被不同線程并發(fā)修改，因?yàn)槿绻麊尉€程違反了規(guī)則，同樣也有會(huì)拋出該異常。 當(dāng)多個(gè)線程對(duì)集合進(jìn)行結(jié)構(gòu)上的改變的操作時(shí)，有可能會(huì)產(chǎn)生fail-fast機(jī)制。例如：假設(shè)存在兩個(gè)線程（線程1、線程2），線程1通過

27、Iterator在遍歷集合A中的元素，在某個(gè)時(shí)候線程2修改了集合A的結(jié)構(gòu)（是結(jié)構(gòu)上面的修改，而不是簡(jiǎn)單的修改集合元素的內(nèi)容），那么這個(gè)時(shí)候程序就會(huì)觸發(fā)fail-fast機(jī)制，拋出 ConcurrentModificationException 異常。在面對(duì)并發(fā)的修改時(shí)，迭代器很快就會(huì)完全失敗，而不是冒著在將來某個(gè)不確定時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)。 我們知道 fail-fast 產(chǎn)生的原因就在于：程序在對(duì) collection 進(jìn)行迭代時(shí)，某個(gè)線程對(duì)該 collection 在結(jié)構(gòu)上對(duì)其做了修改。要想進(jìn)一步了解 fail-fast 機(jī)制，我們首先要對(duì) ConcurrentModificatio

28、nException 異常有所了解。當(dāng)方法檢測(cè)到對(duì)象的并發(fā)修改，但不允許這種修改時(shí)就拋出該異常。同時(shí)需要注意的是，該異常不會(huì)始終指出對(duì)象已經(jīng)由不同線程并發(fā)修改，如果單線程違反了規(guī)則，同樣也有可能會(huì)拋出改異常。誠(chéng)然，迭代器的快速失敗行為無法得到保證，它不能保證一定會(huì)出現(xiàn)該錯(cuò)誤，但是快速失敗操作會(huì)盡最大努力拋出 ConcurrentModificationException 異常，所以，為提高此類操作的正確性而編寫一個(gè)依賴于此異常的程序是錯(cuò)誤的做法，正確做法是：ConcurrentModificationException 應(yīng)該僅用于檢測(cè) bug。 下面我們以 ArrayList 為例進(jìn)一步分析

29、fail-fast 產(chǎn)生的原因:private class Itr implements Iterator int cursor; int lastRet = -1; int expectedModCount = ArrayList.this.modCount; public boolean hasNext() return (this.cursor != ArrayList.this.size); public E next() checkForComodification(); /* 省略此處代碼 */ public void remove() if (this.lastRet 0) th

30、row new IllegalStateException(); checkForComodification(); /* 省略此處代碼 */ final void checkForComodification() if (ArrayList.this.modCount = this.expectedModCount) return; throw new ConcurrentModificationException(); 從上面的源代碼我們可以看出，迭代器在調(diào)用 next() 、 remove() 方法時(shí)都是調(diào)用 checkForComodification() 方法，該方法用于判斷 “mo

31、dCount = expectedModCount”：若不等，觸發(fā) fail-fast 機(jī)制，拋出 ConcurrentModificationException 異常。所以，要弄清楚為什么會(huì)產(chǎn)生 fail-fast 機(jī)制，我們就必須要弄明白 “modCount != expectedModCount” 什么時(shí)候發(fā)生，換句話說，他們的值在什么時(shí)候發(fā)生改變的。 expectedModCount 是在 Itr 中定義的：“int expectedModCount = ArrayList.this.modCount;”，所以它的值是不可能會(huì)修改的，所以會(huì)變的就是 modCount。modCount

32、是在 AbstractList 中定義的，為全局變量：protected transient int modCount = 0; 從 ArrayList 源碼中我們可以看出，我們直接或間接的通過 RemoveRange 、 trimToSize 和 ensureCapcity（add，remove，clear） 三個(gè)方法完成對(duì) ArrayList 結(jié)構(gòu)上的修改,所以 ArrayList 實(shí)例每當(dāng)調(diào)用一次上面的方法，modCount 的值就遞增一次。所以,我們這里可以判斷:由于expectedModCount 的值與 modCount 的改變不同步，導(dǎo)致兩者之間不等，從而觸發(fā)fail-fast機(jī)

33、制。我們可以考慮如下場(chǎng)景： 有兩個(gè)線程（線程A，線程B），其中線程A負(fù)責(zé)遍歷list、線程B修改list。線程A在遍歷list過程的某個(gè)時(shí)候（此時(shí)expectedModCount = modCount=N），線程啟動(dòng)，同時(shí)線程B增加一個(gè)元素，這是modCount的值發(fā)生改變（modCount + 1 = N + 1）。線程A繼續(xù)遍歷執(zhí)行next方法時(shí)，通告checkForComodification方法發(fā)現(xiàn)expectedModCount = N ，而modCount = N + 1，兩者不等，這時(shí)觸發(fā) fail-fast機(jī)制。3、元素的增、改、刪、查元素的增和改ArrayList 提供了 s

34、et(int index, E element) 用于修改元素，提供 add(E e)、add(int index, E element)、addAll(Collection c)、addAll(int index, Collection c) 這些方法用于添加元素。 / 用指定的元素替代此列表中指定位置上的元素，并返回以前位于該位置上的元素 public E set(int index, E element) RangeCheck(index); E oldValue = (E) elementDataindex; elementDataindex = element; return old

35、Value; / 將指定的元素添加到此列表的尾部public boolean add(E e) ensureCapacity(size + 1); elementDatasize+ = e; return true; / 將指定的元素插入此列表中的指定位置。 / 如果當(dāng)前位置有元素，則向右移動(dòng)當(dāng)前位于該位置的元素以及所有后續(xù)元素（將其索引加1）。 public void add(int index, E element) if (index size | index 0) throw new IndexOutOfBoundsException(Index: +index+, Size: +si

36、ze); / 如果數(shù)組長(zhǎng)度不足，將進(jìn)行擴(kuò)容。 ensureCapacity(size+1); / Increments modCount! / 將 elementData中從Index位置開始、長(zhǎng)度為size-index的元素， / 拷貝到從下標(biāo)為index+1位置開始的新的elementData數(shù)組中。 / 即將當(dāng)前位于該位置的元素以及所有后續(xù)元素右移一個(gè)位置。 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementDataindex = element; size+; / 按照指

37、定collection的迭代器所返回的元素順序，將該collection中的所有元素添加到此列表的尾部。 public boolean addAll(Collection c) Object a = c.toArray(); int numNew = a.length; ensureCapacity(size + numNew); / Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; / 從指定的位置開始，將指定collection

38、中的所有元素插入到此列表中。 public boolean addAll(int index, Collection c) if (index size | index 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; 元素的讀取 / 返回此列表中指定位置上的元素。 public E get(int index)

39、 RangeCheck(index); return (E) elementDataindex; 元素的刪除ArrayList 共有 根據(jù)下標(biāo)或者指定對(duì)象兩種方式的刪除功能。romove(int index): 首先是檢查范圍，修改modCount，保留將要被移除的元素，將移除位置之后的元素向前挪動(dòng)一個(gè)位置，將list末尾元素置空（null），返回被移除的元素。/ 移除此列表中指定位置上的元素 public E remove(int index) RangeCheck(index); modCount+; E oldValue = (E) elementDataindex; int numMo

40、ved = size - index - 1; if (numMoved 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData-size = null; / Let gc do its work return oldValue; remove(Object o)：/ 移除此列表中 “首次” 出現(xiàn)的指定元素（如果存在）。這是因?yàn)?ArrayList 中允許存放重復(fù)的元素。 public boolean remove(Object o) / 由于ArrayList中允許存放null，

41、因此下面通過兩種情況來分別處理。 if (o = null) for (int index = 0; index size; index+) if (elementDataindex = null) / 類似remove(int index)，移除列表中指定位置上的元素。 fastRemove(index); return true; else for (int index = 0; index 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData-size = null; /

42、Let gc do its work 4、小結(jié)關(guān)于ArrayList的源碼，總結(jié)如下：三個(gè)不同的構(gòu)造方法。無參構(gòu)造方法構(gòu)造的ArrayList的容量默認(rèn)為10； 帶有Collection參數(shù)的構(gòu)造方法的實(shí)現(xiàn)是將Collection轉(zhuǎn)化為數(shù)組賦給ArrayList的實(shí)現(xiàn)數(shù)組elementData。 擴(kuò)充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個(gè)，也可能是一組）時(shí)，都要調(diào)用該方法來確保足夠的容量。當(dāng)容量不足以容納當(dāng)前的元素個(gè)數(shù)時(shí)，就設(shè)置新的容量為舊的容量的1.5倍加1，如果設(shè)置后的新容量還不夠，則直接新容量設(shè)置為傳入的參數(shù)（也就是所需的容量）。之后，用 A

43、rrays.copyof() 方法將元素拷貝到新的數(shù)組。從中可以看出，當(dāng)容量不夠時(shí)，每次增加元素，都要將原來的元素拷貝到一個(gè)新的數(shù)組中，非常之耗時(shí)，也因此建議在事先能確定元素?cái)?shù)量的情況下，才使用ArrayList，否則建議使用LinkedList。 ArrayList 的實(shí)現(xiàn)中大量地調(diào)用了Arrays.copyof() 和 System.arraycopy()方法 。我們有必要對(duì)這兩個(gè)方法的實(shí)現(xiàn)做下深入的了解。首先來看Arrays.copyof()方法。它有很多個(gè)重載的方法，但實(shí)現(xiàn)思路都是一樣的，我們來看泛型版本的源碼：public static T copyOf(T original, in

44、t newLength) return (T) copyOf(original, newLength, original.getClass(); 很明顯調(diào)用了另一個(gè) copyof 方法，該方法有三個(gè)參數(shù)，最后一個(gè)參數(shù)指明要轉(zhuǎn)換的數(shù)據(jù)的類型，其源碼如下： /* * param original 源數(shù)組 * param newLength 目標(biāo)數(shù)組的長(zhǎng)度 * param newType 目標(biāo)數(shù)組的類型 */public static T copyOf(U original, int newLength, Class newType) T copy = (Object)newType = (Obje

45、ct)Object.class) ? (T) new ObjectnewLength : (T) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(inal, 0, copy, 0, Math.min(original.length, newLength); return copy;這里可以很明顯地看出，該方法實(shí)際上是在其內(nèi)部又創(chuàng)建了一個(gè)長(zhǎng)度為newlength的數(shù)組，調(diào)用System.arraycopy()方法，將原來數(shù)組中的元素復(fù)制到了新的數(shù)組中。 下面來看 System.arraycopy

46、() 方法。該方法被標(biāo)記了native，調(diào)用了系統(tǒng)的C/C+代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。該函數(shù)實(shí)際上最終調(diào)用了C語(yǔ)言的memmove()函數(shù)，因此它可以保證同一個(gè)數(shù)組內(nèi)元素的正確復(fù)制和移動(dòng)，比一般的復(fù)制方法的實(shí)現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強(qiáng)烈推薦在復(fù)制大量數(shù)組元素時(shí)用該方法，以取得更高的效率； ArrayList 基于數(shù)組實(shí)現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素，因此 查找效率高，但每次插入或刪除元素，就要大量地移動(dòng)元素，插入刪除元素的效率低； 在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理

47、，ArrayList中允許元素為null。四. LinkedList 1、LinkedList 簡(jiǎn)介L(zhǎng)inkedList 是 List接口的雙向循環(huán)鏈表實(shí)現(xiàn)。LinkedList 實(shí)現(xiàn)了 List 中所有可選操作，并且允許所有元素（包括 null）。除了實(shí)現(xiàn) List 接口外，LinkedList 為在列表的開頭及結(jié)尾進(jìn)行獲取(get)、刪除(remove)和插入(insert)元素提供了統(tǒng)一的訪問操作，而這些操作允許LinkedList 作為Stack(棧)、Queue(隊(duì)列)或Deque(雙端隊(duì)列：double-ended queue)進(jìn)行使用。 注意，LinkedList 不是同步的。如

48、果多個(gè)線程同時(shí)訪問一個(gè)順序表，而其中至少一個(gè)線程從結(jié)構(gòu)上（結(jié)構(gòu)修改指添加或刪除一個(gè)或多個(gè)元素的任何操作；僅設(shè)置元素的值不是結(jié)構(gòu)修改。）修改了該列表，則它必須保持外部同步。這一般通過對(duì)自然封裝該列表的對(duì)象進(jìn)行同步操作來完成。如果不存在這樣的對(duì)象，則應(yīng)該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在創(chuàng)建時(shí)完成這一操作，以防止對(duì)列表進(jìn)行意外的不同步訪問，如下所示： List list = Collections.synchronizedList(new LinkedList(.);LinkedList 的 iterator 和 listIterator 方法返回的迭代器是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對(duì)列表進(jìn)行修改，除非通過迭代器自身的 remove 或 add 方法，其他任何時(shí)間任何方式的修改，都將導(dǎo)致ConcurrentModificationException。因此，面對(duì)并發(fā)的修改，迭代器很快就會(huì)完全失敗，而不冒將來不確定的時(shí)間任意發(fā)生不確定行為的風(fēng)險(xiǎn)。 LinkedList 在Java中的定義如下：public class LinkedList extends AbstractSequentialList implements List, Deque, Clone