ArrayList, LinkedList, Vector, Stack是List的4個實現(xiàn)類。
ArrayList 是一個數(shù)組隊列，相當(dāng)于動態(tài)數(shù)組。它由數(shù)組實現(xiàn)，隨機訪問效率高，隨機插入、隨機刪除效率低。
LinkedList 是一個雙向鏈表。它也可以被當(dāng)作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。
Vector 是矢量隊列，和ArrayList一樣，它也是一個動態(tài)數(shù)組，由數(shù)組實現(xiàn)。但是ArrayList是非線程安全的，而Vector是線程安全的。
Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。
(1) 對于需要快速插入，刪除元素，應(yīng)該使用LinkedList。
(2) 對于需要快速隨機訪問元素，應(yīng)該使用ArrayList。
(3) 對于“單線程環(huán)境” 或者 “多線程環(huán)境，但List僅僅只會被單個線程操作”，此時應(yīng)該使用非同步的類(如ArrayList)。
對于“多線程環(huán)境，且List可能同時被多個線程操作”，此時，應(yīng)該使用同步的類(如Vector)。
LinkedList和ArrayList性能差異分析（基于jdk1.8）
1.隨機插入
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;
}
}
從上面可以看出，通過add(int,E)向LinkedList中插入元素時，先是在雙向鏈表中找到要插入節(jié)點的位置index；找到之后，再插入一個新節(jié)點。雙向鏈表查找index位置的節(jié)點時，有一個加速動作：若index < 雙向鏈表長度的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++;
}
可以看到有個操作
System.arraycopy(elementData, index, elementData, index + 1,
size - index)
這意味著，每插入一個元素，這個元素之后的所有元素index都會改變。之所以插入元素慢，原因就在這里
2.隨機訪問
LinkedList訪問指定位置元素
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中獲取指定元素時，需要先在雙向鏈表中找到index位置的元素，然后才能訪問
而ArrayList訪問指定元素：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
可以看出，在ArrayList中獲取指定元素時，直接返回數(shù)組中index位置的元素，而不需要像LinkedList一樣進行查找，因此速度更快
3.性能測試對比
在頭部插入節(jié)點，元素數(shù)量分別為10000,10 * 10000,100 * 10000, 1000 * 10000, 10000 * 10000，測試代碼如下：
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
由于機子性能一般，卡到100W還在一直跑...
分析：即使在頭部插入節(jié)點，LinkedList效率也不如ArrayList，而且性能差很多，和網(wǎng)上資料并不相符。希望有大神可以解釋一下
隨機插入：
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
由于機子性能一般，卡到100W還在一直跑...
分析：從上面看出，LinkedList隨機插入效果還不如ArrayList，感覺不太對啊，是數(shù)據(jù)量太大了嗎？那換小一點試試
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ù)量較?。ㄐ∮?00W）時，兩種list插入效率差不多，原因是只在尾部插入，ArrayList并不需要移動元素，而在數(shù)據(jù)量較大時，LinkedList效率急速下降，這里我認為是LinkedList在插入節(jié)點時，需要向jvm申請空間而導(dǎo)致效率降低，在網(wǎng)上也沒有查到相關(guān)資料
感覺出現(xiàn)了許多和預(yù)期不一樣的結(jié)果，有沒有大佬可以解釋一下的~
