一 概覽
List 接口的繼承結(jié)構(gòu)如圖所示苟穆，其中的 RandomAccess 接口沒(méi)有聲明任何方法亭畜，只是作為標(biāo)記揉燃。同樣類似的還有Serializable和Cloneable接口窿撬，RandomAccess的注釋如下
public interface **RandomAccess**
Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.
The best algorithms for manipulating random access lists (such as ArrayList ) can produce quadratic behavior when applied to sequential access lists (such as LinkedList ). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.
It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
runs faster than this loop:
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
This interface is a member of the [Java Collections Framework ][2].
可知，當(dāng)數(shù)據(jù)量很大時(shí)對(duì)于聲明了 RandomAccess 接口的類使用數(shù)組比使用 iterator 遍歷速度更快咒彤，因此疆柔，一個(gè)常見(jiàn)的用法是，遍歷大數(shù)據(jù)量的list時(shí)要作一個(gè)判斷：
if (list instance of RandomAccess)
{
for(int m = 0; m < list.size(); m++){
}
} else {
Iterator iter = list.iterator();
while(iter.hasNext()){}
}
二 ArrayList篇
trimToSize蔼紧，由于 ArrayList 每次增長(zhǎng)會(huì)預(yù)申請(qǐng)多一點(diǎn)空間婆硬，這樣就會(huì)出現(xiàn)當(dāng) size() = 1000 的時(shí)候， ArrayList 已經(jīng)申請(qǐng)了 1200 空間的情況奸例，trimToSize 的作用則是去掉預(yù)留元素位置，就是刪除多余的 200 向楼，改為只申請(qǐng) 1000, 內(nèi)存緊張的時(shí)候會(huì)用到
System.arraycopy( elementData , 0 , a , 0 , size ) 和Arrays.copyof的區(qū)別在于Arrays.copyof會(huì)多拷貝一份查吊。System.arraycopy為什么快
fastRemove，少了rangecheck湖蜕，比普通的remove速度更快
retainAll 和 removeAll 分別調(diào)用 batchRemove(c ,true ) 和 batchRemove(c ,false ) ;
toArray(): 對(duì)該方法返回的數(shù)組逻卖，進(jìn)行操作（增刪改查）都不會(huì)影響源數(shù)據(jù)（ ArrayList 中 elementData ）。二者之間是不會(huì)相互影響的昭抒。
subList(): 對(duì)返回的子集合评也，進(jìn)行操作（增刪改查）都會(huì)影響父集合炼杖。而且若是對(duì)父集合中進(jìn)行刪除操作（僅僅在刪除子集合的首個(gè)元素）時(shí)，會(huì)拋出異常
modCount盗迟，用來(lái)記錄 ArrayList 結(jié)構(gòu)發(fā)生變化的次數(shù)坤邪，如果一個(gè)動(dòng)作前后 modCount 的值不相等，說(shuō)明 ArrayList 被其它線程修改了罚缕，如果在創(chuàng)建迭代器之后的任何時(shí)候以任何方式修改了列表（增加艇纺、刪除、修改）邮弹，除了通過(guò)迭代器自己的 remove 或 add 方法黔衡，迭代器將拋出 ConcurrentModificationException 異常，需要注意的是：這里異常的拋出條件是檢測(cè)到 modCount != expectedmodCount 腌乡，如果并發(fā)場(chǎng)景下一個(gè)線程修改了 modCount 值時(shí)另一個(gè)線程又 " 及時(shí)地 " 修改了 expectedmodCount 值盟劫，則異常不會(huì)拋出。所以不能依賴于這個(gè)異常來(lái)檢測(cè)程序的正確性与纽±谈撸【這個(gè)變量對(duì)于實(shí)現(xiàn)Iterator功能的非線程安全集合都適用，也就是說(shuō)同樣適用于HashMap渣锦，而線程安全的CopyOnWriteArrayList和ConcurrentHashMap都不用modCount機(jī)制】
public E next() {
this.checkForComodification();
...
}
final void checkForComodification() {
if(ArrayList.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
public boolean hasNext() {
return this.cursor != ArrayList.this.size;
}
如果刪除的是 list 里倒數(shù)第二個(gè)值硝岗，這樣觸發(fā) hasNext() 的時(shí)候結(jié)果正好為 false 退出循環(huán)不繼續(xù)執(zhí)行 next() 也就不會(huì)報(bào)錯(cuò)
ArrayList list = new ArrayList() {{
add("a");
add("b");
add("c");
}};
for (String string:list){
if (string.equals("a")) { //這里若把a(bǔ)改成b則不會(huì)報(bào)錯(cuò)
list.remove(string);
}
}
System.out.println(list);
Iterable只是返回了Iterator接口的一個(gè)實(shí)例，這里很是奇怪袋毙，為什么不把兩個(gè)接口合二為一型檀，直接在Iterable里面定義hasNext(),next()等方法呢？原因是實(shí)現(xiàn)了Iterable的類可以在實(shí)現(xiàn)多個(gè)Iterator內(nèi)部類听盖，例如LinkedList中的ListItr和DescendingIterator兩個(gè)內(nèi)部類胀溺，就分別實(shí)現(xiàn)了雙向遍歷和逆序遍歷。Java中Iterable和Iterator接口
Iterator皆看，ListIterator以及Spliterator
實(shí)現(xiàn) Spliterator仓坞，然后用 StreamSupport 就可以構(gòu)造一個(gè) Stream 了，相當(dāng)方便腰吟。對(duì)于 Spliterator 接口的設(shè)計(jì)思想无埃，應(yīng)該要提到的是 Java7 的 Fork/Join( 分支 / 合并 ) 框架，總得來(lái)說(shuō)就是用遞歸的方式把并行的任務(wù)拆分成更小的子任務(wù)毛雇，然后把每個(gè)子任務(wù)的結(jié)果合并起來(lái)生成整體結(jié)果嫉称。JDK8源碼之Spliterator并行遍歷迭代器
Normally, an application developer would not consume the Spliterator API directly. But if you are providing an API, and implement your own collection-like class, you can implement Spliterator to adapt your collection to the Stream API. This supports a functional approach, parallel processing, and other features.
For example, I wrote a utility to enumerate IP addresses in a network, specified by CIDR notation. It's not really a collection; that is, it doesn't carry list of all of the addresses in memory at once, only the network number and netmask. But by exposing a Spliterator , it can be easily adapted to a Stream . (Each Spliterator just tracks the current IP address and maximum address in its share of the network.)
Another example from the core Java runtime is [DirectoryStream for traversing the file system. ][13]
Methods of Iterator:
* hasNext()
* next()
* remove()
Methods of ListIterator:
* add(E e)
* hasNext()
* hasPrevious()
* next()
* nextIndex()
* previous()
* previousIndex()
* remove()
* set(E e)
Methods of Spliterator:
* tryAdvance(Consumer<? super E> action) //就是順序處理每個(gè)元素，類似 Iterator 灵疮，如果還有元素要處理织阅，則返回 true ，否則返回 false
* forEachRemaining(Consumer<? super T> action)
* trySplit() //為 Spliterator 專門(mén)設(shè)計(jì)的方法震捣，區(qū)分與普通的 Iterator 荔棉，該方法會(huì)把當(dāng)前元素劃分一部分出去創(chuàng)建一個(gè)新的 Spliterator 作為返回闹炉，兩個(gè) Spliterator 變會(huì)并行執(zhí)行，如果元素個(gè)數(shù)小到無(wú)法劃分則返回 null
* estimateSize() //用于估算還剩下多少個(gè)元素需要遍歷
* characteristics() //表示該 Spliterator 有哪些特性润樱，用于可以更好控制和優(yōu)化 Spliterator 的使用
- 什么時(shí)候應(yīng)該使用 List list = new ArrayList() 替代 ArrayList list = new ArrayList() 渣触？
When you write:
List < String > list = new ArrayList < String >();
Then you are sure you'll use only the functionality of the *interface* [List ][8].
( ArrayList implements List , so List is more flexibl). Using this, allows you to change the ArrayList to other types in the future (like LinkedList ..).
- ArrayList 初始化方式
//普通
ArrayList<String> list = new ArrayList<String>();
list.add("A");
list.add("B");
list.add("C");
//雙括號(hào)法
ArrayList<String> list = new ArrayList<String>() {{
add("A");
add("B");
add("C");
}}
//java7提供了Arrays.asList，但是通過(guò) asList 返回的 List 祥国，一定不能進(jìn)行 add 操作昵观，否則會(huì)拋出異常
List<String> places = Arrays.asList("Buenos Aires", "Córdoba", "La Plata");
//轉(zhuǎn)型為ArrayList就沒(méi)有問(wèn)題
ArrayList<String> places = new ArrayList<>(Arrays.asList("Buenos Aires", "Córdoba", "La Plata"));
//如果只有一個(gè)元素
List<Long> idList = Collections.singletonList(1001);
//guava框架
List<String> places = ImmutableList.of("Buenos Aires", "Córdoba", "La Plata");
//自定義工廠方法
public static ArrayList<String> createArrayList(String ... elements) {
ArrayList<String> list = new ArrayList<String>();
for (String element : elements) {
list.add(element);
}
return list;
}
....
ArrayList<String> places = createArrayList("S?o Paulo", "Rio de Janeiro", "Brasília");
//創(chuàng)建n個(gè)相同的副本
ArrayList<Object> list = new ArrayList<Object>(Collections.nCopies(1000, new Object()));
//stream風(fēng)格
List<String> strings = Stream.of("foo", "bar", "baz").collect(toList());
- 線程安全
List是非線程安全的，但只有在發(fā)生resize的時(shí)候才可能觸發(fā)不安全的操作舌稀，因此啊犬，如果你的List初始容量足夠大，是可以進(jìn)行多線程操作的壁查，當(dāng)然觉至，并發(fā)的場(chǎng)合還是推薦使用并發(fā)容器CopyOnWriteList
三 LinkedList篇
和ArrayList的一大區(qū)別在于沒(méi)有實(shí)現(xiàn)RandomAccess接口，另外ArrayList 里是實(shí)現(xiàn)了 Iterator 類睡腿，然后用ListIterator擴(kuò)展了Iterator類语御，而LinkedList里是只實(shí)現(xiàn)了ListIterator類，通過(guò)接口窄化間接實(shí)現(xiàn)Iterator功能席怪，最后应闯，LinkedList 的實(shí)現(xiàn)是基于Deque的，所以它可以窄化實(shí)現(xiàn)為Stack和Queue挂捻。
四 vector 篇
就是把ArrayList所有public方法加上synchronized
五 stack 篇
就是擴(kuò)展了vector 碉纺，增加了push，pop刻撒，peep方法
