人物背景：
老徐，男，本名徐福貴，從事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相差不大，
微信掃描二維碼關注后回復「電子書」，獲取12本Java必讀技術書籍，
最后，謝謝你這么帥，還給我點贊和關注，
作者：萬貓學社
出處：http://www.cnblogs.com/heihaozi/
著作權宣告：本文遵循 CC 4.0 BY-NC-SA 著作權協議，轉載請附上原文出處鏈接和本宣告，
微信掃描二維碼，關注萬貓學社，回復「電子書」，免費獲取12本Java必讀技術書籍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/450348.html
標籤：Java
上一篇：【C/C++】編程基礎