List是一個(gè)有序的集合屎篱，和set不同的是盈罐，List允許存儲(chǔ)項(xiàng)的值為空驻右，也允許存儲(chǔ)相等值的存儲(chǔ)項(xiàng)
本文參考了一下博客
1.https://blog.csdn.net/wz249863091/article/details/52853360
2.https://blog.csdn.net/zxt0601/article/details/77281231
1.ArrayList
ArrayList是一個(gè)數(shù)組實(shí)現(xiàn)的列表，由于是以數(shù)組的形式存儲(chǔ)起惕，決定了特點(diǎn)是查詢快涡贱，插入刪除慢。（因?yàn)橹赶蛩饕恢貌迦雽?duì)象時(shí),會(huì)將指定索引位置及之后的所有對(duì)象相應(yīng)向后移動(dòng)一位）惹想。
- ArrayList初始容量是10问词。
- 如果能預(yù)先知道數(shù)據(jù)項(xiàng)的個(gè)數(shù)，盡量使用initialCapacity帶參的構(gòu)造函數(shù)嘀粱，因?yàn)闊o(wú)參的在擴(kuò)充容量的時(shí)候要不停的調(diào)Arrays.copyof()方法激挪，擴(kuò)展數(shù)組大小造成性能浪費(fèi)。
- add操作：不管是不是指定index的add操作锋叨，都會(huì)先確認(rèn)當(dāng)前的數(shù)組空間是否夠插入數(shù)據(jù)垄分。ArrayList默認(rèn)每次都是自增50%（10,15,22,33...）的大小再和minCapacity比較，如果還是不夠娃磺，就把當(dāng)前的size擴(kuò)充至minCapacity薄湿。如果是在中間插入，需要用到System.arraycopy豌鸡，把index開(kāi)始所有的數(shù)據(jù)向后移動(dòng)一位再進(jìn)行插入嘿般。
- 減少擴(kuò)容帶來(lái)的性能問(wèn)題可以通過(guò)段标，1）
public ArrayList(int initialCapacity) {} //構(gòu)造方法涯冠，指定集合的大小。
2）在需要擴(kuò)容的時(shí)候逼庞，手動(dòng)調(diào)用方法擴(kuò)容蛇更。
public void ensureCapacity(int minCapacity) {}
不過(guò)該方法是ArrayList的API，不是List接口里的赛糟，所以使用時(shí)需要強(qiáng)轉(zhuǎn):
((ArrayList)list).ensureCapacity(20);
優(yōu)點(diǎn)
1.底層是數(shù)組派任，根據(jù)下標(biāo)查找的時(shí)間復(fù)雜段為O(1)。
缺點(diǎn)
1.因其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組璧南，所以可想而知掌逛，它是占據(jù)一塊連續(xù)的內(nèi)存空間（容量就是數(shù)組的length），所以它也有數(shù)組的缺點(diǎn)司倚，空間效率不高豆混。
2.線程不安全，主要體現(xiàn)在动知，在做add和remove等操作的時(shí)候皿伺，整個(gè)方法不是原子的。以增操作為案例
源碼：
public boolean add(E e) {
// 確定ArrayList的容量大小
ensureCapacity(size + 1); // Increments modCount!!
// 添加e到ArrayList中
elementData[size++] = e;
return true;
}
// 若ArrayList的容量不足以容納當(dāng)前的全部元素盒粮，設(shè)置 新的容量=“(原始容量x3)/2 + 1”
public void ensureCapacity(int minCapacity) {
// 將“修改統(tǒng)計(jì)數(shù)”+1鸵鸥，該變量主要是用來(lái)實(shí)現(xiàn)fail-fast機(jī)制的
modCount++;
int oldCapacity = elementData.length;
// 若當(dāng)前容量不足以容納當(dāng)前的元素個(gè)數(shù)，設(shè)置 新的容量=“(原始容量x3)/2 + 1”
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
//如果還不夠丹皱，則直接將minCapacity設(shè)置為當(dāng)前容量
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
而elementData[size++] = e; 其實(shí)可以看成兩步
- elementData[size] = e妒穴；
- size ++宋税；
①假設(shè)A線程執(zhí)行完第一條語(yǔ)句時(shí)，CPU暫停執(zhí)行A線程轉(zhuǎn)而去執(zhí)行B線程宰翅，此時(shí)ArrayList的size并沒(méi)有加一弃甥，這時(shí)在ArrayList中B線程就會(huì)覆蓋掉A線程賦的值，而此時(shí)汁讼，A線程和B線程先后執(zhí)行size++淆攻，便會(huì)出現(xiàn)值為null的情況；
②至于異常情況中會(huì)出現(xiàn)的ArrayIndexOutOfBoundsException異常嘿架，
則是A線程在執(zhí)行ensureCapacity(size+1)后沒(méi)有繼續(xù)執(zhí)行瓶珊，此時(shí)恰好minCapacity等于oldCapacity，B線程再去執(zhí)行耸彪，同樣由于minCapacity等于oldCapacity伞芹，ArrayList并沒(méi)有增加長(zhǎng)度，B線程可以繼續(xù)執(zhí)行賦值（elementData[size] = e）并size ++也執(zhí)行了蝉娜，此時(shí)唱较，CPU又去執(zhí)行A線程的賦值操作，由于size值加了1召川，size值大于了ArrayList的最大長(zhǎng)度南缓，
因此便出現(xiàn)了ArrayIndexOutOfBoundsException異常。
解決：
如果需要在多線程中使用荧呐，可以采用list<Object> list =Collections.synchronizedList(new ArrayList<Object>)來(lái)創(chuàng)建一個(gè)ArrayList對(duì)象汉形。
2.Vector
Vector就是ArrayList的線程安全版，它的方法前都加了synchronized鎖倍阐，其他實(shí)現(xiàn)邏輯都相同概疆。
如果對(duì)線程安全要求不高的話，可以選擇ArrayList峰搪，畢竟synchronized也很耗性能岔冀。
3.LinkedList
LinkedList還是一個(gè)雙向鏈表。
跟數(shù)據(jù)結(jié)構(gòu)里的鏈表是一樣的概耻，只不過(guò)C里面的是指針之前前后節(jié)點(diǎn)使套，java是用的對(duì)象。
通過(guò)上面對(duì)ArrayList和LinkedList的分析咐蚯，可以理解List的3個(gè)特性
1.是按順序查找
2.允許存儲(chǔ)項(xiàng)為空
3.允許多個(gè)存儲(chǔ)項(xiàng)的值相等
