ArrayList, LinkedList, Vector, Stack是List的4個(gè)實(shí)現(xiàn)類。
ArrayList 是一個(gè)數(shù)組隊(duì)列虽画，相當(dāng)于動(dòng)態(tài)數(shù)組舞蔽。它由數(shù)組實(shí)現(xiàn)，隨機(jī)訪問(wèn)效率高码撰，隨機(jī)插入渗柿、隨機(jī)刪除效率低。
LinkedList 是一個(gè)雙向鏈表脖岛。它也可以被當(dāng)作堆棧朵栖、隊(duì)列或雙端隊(duì)列進(jìn)行操作。LinkedList隨機(jī)訪問(wèn)效率低柴梆，但隨機(jī)插入陨溅、隨機(jī)刪除效率低。
Vector 是矢量隊(duì)列绍在，和ArrayList一樣门扇，它也是一個(gè)動(dòng)態(tài)數(shù)組，由數(shù)組實(shí)現(xiàn)偿渡。但是ArrayList是非線程安全的臼寄，而Vector是線程安全的。
Stack 是棧溜宽，它繼承于Vector吉拳。它的特性是：先進(jìn)后出(FILO, First In Last Out)。
(1) 對(duì)于需要快速插入适揉，刪除元素留攒，應(yīng)該使用LinkedList。
(2) 對(duì)于需要快速隨機(jī)訪問(wèn)元素嫉嘀，應(yīng)該使用ArrayList炼邀。
(3) 對(duì)于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會(huì)被單個(gè)線程操作”吃沪，此時(shí)應(yīng)該使用非同步的類(如ArrayList)汤善。
對(duì)于“多線程環(huán)境，且List可能同時(shí)被多個(gè)線程操作”票彪，此時(shí)红淡，應(yīng)該使用同步的類(如Vector)。
LinkedList和ArrayList性能差異分析（基于jdk1.8）
1.隨機(jī)插入
LinkedList在指定位置插入元素：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
//查找指定的node
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
從上面可以看出降铸，通過(guò)add(int,E)向LinkedList中插入元素時(shí)在旱，先是在雙向鏈表中找到要插入節(jié)點(diǎn)的位置index；找到之后推掸，再插入一個(gè)新節(jié)點(diǎn)桶蝎。雙向鏈表查找index位置的節(jié)點(diǎn)時(shí)驻仅，有一個(gè)加速動(dòng)作：若index < 雙向鏈表長(zhǎng)度的1/2，則從前向后查找; 否則登渣，從后向前查噪服。
ArrayList向指定位置插入元素：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
可以看到有個(gè)操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index)
這意味著，每插入一個(gè)元素胜茧，這個(gè)元素之后的所有元素index都會(huì)改變粘优。之所以插入元素慢，原因就在這里
2.隨機(jī)訪問(wèn)
LinkedList訪問(wèn)指定位置元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//查找指定的node
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
可以看出呻顽，在LinkedList中獲取指定元素時(shí)雹顺，需要先在雙向鏈表中找到index位置的元素，然后才能訪問(wèn)
而ArrayList訪問(wèn)指定元素：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
可以看出廊遍，在ArrayList中獲取指定元素時(shí)嬉愧，直接返回?cái)?shù)組中index位置的元素，而不需要像LinkedList一樣進(jìn)行查找喉前，因此速度更快
3.性能測(cè)試對(duì)比
在頭部插入節(jié)點(diǎn)没酣，元素?cái)?shù)量分別為10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000，測(cè)試代碼如下：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add(0, "1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add(0,"1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
}
結(jié)果：
num : 100ArrayList cost : 2ms
num : 100LinkedList cost : 0ms
num : 1000ArrayList cost : 2ms
num : 1000LinkedList cost : 4ms
num : 5000ArrayList cost : 5ms
num : 5000LinkedList cost : 24ms
num : 10000ArrayList cost : 6ms
num : 10000LinkedList cost : 76ms
num : 100000ArrayList cost : 535ms
num : 100000LinkedList cost : 33265ms
num : 1000000ArrayList cost : 84961ms
由于機(jī)子性能一般被饿，卡到100W還在一直跑...
分析：即使在頭部插入節(jié)點(diǎn)四康，LinkedList效率也不如ArrayList，而且性能差很多狭握，和網(wǎng)上資料并不相符。希望有大神可以解釋一下
隨機(jī)插入：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add((int)(Math.random()*i), "1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add((int)(Math.random()*i),"1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
結(jié)果：
num : 10000ArrayList cost : 12ms
num : 10000LinkedList cost : 87ms
num : 100000ArrayList cost : 477ms
num : 100000LinkedList cost : 37157ms
由于機(jī)子性能一般疯溺，卡到100W還在一直跑...
分析：從上面看出论颅，LinkedList隨機(jī)插入效果還不如ArrayList，感覺(jué)不太對(duì)啊囱嫩，是數(shù)據(jù)量太大了嗎恃疯？那換小一點(diǎn)試試
num : 100ArrayList cost : 2ms
num : 100LinkedList cost : 0ms
num : 1000ArrayList cost : 2ms
num : 1000LinkedList cost : 4ms
num : 5000ArrayList cost : 5ms
num : 5000LinkedList cost : 24ms
效率依然不怎么樣啊，想不明白墨闲。今妄。
在尾部插入：
public static void main(String[] args) {
int[] nums = {10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000};
for(int i=0; i<nums.length; i++){
testList(nums[i]);
}
}
public static void testList(int num){
List<String> aList = new ArrayList<String>();
List<String> lList = new LinkedList<String>();
long starttime, endtime;
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
aList.add("1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "ArrayList cost : " + (endtime - starttime) + "ms");
starttime= System.currentTimeMillis();
for(int i=0; i<num; i++){
lList.add("1");
}
endtime = System.currentTimeMillis();
System.out.println("num : " + num + "LinkedList cost : " + (endtime - starttime) + "ms");
}
結(jié)果：
num : 10000ArrayList cost : 2ms
num : 10000LinkedList cost : 2ms
num : 100000ArrayList cost : 7ms
num : 100000LinkedList cost : 5ms
num : 1000000ArrayList cost : 29ms
num : 1000000LinkedList cost : 22ms
num : 10000000ArrayList cost : 150ms
num : 10000000LinkedList cost : 4874ms
num : 100000000ArrayList cost : 1800ms
num : 100000000LinkedList cost : 66919ms
分析：在數(shù)據(jù)量較小（小于100W）時(shí)鸳碧，兩種list插入效率差不多盾鳞，原因是只在尾部插入，ArrayList并不需要移動(dòng)元素瞻离，而在數(shù)據(jù)量較大時(shí)腾仅，LinkedList效率急速下降，這里我認(rèn)為是LinkedList在插入節(jié)點(diǎn)時(shí)套利，需要向jvm申請(qǐng)空間而導(dǎo)致效率降低推励，在網(wǎng)上也沒(méi)有查到相關(guān)資料
感覺(jué)出現(xiàn)了許多和預(yù)期不一樣的結(jié)果鹤耍，有沒(méi)有大佬可以解釋一下的~
