java集合系列——List集合總結（六）

一.總結概述

1. List繼承了Collection，是有序的清單。
2. 實作類有ArrayList、LinkedList、Vector、Stack等
   • ArrayList是基于數組實作的，是一個數組隊列。可以動态的增加容量！
   • LinkedList是基于連結清單實作的，是一個雙向循環清單。可以被當做堆棧使用！
   • Vector是基于數組實作的，是一個矢量隊列，是線程安全的！
   • Stack是基于數組實作的，是棧，它繼承與Vector，特性是FILO（先進後出）！

二.使用場景

在實際的應用中如果使用到隊列，棧，連結清單，首先可以想到使用List。不同的場景下面使用不同的工具，效率才能更高！

1. 當集合中對插入元素資料的速度要求不高，但是要求快速通路元素資料，則使用ArrayList！

2. 當集合中對通路元素資料速度不做要求不高，但是對插入和删除元素資料速度要求高的情況，則使用LinkedList！

3.當集合中有多線程對集合元素進行操作時候，則使用Vector！但是現在BVector現在一般不再使用，如需在多線程下使用，可以用CopyOnWriteArrayList，在java.util.concurrent包下。

4.當集合中有需求是希望後儲存的資料先讀取出來，則使用Stack！

三.性能測試

/*
 * @author 阿飛
 * 性能測試，通過插入、随機讀取和删除對ArrayList、LinkedList、Vector和Stack進行測試！
 * 結論：看LinkedList
 *  插入10萬個元素，LinkedList所花時間最短：17 ms。
 *  删除10萬個元素，LinkedList所花時間最短： 9 ms。
 *  周遊10萬個元素，LinkedList所花時間最長：10255 ms；而ArrayList、Stack和Vector則相差不多，都隻用了幾秒。
 *  (1) 對于需要快速插入，删除元素，應該使用LinkedList。
 *  (2) 對于需要快速随機通路元素，應該使用ArrayList。
 * 
 */
public class ListTest {

    private static final int COUNT = ; //十萬

    private static ArrayList<Object> arrayList = new ArrayList<Object>();
    private static LinkedList<Object> linkedList = new LinkedList<Object>();
    private static Vector<Object> vector = new Vector<Object>();
    private static Stack<Object> stack = new Stack<Object>();

    public static void main(String[] args) {
        System.out.println("....開始測試插入元素..........");

        // 插入元素測試
        insertData(arrayList,"ArrayList") ;
        insertData(linkedList,"LinkedList") ;
        insertData(vector,"Vector") ;
        insertData(stack,"Stack") ;

        System.out.println("....開始測試讀取元素..........");

        // 随機讀取元素測試
        readAccessData(arrayList,"ArrayList") ;
        readAccessData(linkedList,"LinkedList") ;
        readAccessData(vector,"Vector") ;
        readAccessData(stack,"Stack") ;

        System.out.println("....開始測試删除元素..........");

        // 随機讀取元素測試
        deleteData(arrayList,"ArrayList") ;
        deleteData(linkedList,"LinkedList") ;
        deleteData(vector,"Vector") ;
        deleteData(stack,"Stack") ;



    }


    /**
     * 指定的List 的子類中插入元素，并統計插入的時間
     * @param list List 的子類
     * @param name 子類的名稱
     */
    private static void insertData(List<Object> list,String name) {
        long startTime = System.currentTimeMillis();

        // 向list的位置0插入COUNT個數
        for (int i=; i<COUNT; i++){
            list.add(, i);
        }

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(name + " : 插入 "+COUNT+"元素， 使用的時間是 " + interval+" ms");
    }

    /**
     * 指定的List 的子類中删除元素，并統計删除的時間
     * @param list List 的子類
     * @param name 子類的名稱
     */
    private static void deleteData(List<Object> list,String name) {
        long startTime = System.currentTimeMillis();

        // 删除list第一個位置元素
        for (int i=; i<COUNT; i++)
            list.remove();

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(name + " : 删除 "+COUNT+"元素， 使用的時間是 " + interval+" ms");
    }

    /**
     * 指定的List 的子類中讀取元素，并統計讀取的時間
     * @param list List 的子類
     * @param name 子類的名稱
     */
    private static void readAccessData(List<Object> list,String name) {
        long startTime = System.currentTimeMillis();

        // 讀取list元素
        for (int i = ; i < COUNT; i++)
            list.get(i);

        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(name + " : 随機讀取 "+COUNT+"元素， 使用的時間是 " + interval+" ms");
    }
}
           

運作結果：

....開始測試插入元素..........
ArrayList : 插入 元素， 使用的時間是  ms
LinkedList : 插入 元素， 使用的時間是  ms
Vector : 插入 元素， 使用的時間是  ms
Stack : 插入 元素， 使用的時間是  ms
....開始測試讀取元素..........
ArrayList : 随機讀取 元素， 使用的時間是  ms
LinkedList : 随機讀取 元素， 使用的時間是  ms
Vector : 随機讀取 元素， 使用的時間是  ms
Stack : 随機讀取 元素， 使用的時間是  ms
....開始測試删除元素..........
ArrayList : 删除 元素， 使用的時間是  ms
LinkedList : 删除 元素， 使用的時間是  ms
Vector : 删除 元素， 使用的時間是  ms
Stack : 删除 元素， 使用的時間是  ms
           

4.分析ArrayList和LinkedList運作結果

從運作的結果可以看出，ArrayList和LinkedLis适用各自的場景中！

為什麼ArrayList讀取速度快于LinkedList，而插入和删除速度又慢于LinkedList？

前面章節分析了這兩個類的源碼！

（1）ArrayList随機讀取的時候采用的是get(index),根據指定位置讀取元素，而LinkedList則采用size/2 ,二分法去加速一次讀取元素！

源代碼如下：

ArrayList：

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
 }
 E elementData(int index) {
        return (E) elementData[index];//直接通過數組的下标來讀取元素
    }
           

LinkedList：

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> )) {
            Node<E> x = first;
            for (int i = ; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - ; i > index; i--)
                x = x.prev;
            return x;
        }
    }
           

（2）ArrayList插入時候要判斷容量，删除時候要将數組移位，有一個複制操作！而LinkedList直接插入，不用判斷容量，删除的時候也是直接删除跳轉指針節點，沒有複制的操作！

源代碼如下：

ArrayList：

public boolean add(E e) {
        ensureCapacityInternal(size + );  // 判斷是否要增容
        elementData[size++] = e;
        return true;
    }
           

LinkedList：

public boolean add(E e) {
        linkLast(e);
        return true;
    }

  void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
           

java集合系列——java集合概述（一）

java集合系列——List集合之ArrayList介紹（二）

java集合系列——List集合之LinkedList介紹（三）

java集合系列——List集合之Vector介紹（四）

java集合系列——List集合之Stack介紹（五）

java集合系列——List集合總結（六）

java集合系列——Map介紹（七）

java集合系列——Map之HashMap介紹（八）

java集合系列——Map之TreeMap介紹（九）

java集合系列——Set之HashSet和TreeSet介紹（十）

如果帥氣（美麗）、睿智（聰穎），和我一樣簡單善良的你看到本篇博文中存在問題，請指出，我虛心接受你讓我成長的批評，謝謝閱讀！

祝你今天開心愉快！

歡迎通路我的csdn部落格，我們一同成長！

“不管做什麼，隻要堅持下去就會看到不一樣！在路上，不卑不亢!”

部落格首頁：http://blog.csdn.net/u010648555