一、概念:
一般我們都知道ArrayList＊ 由一個(gè)數(shù)組后推得到的 List。作為一個(gè)常規(guī)用途的對(duì)象容器使用，用于替換原先的 Vector。允許我們快速訪問元素，但在從列表中部插入和刪除元素時(shí)，速度卻嫌稍慢。一般只應(yīng)該用ListIterator 對(duì)一個(gè) ArrayList 進(jìn)行向前和向后遍歷，不要用它刪除和插入元素；與 LinkedList 相比，它的效率要低許多LinkedList 提供優(yōu)化的順序訪問性能，同時(shí)可以高效率地在列表中部進(jìn)行插入和刪除操作。但在進(jìn)行隨機(jī)訪問時(shí)，速度卻相當(dāng)慢，此時(shí)應(yīng)換用 ArrayList。
二、測(cè)試
本來自己寫了一些測(cè)試類想測(cè)試下ArrayList和LinkedList的性能比較，發(fā)現(xiàn)怎么寫都差強(qiáng)人意，今天在《Thinking in Java》中看到了這樣的一段代碼，個(gè)人覺得寫得不賴。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
public class ListPerformance{ private static final int REPS = 100; private abstract static class Tester//內(nèi)部抽象類，作為L(zhǎng)ist測(cè)試。 { String name; int size; Tester(String name, int size) { this.name = name; this.size = size; } abstract void test(List a); } private static Tester[] tests = {new Tester("get", 300)//一個(gè)測(cè)試數(shù)組，存儲(chǔ)get(隨機(jī)取)、iteration(順序遍歷)、insert(中間插入)、remove(隨機(jī)刪除) { void test(List a) { for (int i = 0; i < REPS; i++) { for (int j = 0; j < a.size(); j++) { a.get(j); } } } }, new Tester("iteration", 300) { void test(List a) { for (int i = 0; i < REPS; i++) { Iterator it = a.iterator(); while (it.hasNext()) it.next(); } } }, new Tester("insert", 1000) { void test(List a) { int half = a.size() / 2; String s = "test"; ListIterator it = a.listIterator(half); for (int i = 0; i < size * 10; i++) { it.add(s); } } }, new Tester("remove", 5000) { void test(List a) { ListIterator it = a.listIterator(3); while (it.hasNext()) { it.next(); it.remove(); } } }, }; public static void test(List a) { System.out.println("Testing " + a.getClass().getName());//輸出測(cè)試的類名稱 for (int i = 0; i < tests.length; i++) { fill(a, tests[i].size);//填充空集合 System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(a);//進(jìn)行測(cè)試 long t2 = System.currentTimeMillis(); System.out.print(":" + (t2 - t1)+" ms "); } } public static Collection fill(Collection c, int size) { for (int i = 0; i < size; i++) { c.add(Integer.toString(i)); } return c; } public static void main(String[] args) { test(new ArrayList()); System.out.println(); test(new LinkedList()); }} |
三、總結(jié)
首先，真的夸一下，這段代碼寫得真是好啊，無論是內(nèi)部類的應(yīng)用還是對(duì)面向?qū)ο蟮恼J(rèn)識(shí)，都考慮的恰到好處，哎，我什么時(shí)候才能寫出這么棒的代碼啊。
測(cè)試結(jié)果每次都有些許的差異，但不難得出以下的結(jié)論：
1、在 ArrayList 中進(jìn)行隨機(jī)訪問（即 get()）以及循環(huán)反復(fù)是最劃得來的 。原因在于，ArrayList是基于數(shù)組而來的，所以每個(gè)元素都有其對(duì)應(yīng)的index，所以隨機(jī)定位一個(gè)元素要快捷的多。
2、在 LinkedList 中進(jìn)行順序訪問、插入、刪除動(dòng)作的話還是比較高效的。原因在于，插入、刪除的話對(duì)于LinkedList來說只需要改變其排列的一個(gè)node結(jié)點(diǎn)就可以了，而對(duì)于ArrayList來說刪除一個(gè)元素，需要不斷把后面的元素移到前面的位置上。
3、至于順序訪問，之前一直認(rèn)為ArrayList 基于數(shù)組排列，在內(nèi)存中是連續(xù)排列的，應(yīng)該會(huì)快得多，然后多次測(cè)試發(fā)現(xiàn)并不是想象的那樣，或者說ArrayList沒有表現(xiàn)出它該有的優(yōu)勢(shì)，甚至還不如LinkedList的訪問速度。原因在于:LinkedList 提供了優(yōu)化的順序訪問性能。
總結(jié)
以上所述是小編給大家介紹的ArrayList 和 LinkedList的執(zhí)行效率比較，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)服務(wù)器之家網(wǎng)站的支持！
原文鏈接：http://www.cnblogs.com/jmcui/archive/2017/08/14/7357092.html
