java零基礎入門-高級特性篇(二)? List集合
前面講解過集合框架的大致結構，本章詳細介紹List這個接口以及List接口的三個實現，ArrayList，LinkedList和Vector桃笙。
既然ArrayList和LinkedList實現了List接口，那么我們首先看看List接口中有哪些方法是常用的沙绝，再來看看這兩個實現類是怎么實現這些常用方法的搏明。
List接口常用方法
這里的E是泛型，這個東西后面再說闪檬，先可以理解為任何一個類型星著，比如學生類，車輛類等等粗悯。集合里面只能放引用類型虚循，所以不要將基礎類型放進集合。
add（E e）// 可以暫時理解成 add（Student stu）样傍，下面也一樣邮丰，這個是添加方法，將元素添加進集合铭乾，默認往集合尾部添加剪廉。
add (int index,E element)，根據指定的位置添加元素炕檩，比如我現在List里面有2個元素了斗蒋，下標是0，1笛质，但是我要新增一個放在中間泉沾，就是add（1，stu）這樣就可以將元素插入到指定位置妇押。
get (int index) 根據指定位置獲取元素跷究，我要第二個元素，get（1）可以獲取到敲霍。
set（int index俊马，E element），set是替換肩杈，add可以理解成插隊柴我，你插進去了，后面的人往后移扩然，而set就是請托排隊艘儒，你來了，托就走了，一手交錢界睁，一手交位觉增，你代替了他的位置，托不會站在你后面繼續(xù)排隊翻斟。
remove(int index)抑片，根據指定位置刪除元素。
這是List接口里面常用的方法杨赤，下面來看看兩個實現類如何來實現這些方法敞斋。
ArrayList：Array 是數組，ArrayList顧名思義疾牲，就是跟數組特性類似的List實現植捎。
LinkedList：Linked 是鏈表，LinkedList顧名思義阳柔，就是有鏈表特性的List實現焰枢。
我們在給類起名字的時候，也最好做到顧名思義舌剂，這樣讓人一目了然济锄，你設計的類是做什么的。
ArrayList
上面說ArrayList跟數組的特性類似霍转，原因就是ArrayList的底層就是使用數組來實現的荐绝。數組不是長度固定嗎？ArrayList就實現了可變長的數組避消，下面來看看ArrayList是如何實現可變長數組的低滩。
add（E e），首先新增一個長度加一的數組岩喷，然后復制原數組的內容到新數組恕沫，然后將add進來的元素添加到最后。
add (int index,E element)纱意，將元素 element放到集合里位置為index的地方婶溯。1新建長度加一數組，2原數組復制到新數組偷霉，3將原數組復制到新數組 迄委，4從插入位置到最后往后移一位 ，5將新元素覆蓋到index位置腾它。
get和set不改變數組長度跑筝，直接使用數組的下標來實現操作死讹，比如get方法瞒滴，底層其實就是數組的獲取元素方法：array[index]，而set也是類似，直接在數組中進行賦值： array[index] = element妓忍。
remove操作與add的操作類似虏两，只是做了一個反向操作，新增數組和元素右移變成了新增數組和元素左移世剖。
由于ArrayList底層使用數組實現定罢，所以可以直接使用下標（索引）來查找元素，使得ArrayList的查詢效率非常高旁瘫，get方法只是對數組的方法做了一個簡單的封裝祖凫，沒有多余的操作。而正是由于數組實現的底層酬凳，數組長度不可變惠况，導致每次新增和刪除元素使ArrayList長度發(fā)生變化的時候，都需要進行數組的復制操作宁仔，這樣使計算資源的消耗變大稠屠，導致效率較低。
簡單來說ArrayList的特點就是查詢快翎苫，增刪慢权埠。這里的慢是相對的，如果在增刪較少的場景使用煎谍，是完全可以的攘蔽。
在工作中會大量的使用到List集合，但是大部分時候都是無腦使用ArrayList來做實現呐粘，如果在性能要求較高并且頻繁的對List進行增刪元素的場景使用ArrayList秩彤，會使效率降低。那么這種頻繁增刪元素的場景該使用什么樣的List呢事哭？噔噔噔~噔~有請LinkedList出場漫雷。
LinkedList
鏈表是一種數據結構，有很多種形式鳍咱，LinkedList是使用雙向鏈表實現的降盹，那么雙向鏈表是個啥？
當我們站在一起排成一行的時候谤辜，就像軍訓的時候那樣蓄坏，每一行的同學只能知道你的左邊和右邊是誰，并不知道你左邊的左邊或者右邊的右邊是誰丑念。這種只知道左右涡戳，不知道其他的數據結構就是雙向鏈表。
雙向鏈表結構中的每一個元素不僅僅包含了數據脯倚，還記錄了上一個元素的地址和下一個元素的地址渔彰，所以每個元素只知道相鄰的元素的位置嵌屎，對于集合中的其他元素則是一概不知。
再來看一下LinkedList如何新增元素恍涂。
這個過程非潮Χ瑁快速，不用復制什么數組再沧，雙向鏈表知道第一個元素和最后一個元素的地址尼夺，來了一個新元素，將新元素的頭部指向前一個元素的值炒瘸，前一個元素的尾部指向新元素的值淤堵，這樣就完成了添加。
同理刪除元素也非城昀快粘勒，只需要修改前后元素的頭尾部指向的元素即可。
這里要提示一下屎即，LinkedList不僅僅實現了List的接口庙睡，還實現了Deque接口，Deque是隊列Queue的子接口技俐。翻譯一下乘陪，LinkedList不僅僅有List集合在指定下標新增刪除元素等功能，還有隊列集合Queue的在第一個元素之前添加元素addFirst雕擂，在最后一個元素后添加addLast等方法啡邑，充分的運用了雙向鏈表知道頭尾地址的優(yōu)勢。
LinkedList實現多個接口井赌，就是我們介紹接口的時候說的谤逼，用多個標準組成一個新標準，這個就是實現多個接口用法的最好例子仇穗。請各位細細品味流部。
總結一下LinkedList的特點就是增刪快，查詢慢纹坐。這里的增刪是指不按下標增刪枝冀，按照下標增刪元素一樣慢。
Vector
Vector這個集合是個非常古老的List實現耘子，早在java1.0的版本的時候就有了果漾，但是由于早期的方法名稱定義過于繁瑣等問題。經過多年的發(fā)展谷誓，ArrayList已經可以完全的替代Vector這個類绒障。這里說這個類，其實是很多古老的題目和不思進取的出題者會問 "ArrayList和Vector有什么區(qū)別呀捍歪？"户辱，他們希望的答案是“Vector線程安全鸵钝，ArrayList線程不安全”。其實ArrayList也可以通過一些手段達到線程安全焕妙，以后講多線程的時候蒋伦，再來告訴你答案吧弓摘。
因為ArrayList已經可以完全的替代Vector焚鹊，所以現在版本的java已經不再建議使用這個類，以后你可能只會在各種題目里面見到他韧献。
復習一下前面的知識
接口定義了標準末患，這里的List接口定義了添加元素，刪除元素等方法锤窑，而實現類根據不同的需求璧针，使用不同的實現方式，比如ArrayList用數組實現渊啰，查詢快探橱，LinkedList用雙向鏈表實現，增刪快绘证。如果我們還有其他場景有特殊需求隧膏，比如我要查詢快也要增刪快，你甚至可以自己去實現List接口嚷那，然后實現List的方法即可胞枕，這就是使用接口編程的好處。
以下是擴展知識魏宽，了解即可腐泻。
ArrayList的擴容
ArrayList在頻繁做增刪元素的時候效率會降低，究其原因就是底層需要判斷新建一個多長的新數組來存放增長后的集合队询，而這個判斷的過程比較復雜派桩，可能會需要一次，也可能會需要多次蚌斩，導致性能下降窄坦。
如果我們可以幫助ArrayList進行底層數組的擴容，也就是說我們成了指揮者凳寺，直接告訴他鸭津，你給我新建一個XXX長度的數組，而不是讓ArrayList自己去判斷肠缨，這樣效率會得到不小的提升逆趋。其實ArrayList里面也有提供定義數組容量的方法來精準的定義新數組長度。有興趣的同學可以去看看源代碼晒奕。
LinkedList下標操作的實現
前面說LinkedList的查詢效率比較慢闻书，原因就是雙向鏈表沒有數組那種操作下標的優(yōu)勢名斟。LinkedList的get（index）方法實現，做了以下操作：
1.將要查找的index與集合長度的一半進行對比
2.如果在index在集合前半段魄眉，從第一個元素開始砰盐，往后循環(huán)對比每一個元素，直到找到index的位置坑律。如果index在集合后半段岩梳，則從最后一個元素開始，往前循環(huán)遍歷晃择，直到找到index位置冀值。
你沒看錯，他只能循環(huán)宫屠，一個個對比列疗，你說能不慢么。不止是get（index）浪蹂，在LinkedList里面任何要使用index的地方抵栈，比如add（index，e）都是一個個循環(huán)對比坤次，所以效率都不高古劲。
總結，如果要操作下標浙踢，請使用ArrayList~
