java零基礎(chǔ)入門-高級(jí)特性篇(二)? List集合
前面講解過(guò)集合框架的大致結(jié)構(gòu)，本章詳細(xì)介紹List這個(gè)接口以及List接口的三個(gè)實(shí)現(xiàn)，ArrayList，LinkedList和Vector。
既然ArrayList和LinkedList實(shí)現(xiàn)了List接口，那么我們首先看看List接口中有哪些方法是常用的，再來(lái)看看這兩個(gè)實(shí)現(xiàn)類是怎么實(shí)現(xiàn)這些常用方法的。
List接口常用方法
這里的E是泛型，這個(gè)東西后面再說(shuō)，先可以理解為任何一個(gè)類型，比如學(xué)生類，車輛類等等。集合里面只能放引用類型，所以不要將基礎(chǔ)類型放進(jìn)集合。
add（E e）// 可以暫時(shí)理解成 add（Student stu），下面也一樣，這個(gè)是添加方法，將元素添加進(jìn)集合，默認(rèn)往集合尾部添加。
add (int index,E element)，根據(jù)指定的位置添加元素，比如我現(xiàn)在List里面有2個(gè)元素了，下標(biāo)是0，1，但是我要新增一個(gè)放在中間，就是add（1，stu）這樣就可以將元素插入到指定位置。
get (int index) 根據(jù)指定位置獲取元素，我要第二個(gè)元素，get（1）可以獲取到。
set（int index，E element），set是替換，add可以理解成插隊(duì)，你插進(jìn)去了，后面的人往后移，而set就是請(qǐng)托排隊(duì)，你來(lái)了，托就走了，一手交錢，一手交位，你代替了他的位置，托不會(huì)站在你后面繼續(xù)排隊(duì)。
remove(int index)，根據(jù)指定位置刪除元素。
這是List接口里面常用的方法，下面來(lái)看看兩個(gè)實(shí)現(xiàn)類如何來(lái)實(shí)現(xiàn)這些方法。
ArrayList：Array 是數(shù)組，ArrayList顧名思義，就是跟數(shù)組特性類似的List實(shí)現(xiàn)。
LinkedList：Linked 是鏈表，LinkedList顧名思義，就是有鏈表特性的List實(shí)現(xiàn)。
我們?cè)诮o類起名字的時(shí)候，也最好做到顧名思義，這樣讓人一目了然，你設(shè)計(jì)的類是做什么的。
ArrayList
上面說(shuō)ArrayList跟數(shù)組的特性類似，原因就是ArrayList的底層就是使用數(shù)組來(lái)實(shí)現(xiàn)的。數(shù)組不是長(zhǎng)度固定嗎？ArrayList就實(shí)現(xiàn)了可變長(zhǎng)的數(shù)組，下面來(lái)看看ArrayList是如何實(shí)現(xiàn)可變長(zhǎng)數(shù)組的。
add（E e），首先新增一個(gè)長(zhǎng)度加一的數(shù)組，然后復(fù)制原數(shù)組的內(nèi)容到新數(shù)組，然后將add進(jìn)來(lái)的元素添加到最后。
add (int index,E element)，將元素 element放到集合里位置為index的地方。1新建長(zhǎng)度加一數(shù)組，2原數(shù)組復(fù)制到新數(shù)組，3將原數(shù)組復(fù)制到新數(shù)組 ，4從插入位置到最后往后移一位 ，5將新元素覆蓋到index位置。
get和set不改變數(shù)組長(zhǎng)度，直接使用數(shù)組的下標(biāo)來(lái)實(shí)現(xiàn)操作，比如get方法，底層其實(shí)就是數(shù)組的獲取元素方法：array[index]，而set也是類似，直接在數(shù)組中進(jìn)行賦值： array[index] = element。
remove操作與add的操作類似，只是做了一個(gè)反向操作，新增數(shù)組和元素右移變成了新增數(shù)組和元素左移。
由于ArrayList底層使用數(shù)組實(shí)現(xiàn)，所以可以直接使用下標(biāo)（索引）來(lái)查找元素，使得ArrayList的查詢效率非常高，get方法只是對(duì)數(shù)組的方法做了一個(gè)簡(jiǎn)單的封裝，沒(méi)有多余的操作。而正是由于數(shù)組實(shí)現(xiàn)的底層，數(shù)組長(zhǎng)度不可變，導(dǎo)致每次新增和刪除元素使ArrayList長(zhǎng)度發(fā)生變化的時(shí)候，都需要進(jìn)行數(shù)組的復(fù)制操作，這樣使計(jì)算資源的消耗變大，導(dǎo)致效率較低。
簡(jiǎn)單來(lái)說(shuō)ArrayList的特點(diǎn)就是查詢快，增刪慢。這里的慢是相對(duì)的，如果在增刪較少的場(chǎng)景使用，是完全可以的。
在工作中會(huì)大量的使用到List集合，但是大部分時(shí)候都是無(wú)腦使用ArrayList來(lái)做實(shí)現(xiàn)，如果在性能要求較高并且頻繁的對(duì)List進(jìn)行增刪元素的場(chǎng)景使用ArrayList，會(huì)使效率降低。那么這種頻繁增刪元素的場(chǎng)景該使用什么樣的List呢？噔噔噔~噔~有請(qǐng)LinkedList出場(chǎng)。
LinkedList
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，有很多種形式，LinkedList是使用雙向鏈表實(shí)現(xiàn)的，那么雙向鏈表是個(gè)啥？
當(dāng)我們站在一起排成一行的時(shí)候，就像軍訓(xùn)的時(shí)候那樣，每一行的同學(xué)只能知道你的左邊和右邊是誰(shuí)，并不知道你左邊的左邊或者右邊的右邊是誰(shuí)。這種只知道左右，不知道其他的數(shù)據(jù)結(jié)構(gòu)就是雙向鏈表。
雙向鏈表結(jié)構(gòu)中的每一個(gè)元素不僅僅包含了數(shù)據(jù)，還記錄了上一個(gè)元素的地址和下一個(gè)元素的地址，所以每個(gè)元素只知道相鄰的元素的位置，對(duì)于集合中的其他元素則是一概不知。
再來(lái)看一下LinkedList如何新增元素。
這個(gè)過(guò)程非?？焖伲挥脧?fù)制什么數(shù)組，雙向鏈表知道第一個(gè)元素和最后一個(gè)元素的地址，來(lái)了一個(gè)新元素，將新元素的頭部指向前一個(gè)元素的值，前一個(gè)元素的尾部指向新元素的值，這樣就完成了添加。
同理刪除元素也非?？欤恍枰薷那昂笤氐念^尾部指向的元素即可。
這里要提示一下，LinkedList不僅僅實(shí)現(xiàn)了List的接口，還實(shí)現(xiàn)了Deque接口，Deque是隊(duì)列Queue的子接口。翻譯一下，LinkedList不僅僅有List集合在指定下標(biāo)新增刪除元素等功能，還有隊(duì)列集合Queue的在第一個(gè)元素之前添加元素addFirst，在最后一個(gè)元素后添加addLast等方法，充分的運(yùn)用了雙向鏈表知道頭尾地址的優(yōu)勢(shì)。
LinkedList實(shí)現(xiàn)多個(gè)接口，就是我們介紹接口的時(shí)候說(shuō)的，用多個(gè)標(biāo)準(zhǔn)組成一個(gè)新標(biāo)準(zhǔn)，這個(gè)就是實(shí)現(xiàn)多個(gè)接口用法的最好例子。請(qǐng)各位細(xì)細(xì)品味。
總結(jié)一下LinkedList的特點(diǎn)就是增刪快，查詢慢。這里的增刪是指不按下標(biāo)增刪，按照下標(biāo)增刪元素一樣慢。
Vector
Vector這個(gè)集合是個(gè)非常古老的List實(shí)現(xiàn)，早在java1.0的版本的時(shí)候就有了，但是由于早期的方法名稱定義過(guò)于繁瑣等問(wèn)題。經(jīng)過(guò)多年的發(fā)展，ArrayList已經(jīng)可以完全的替代Vector這個(gè)類。這里說(shuō)這個(gè)類，其實(shí)是很多古老的題目和不思進(jìn)取的出題者會(huì)問(wèn) "ArrayList和Vector有什么區(qū)別呀？"，他們希望的答案是“Vector線程安全，ArrayList線程不安全”。其實(shí)ArrayList也可以通過(guò)一些手段達(dá)到線程安全，以后講多線程的時(shí)候，再來(lái)告訴你答案吧。
因?yàn)锳rrayList已經(jīng)可以完全的替代Vector，所以現(xiàn)在版本的java已經(jīng)不再建議使用這個(gè)類，以后你可能只會(huì)在各種題目里面見(jiàn)到他。
復(fù)習(xí)一下前面的知識(shí)
接口定義了標(biāo)準(zhǔn)，這里的List接口定義了添加元素，刪除元素等方法，而實(shí)現(xiàn)類根據(jù)不同的需求，使用不同的實(shí)現(xiàn)方式，比如ArrayList用數(shù)組實(shí)現(xiàn)，查詢快，LinkedList用雙向鏈表實(shí)現(xiàn)，增刪快。如果我們還有其他場(chǎng)景有特殊需求，比如我要查詢快也要增刪快，你甚至可以自己去實(shí)現(xiàn)List接口，然后實(shí)現(xiàn)List的方法即可，這就是使用接口編程的好處。
以下是擴(kuò)展知識(shí)，了解即可。
ArrayList的擴(kuò)容
ArrayList在頻繁做增刪元素的時(shí)候效率會(huì)降低，究其原因就是底層需要判斷新建一個(gè)多長(zhǎng)的新數(shù)組來(lái)存放增長(zhǎng)后的集合，而這個(gè)判斷的過(guò)程比較復(fù)雜，可能會(huì)需要一次，也可能會(huì)需要多次，導(dǎo)致性能下降。
如果我們可以幫助ArrayList進(jìn)行底層數(shù)組的擴(kuò)容，也就是說(shuō)我們成了指揮者，直接告訴他，你給我新建一個(gè)XXX長(zhǎng)度的數(shù)組，而不是讓ArrayList自己去判斷，這樣效率會(huì)得到不小的提升。其實(shí)ArrayList里面也有提供定義數(shù)組容量的方法來(lái)精準(zhǔn)的定義新數(shù)組長(zhǎng)度。有興趣的同學(xué)可以去看看源代碼。
LinkedList下標(biāo)操作的實(shí)現(xiàn)
前面說(shuō)LinkedList的查詢效率比較慢，原因就是雙向鏈表沒(méi)有數(shù)組那種操作下標(biāo)的優(yōu)勢(shì)。LinkedList的get（index）方法實(shí)現(xiàn)，做了以下操作：
1.將要查找的index與集合長(zhǎng)度的一半進(jìn)行對(duì)比
2.如果在index在集合前半段，從第一個(gè)元素開(kāi)始，往后循環(huán)對(duì)比每一個(gè)元素，直到找到index的位置。如果index在集合后半段，則從最后一個(gè)元素開(kāi)始，往前循環(huán)遍歷，直到找到index位置。
你沒(méi)看錯(cuò)，他只能循環(huán)，一個(gè)個(gè)對(duì)比，你說(shuō)能不慢么。不止是get（index），在LinkedList里面任何要使用index的地方，比如add（index，e）都是一個(gè)個(gè)循環(huán)對(duì)比，所以效率都不高。
總結(jié)，如果要操作下標(biāo)，請(qǐng)使用ArrayList~
