List完全解析

一 概覽

image.png

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方法

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末骨田,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子声怔,更是在濱河造成了極大的恐慌态贤,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,123評(píng)論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件醋火,死亡現(xiàn)場(chǎng)離奇詭異悠汽,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)胎撇,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,031評(píng)論 2 384
  • 文/潘曉璐 我一進(jìn)店門(mén)介粘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人晚树,你說(shuō)我怎么就攤上這事⊙挪桑” “怎么了爵憎?”我有些...
    開(kāi)封第一講書(shū)人閱讀 156,723評(píng)論 0 345
  • 文/不壞的土叔 我叫張陵慨亲,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我宝鼓,道長(zhǎng)刑棵,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,357評(píng)論 1 283
  • 正文 為了忘掉前任愚铡,我火速辦了婚禮蛉签,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘沥寥。我一直安慰自己碍舍,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,412評(píng)論 5 384
  • 文/花漫 我一把揭開(kāi)白布邑雅。 她就那樣靜靜地躺著片橡,像睡著了一般。 火紅的嫁衣襯著肌膚如雪淮野。 梳的紋絲不亂的頭發(fā)上捧书,一...
    開(kāi)封第一講書(shū)人閱讀 49,760評(píng)論 1 289
  • 那天,我揣著相機(jī)與錄音骤星,去河邊找鬼经瓷。 笑死,一個(gè)胖子當(dāng)著我的面吹牛洞难,可吹牛的內(nèi)容都是我干的舆吮。 我是一名探鬼主播,決...
    沈念sama閱讀 38,904評(píng)論 3 405
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼廊营,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼歪泳!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起露筒,我...
    開(kāi)封第一講書(shū)人閱讀 37,672評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤呐伞,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后慎式,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體伶氢,經(jīng)...
    沈念sama閱讀 44,118評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,456評(píng)論 2 325
  • 正文 我和宋清朗相戀三年瘪吏,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了癣防。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,599評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡掌眠,死狀恐怖蕾盯,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情蓝丙,我是刑警寧澤级遭,帶...
    沈念sama閱讀 34,264評(píng)論 4 328
  • 正文 年R本政府宣布望拖,位于F島的核電站,受9級(jí)特大地震影響挫鸽,放射性物質(zhì)發(fā)生泄漏说敏。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,857評(píng)論 3 312
  • 文/蒙蒙 一丢郊、第九天 我趴在偏房一處隱蔽的房頂上張望盔沫。 院中可真熱鬧,春花似錦枫匾、人聲如沸架诞。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,731評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)侈贷。三九已至,卻和暖如春等脂,著一層夾襖步出監(jiān)牢的瞬間俏蛮,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,956評(píng)論 1 264
  • 我被黑心中介騙來(lái)泰國(guó)打工上遥, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留搏屑,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,286評(píng)論 2 360
  • 正文 我出身青樓粉楚,卻偏偏與公主長(zhǎng)得像辣恋,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子模软,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,465評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容

  • Java源碼研究之容器(1) 如何看源碼 很多時(shí)候我們看源碼, 看完了以后經(jīng)常也沒(méi)啥收獲, 有些地方看得懂, 有些...
    駱駝騎士閱讀 987評(píng)論 0 22
  • 概要 上一章伟骨,我們學(xué)習(xí)了Collection的架構(gòu)。這一章開(kāi)始燃异,我們對(duì)Collection的具體實(shí)現(xiàn)類進(jìn)行講解携狭;首...
    廢棄的root閱讀 888評(píng)論 0 4
  • Java集合 作為一個(gè)Developer,Java集合類是我們?cè)诠ぷ髦羞\(yùn)用最多的回俐、最頻繁的類逛腿。相比于數(shù)組(Arra...
    賈博巖閱讀 65,301評(píng)論 14 103
  • Collection接口 Collection接口是所有集合的祖先類。他有兩個(gè)構(gòu)造方法仅颇,一個(gè)無(wú)參構(gòu)造单默,一個(gè)是帶Co...
    夜幕繁華閱讀 583評(píng)論 0 0
  • hashmap實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu),數(shù)組忘瓦、桶等搁廓。 如圖所示 JDK 1.7,是以數(shù)組+鏈表組成的,鏈表為相同hash的鍵...
    不需要任何閱讀 820評(píng)論 0 1