人物背景：
老徐，男，本名徐福貴，從事Java相關研發工作多年，職場老油條，摸魚小能手，雖然歲數不大但長的比較着急，人稱老徐。據說之前炒某币敗光了所有家産，甚至現在還有欠債。
阿珍，女，本名陳家珍，剛剛入職不久的實習生，雖然是職場菜鳥但聰明好學。據說是學校的四大校花之一，追求她的人從旺角排到了銅鑼灣，不過至今還單身。
老徐問道：“阿珍，你知道ArrayList和LinkedList的差別嗎？”
阿珍微微一笑，說：“這也太小兒科了，ArrayList是基于數組實作，LinkedList是基于連結清單實作。”
老徐豎起了大拇指，說：“不錯，有進步！那你知道ArrayList和LinkedList的效率到底哪個高？”
阿珍回答：“這也難不倒我，這要分不同情況的。在新增、删除元素時，LinkedList的效率要高于ArrayList，而在周遊的時候，ArrayList的效率要高于LinkedList。”
老徐反問到：“不一定哦。在新增、删除元素時，LinkedList的效率有可能低于ArrayList，而在周遊的時候，ArrayList的效率有可能低于LinkedList。”
阿珍回答：“不可能，絕對不可能，書上都是這麼寫的。”
老徐得意地笑了，說：“實踐是檢驗真理的唯一标準。趁着老闆不在，咱兩寫個程式實踐一下。”
ArrayList和LinkedList的新增元素對比
首先，寫一段計算新增元素耗時的代碼：
/**
* 從List的頭部新增元素
* @param list list
* @param count 新增元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static long addHeader(List<String> list, int count) {
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.add(0, "onemore-" + i);
}
long end = System.nanoTime();
return (end - start) / 1000000;
}
/**
* 從List的中部新增元素
* @param list list
* @param count 新增元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static long addMiddle(List<String> list, int count) {
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.add(list.size() / 2, "onemore-" + i);
}
long end = System.nanoTime();
return (end - start) / 1000000;
}
/**
* 從List的尾部新增元素
* @param list list
* @param count 新增元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static long addTail(List<String> list, int count) {
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
long end = System.nanoTime();
return (end - start) / 1000000;
}
複制
然後，我們把新增元素的個數設定為50000，對比一下：
public static void main(String[] args) {
int count = 50000;
System.out.println("從ArrayList的頭部新增元素：" + addHeader(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的頭部新增元素：" + addHeader(new LinkedList<>(), count) + "ms");
System.out.println("從ArrayList的中部新增元素：" + addMiddle(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的中部新增元素：" + addMiddle(new LinkedList<>(), count) + "ms");
System.out.println("從ArrayList的尾部新增元素：" + addTail(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的尾部新增元素：" + addTail(new LinkedList<>(), count) + "ms");
}
複制
運作結果如下：
ArrayList從頭部新增元素：204ms
LinkedList從頭部新增元素：17ms
ArrayList從中部新增元素：71ms
LinkedList從中部新增元素：8227ms
ArrayList從尾部新增元素：13ms
LinkedList從尾部新增元素：21ms
複制
我們可以看出，從頭部新增元素時，ArrayList的效率低于LinkedList；從中部新增元素時，ArrayList的效率高于LinkedList；從尾部新增元素時，ArrayList的效率高于LinkedList。
阿珍驚呆了，說：“怎麼可能？這是為什麼呀？”老徐回答：“我來幫你簡單分析一下。”
ArrayList是基于數組實作的，在添加元素到數組頭部的時候，在添加元素之前需要把頭部以後的元素一個一個地往後挪，是以效率很低；而LinkedList是基于連結清單實作，從頭部添加元素的時候，通過頭部指針就可以直接添加，是以效率很高。
ArrayList在添加元素到數組中間的時候，同樣有部分元素需要一個一個地往後挪，是以效率也不是很高；而LinkedList從中部添加元素的時候，是添加元素最低效率的，因為靠近中間位置，在添加元素之前需要循環查找周遊部分元素，是以效率很低。
ArrayList從尾部添加元素的時候，不需要挪動任何元素，直接把元素放入數組，效率非常高。而LinkedList雖然不需要循環查找周遊元素，但LinkedList中多了實列化節點對象和變換指針指向的過程，是以效率較低一些。
當然，這裡有一個大前提，就是ArrayList初始化容量足夠，不需要動态擴容數組容量。是以，在我們的日常開發中，最好指定ArrayList的初始化容量。
ArrayList和LinkedList的删除元素對比
首先，寫一段計算删除元素耗時的代碼：
/**
* 從List的頭部删除元素
* @param list list
* @param count 删除元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static double deleteHeader(List<String> list, int count) {
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.remove(0);
}
long end = System.nanoTime();
return (end - start) / 1000000.0;
}
/**
* 從List的中部删除元素
* @param list list
* @param count 删除元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static double deleteMiddle(List<String> list, int count) {
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.remove(list.size() / 2);
}
long end = System.nanoTime();
return (end - start) / 1000000.0;
}
/**
* 從List的尾部删除元素
* @param list list
* @param count 删除元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static double deleteTail(List<String> list, int count) {
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
list.remove(list.size() - 1);
}
long end = System.nanoTime();
return (end - start) / 1000000.0;
}
複制
然後，我們把删除元素的個數設定為50000，對比一下：
public static void main(String[] args) {
int count = 50000;
System.out.println("從ArrayList的頭部删除元素：" + deleteHeader(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的頭部删除元素：" + deleteHeader(new LinkedList<>(), count) + "ms");
System.out.println("從ArrayList的中部删除元素：" + deleteMiddle(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的中部删除元素：" + deleteMiddle(new LinkedList<>(), count) + "ms");
System.out.println("從ArrayList的尾部删除元素：" + deleteTail(new ArrayList<>(count), count) + "ms");
System.out.println("從LinkedList的尾部删除元素：" + deleteTail(new LinkedList<>(), count) + "ms");
}
複制
運作結果如下：
從ArrayList的頭部删除元素：260.7014ms
從LinkedList的頭部删除元素：14.2948ms
從ArrayList的中部删除元素：95.9073ms
從LinkedList的中部删除元素：3602.6931ms
從ArrayList的尾部删除元素：1.6261ms
從LinkedList的尾部删除元素：3.9645ms
複制
我們可以看出，從頭部删除元素時，ArrayList的效率低于LinkedList；從中部删除元素時，ArrayList的效率高于LinkedList；從尾部删除元素時，ArrayList的效率高于LinkedList。
阿珍搶着說：“删除元素這個我知道，和新增元素的原理差不多。”老徐回答：“既然你知道了，我就不啰嗦了，我們繼續看周遊元素。”
ArrayList和LinkedList的周遊元素對比
周遊元素一般有兩種方式：for循環和foreach，寫一段計算這兩種周遊方式耗時的代碼：
/**
* 通過for循環周遊List
*
* @param list list
* @param count 周遊元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static double getByFor(List<String> list, int count) {
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
String name = "萬貓學社";
long start = System.nanoTime();
for (int i = 0; i < count; i++) {
if (name.equals(list.get(i))) {
System.out.println(name);
}
}
long end = System.nanoTime();
return (end - start) / 1000000.0;
}
/**
* 通過foreach周遊List
*
* @param list list
* @param count 周遊元素的個數
* @return 所耗費的時間（機關：ms）
*/
public static double getByForeach(List<String> list, int count) {
for (int i = 0; i < count; i++) {
list.add("onemore-" + i);
}
String name = "萬貓學社";
long start = System.nanoTime();
for (String str : list) {
if (name.equals(str)) {
System.out.println(name);
}
}
long end = System.nanoTime();
return (end - start) / 1000000.0;
}
複制
然後，我們把周遊元素的個數設定為50000，對比一下：
public static void main(String[] args) {
int count = 50000;
System.out.println("通過for循環周遊ArrayList：" + getByFor(new ArrayList<>(count), count) + "ms");
System.out.println("通過for循環周遊LinkedList：" + getByFor(new LinkedList<>(), count) + "ms");
System.out.println("通過foreach周遊ArrayList：" + getByForeach(new ArrayList<>(count), count) + "ms");
System.out.println("通過foreach周遊LinkedList：" + getByForeach(new LinkedList<>(), count) + "ms");
}
複制
運作結果如下：
通過for循環周遊ArrayList：3.4403ms
通過for循環周遊LinkedList：3563.1219ms
通過foreach周遊ArrayList：3.7388ms
通過foreach周遊LinkedList：3.7953ms
複制
我們可以看到，通過for循環周遊時，ArrayList的效率高于LinkedList，而且LinkedList的效率極低；通過foreach周遊時，ArrayList的效率和LinkedList相差不大。
老徐：“阿珍，你知道為什麼for循環周遊LinkedList的效率那麼低嗎？”
阿珍：“因為LinkedList基于連結清單實作的，每一次for循環都要周遊找到對應的節點，是以嚴重影響了周遊的效率；而ArrayList直接可以通過數組下标直接找到對應的元素，是以for循環效率非常高。對不對？”
老徐：“是的，是以我們不要使用for循環周遊LinkedList。”
總結
ArrayList是基于數組實作，LinkedList是基于連結清單實作。
在ArrayList初始化容量足夠的情況下，從頭部新增元素時，ArrayList的效率低于LinkedList；從中部新增元素時，ArrayList的效率高于LinkedList；從尾部新增元素時，ArrayList的效率高于LinkedList。
從頭部删除元素時，ArrayList的效率低于LinkedList；從中部删除元素時，ArrayList的效率高于LinkedList；從尾部删除元素時，ArrayList的效率高于LinkedList。
通過for循環周遊時，ArrayList的效率高于LinkedList，而且LinkedList的效率極低；通過foreach周遊時，ArrayList的效率和LinkedList相差不大。