當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

List集合的总结和应用场景的介绍

發布時間：2024/8/26 综合教程 35 生活家

生活随笔收集整理的這篇文章主要介紹了 List集合的总结和应用场景的介绍小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1、List的整體介紹

List 是一個接口，它繼承于Collection的接口，它代表著有序的隊列。list的實現類對象中每一個元素都有一個索引值，能夠按照索引值進行元素查找。
AbstractList 是一個抽象類，它繼承于AbstractCollection。AbstractList實現List接口中除size()、get(int location)之外的函數。
AbstractSequentialList 是一個抽象類，它繼承于AbstractList。AbstractSequentialList 實現了“鏈表中，根據index索引值操作鏈表的全部函數”。
ArrayList, LinkedList, Vector, Stack是List的4個實現類。

ArrayList 是一個數組隊列，相當于動態數組。它由動態數組實現，隨機訪問效率高，隨機插入、隨機刪除效率低。ArrayList是非線程安全的。
LinkedList 是一個雙向鏈表。它是由雙向鏈表實現的，它也可以被當作堆棧、隊列或雙端隊列進行操作。LinkedList隨機訪問效率低，但隨機插入、隨機刪除效率低。一般對LinkedList進行元素遍歷的時候使用removeFist()函數和removeLast()函數進行遍歷的時候效率比較高，隨機訪問的方式效率最低。　　
Vector 是矢量隊列，和ArrayList一樣，它也是一個動態數組實現。Vector是線程安全的。

Stack 是棧，它繼承于Vector。它的特性是：先進后出(FILO, First In Last Out)。

2、List的使用場景

如果涉及到“棧”、“隊列”、“鏈表”等操作，應該考慮用List，具體的選擇哪個List，根據下面的標準來取舍。
(01) 對于需要快速插入，刪除元素，應該使用LinkedList。
(02) 對于需要快速隨機訪問元素，應該使用ArrayList，也可以使用Vector。
(03) 對于“單線程環境” 或者 “多線程環境，但List僅僅只會被單個線程操作”，此時應該使用非同步的類(如ArrayList)。
對于“多線程環境，且List可能同時被多個線程操作”，此時，應該使用同步的類(如Vector)。

下面是對不同集合類是測試程序：

 1 import java.util.*;
 2 import java.lang.Class;
 3 
 4 /*
 5  * @desc 對比ArrayList和LinkedList的插入、隨機讀取效率、刪除的效率
 6  *
 7  * @author skywang
 8  */
 9 public class ListCompareTest {
10 
11     private static final int COUNT = 100000;
12 
13     private static LinkedList linkedList = new LinkedList();
14     private static ArrayList arrayList = new ArrayList();
15     private static Vector vector = new Vector();
16     private static Stack stack = new Stack();
17 
18     public static void main(String[] args) {
19         // 換行符
20         System.out.println();
21         // 插入
22         insertByPosition(stack) ;
23         insertByPosition(vector) ;
24         insertByPosition(linkedList) ;
25         insertByPosition(arrayList) ;
26 
27         // 換行符
28         System.out.println();
29         // 隨機讀取
30         readByPosition(stack);
31         readByPosition(vector);
32         readByPosition(linkedList);
33         readByPosition(arrayList);
34 
35         // 換行符
36         System.out.println();
37         // 刪除 
38         deleteByPosition(stack);
39         deleteByPosition(vector);
40         deleteByPosition(linkedList);
41         deleteByPosition(arrayList);
42     }
43 
44     // 獲取list的名稱
45     private static String getListName(List list) {
46         if (list instanceof LinkedList) {
47             return "LinkedList";
48         } else if (list instanceof ArrayList) {
49             return "ArrayList";
50         } else if (list instanceof Stack) {
51             return "Stack";
52         } else if (list instanceof Vector) {
53             return "Vector";
54         } else {
55             return "List";
56         }
57     }
58 
59     // 向list的指定位置插入COUNT個元素，并統計時間
60     private static void insertByPosition(List list) {
61         long startTime = System.currentTimeMillis();
62 
63         // 向list的位置0插入COUNT個數
64         for (int i=0; i<COUNT; i++)
65             list.add(0, i);
66 
67         long endTime = System.currentTimeMillis();
68         long interval = endTime - startTime;
69         System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time：" + interval+" ms");
70     }
71 
72     // 從list的指定位置刪除COUNT個元素，并統計時間
73     private static void deleteByPosition(List list) {
74         long startTime = System.currentTimeMillis();
75 
76         // 刪除list第一個位置元素
77         for (int i=0; i<COUNT; i++)
78             list.remove(0);
79 
80         long endTime = System.currentTimeMillis();
81         long interval = endTime - startTime;
82         System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time：" + interval+" ms");
83     }
84 
85     // 根據position，不斷從list中讀取元素，并統計時間
86     private static void readByPosition(List list) {
87         long startTime = System.currentTimeMillis();
88 
89         // 讀取list元素
90         for (int i=0; i<COUNT; i++)
91             list.get(i);
92 
93         long endTime = System.currentTimeMillis();
94         long interval = endTime - startTime;
95         System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time：" + interval+" ms");
96     }
97 }

View Code

測試結果：

 1 Stack : insert 100000 elements into the 1st position use time：1640 ms
 2 Vector : insert 100000 elements into the 1st position use time：1607 ms
 3 LinkedList : insert 100000 elements into the 1st position use time：29 ms
 4 ArrayList : insert 100000 elements into the 1st position use time：1617 ms
 5 
 6 Stack : read 100000 elements by position use time：9 ms
 7 Vector : read 100000 elements by position use time：6 ms
 8 LinkedList : read 100000 elements by position use time：10809 ms
 9 ArrayList : read 100000 elements by position use time：5 ms
10 
11 Stack : delete 100000 elements from the 1st position use time：1916 ms
12 Vector : delete 100000 elements from the 1st position use time：1910 ms
13 LinkedList : delete 100000 elements from the 1st position use time：15 ms
14 ArrayList : delete 100000 elements from the 1st position use time：1909 ms

從中，我們可以發現：
插入10萬個元素，LinkedList所花時間最短：29ms。
刪除10萬個元素，LinkedList所花時間最短：15ms。
遍歷10萬個元素，LinkedList所花時間最長：10809 ms；而ArrayList、Stack和Vector則相差不多，都只用了幾秒。

考慮到Vector是支持同步的，而Stack又是繼承于Vector的；因此，得出結論：
(01) 對于需要快速插入，刪除元素，應該使用LinkedList。
(02) 對于需要快速隨機訪問元素，應該使用ArrayList。
(03) 對于“單線程環境” 或者 “多線程環境，但List僅僅只會被單個線程操作”，此時應該使用非同步的類。

3、ArrayList和LinkedList的對比分析

3.1、LinkedList的插入刪除元素的效率比ArrayList的效率要高

　　從源代碼中我們可以看出：通過add(int index, E element)向LinkedList插入元素時。先是在雙向鏈表中找到要插入節點的位置index；找到之后，再插入一個新節點。雙向鏈表查找index位置的節點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。而且因為Linked List是通過雙向鏈表實現的，插入刪除元素的時候不需要移動大量的元素。

　在ArrayList中，當我們要插入元素的時候，首先要調用ensureCapacity(size+1)函數，它的作用是“確認ArrayList的容量，若容量不夠，則增加容量。”但是真正耗時的操作是 System.arraycopy(elementData, index, elementData, index + 1, size - index);

Sun JDK包的java/lang/System.java中的arraycopy()聲明如下：

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

arraycopy()是個JNI函數，它是在JVM中實現的。sunJDK中看不到源碼，不過可以在OpenJDK包中看到的源碼。網上有對arraycopy()的分析說明，實際上，我們只需要了解： System.arraycopy(elementData, index, elementData, index + 1, size - index); 會移動index之后所有元素即可。這就意味著，ArrayList的add(int index, E element)函數，會引起index之后所有元素的改變！

綜上所述，LinkedList的插入刪除元素的效率比ArrayList的效率要高。

3.2、ArrayList的隨機訪問效率比LinkedList的效率要高

　　在LinkedList的源碼中我們可以看出：通過get(int index)獲取LinkedList第index個元素時。先是在雙向鏈表中找到要index位置的元素；找到之后再返回。
　　雖然雙向鏈表查找index位置的節點時，有一個加速動作：若index < 雙向鏈表長度的1/2，則從前向后查找; 否則，從后向前查找。但是ArrayList是通過動態數組實現的，本事上還是一個數組，通過get(int index)獲取ArrayList第index個元素時，直接返回數組中index位置的元素，而不需要像LinkedList一樣進行查找。綜上所述，ArrayList的隨機訪問效率比LinkedList的效率要高

4、Arraylist和Vector的對比分析

4.1、兩者的相同之處

兩者都是List接口下的具體實現類，都繼承與AbstractList，并且實現了List接口
它們都實現了RandomAccess和Cloneable接口
它們都是通過數組實現的，本質上都是動態數組
它們的默認數組容量是10
它們都支持Iterator和listIterator遍歷

4.2、兩者的不同之處

線程安全性不同：ArrayList是非線程安全；而Vector是線程安全的，它的函數都是synchronized的，即都是支持同步的。ArrayList適用于單線程，Vector適用于多線程。
對序列化支持不同：ArrayList支持序列化，而Vector不支持；即ArrayList有實現java.io.Serializable接口，而Vector沒有實現該接口。
構造函數個數不同：ArrayList有3個構造函數，而Vector有4個構造函數。Vector除了包括和ArrayList類似的3個構造函數之外，另外的一個構造函數可以指定容量增加系數。
容量增加方式不同：逐個添加元素時，若ArrayList容量不足時，“新的容量”=“(原始容量x3)/2 + 1”。而Vector的容量增長與“增長系數有關”，若指定了“增長系數”，且“增長系數有效(即，大于0)”；那么，每次容量不足時，“新的容量”=“原始容量+增長系數”。若增長系數無效(即，小于/等于0)，則“新的容量”=“原始容量 x 2”。
對Enumeration的支持不同。Vector支持通過Enumeration去遍歷，而List不支持

總結

以上是生活随笔為你收集整理的List集合的总结和应用场景的介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

list
场景