Java提高篇（三二）-----List總結

        前面LZ已經充分介紹了大部分關於List介面的知識，如ArrayList、LinkedList、Vector、Stack，透過這幾個知識點可以對List介面有了比較深的了解了。只有透過歸納總結的知識才是你的知識。所以下面LZ就List介面做一個總結。建議閱讀：

        java java提高篇（二二）-----LinkedList

        java提高篇（二九）-----Vector

一、List介面概述

        List介面，成為有序的Collection也就是序列。此介面可以對清單中的每一個元素的插入位置進行精確的控制，同時使用者可以根據元素的整數索引（在清單中的位置）存取元素，並蒐索清單中的元素。 下圖是List介面的架構圖：

       
       

Collection：

Collection 層級結構中的根介面。它表示一組對象，這些對像也稱為 collection 的元素。對於Collection而言，它不提供任何直接的實現，所有的實現全部都由它的子類別負責。

        AbstractCollection：

提供 Collection 介面的骨幹實現，以最大限度地減少了實現此介面所需的工作。對於我們而言要實作一個不可修改的 collection，只需擴展此類，並提供 iterator 和 size 方法的實作。但要實作可修改的 collection，就必須另外重寫此類別的 add 方法（否則，會拋出 UnsupportedOperationException），iterator 方法傳回的迭代器還必須另外實作其 remove 方法。

        terator：

迭代器。

        ListIterator：

系列表迭代器，允許程式設計師按任何方向遍歷列表、迭代期間修改列表，並在列表中的當前位置。

        List：

繼承於Collection的介面。它代表有序的隊列。

        AbstractList：

List 介面的骨幹實現，以最大限度地減少實現「隨機存取」資料儲存（如數位

List 介面的骨幹實現，以最大限度地減少實現「隨機存取」資料儲存（如數組）支援的該介面所需的工作。         Queue：

隊列。提供隊列基本的插入、取得、檢查操作。

        Deque：一個線性 collection，支援在兩端插入和移除元素。大多數 Deque 實作對於它們能夠包含的元素數沒有固定限制，但此介面既支援有容量限制的雙端佇列，也支援沒有固定大小限制的雙端佇列。

        AbstractSequentialList：從某種意義上說，此類與在列表的列表迭代器上實現“隨機訪問”方法。

        LinkedList：List 介面的連結清單實作。它實作所有可選的列表操作。

        ArrayList：List 介面的大小可變數組的實作。它實現了所有可選列表操作，並允許包括 null 在內的所有元素。除了實作 List 介面外，此類還提供一些方法來操作內部用來儲存清單的陣列的大小。

        Vector：實現可成長的物件陣列。與陣列一樣，它包含可以使用整數索引進行存取的元件。

        Stack：後進先出（LIFO）的物件堆疊。它透過五個操作對類別 Vector 進行了擴展 ，允許將向量視為堆疊。

        Enumeration：枚舉，實現了該介面的對象，它產生一系列元素，一次產生一個。連續呼叫 nextElement 方法將傳回一系列的連續元素。

二、使用場景

           每個知識點都有它的使用範圍。集合也是如此，在Java中集合的家族非常龐大，每個成員都有最適合的使用場景。在剛接觸List時，LZ就說過如果涉及「堆疊」、「佇列」、「鍊錶」等操作，請優先考慮用List。

至於是那個List則分如下：

       

1、需要快速插入、刪除元素，則需使用LinkedList。

       

2、需要快速存取元素，則需使用ArrayList。

       

3、對於“單線程環境”或“多線程環境，但是List僅被一個線程操作”，需要考慮使用非同步的類，如果是“多線程環境，切List可能同時被多個線程操作”，考慮使用同步的類別（如Vector）。

2.1ArrayList、LinkedList效能分析

2.1ArrayList、LinkedList效能分析

        在List中我們使用最普遍的是LinkedList和ArrayList，同時我們也了解了他們兩者之間的差異和場景。

public class ListTest {
    private static final int COUNT = 100000;
    
    private static ArrayList arrayList = new ArrayList<>();
    private static LinkedList linkedList = new LinkedList<>();
    private static Vector vector = new Vector<>();
    
    public static void insertToList(List list){
        long startTime = System.currentTimeMillis();

        for(int i = 0 ; i < COUNT ; i++){
            list.add(0,i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("插入 " + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void deleteFromList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.remove(0);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("删除" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void readList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.get(i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("读取" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }

    private static String getName(List list) {
        String name = "";
        if(list instanceof ArrayList){
            name = "ArrayList";
        }
        else if(list instanceof LinkedList){
            name = "LinkedList";
        }
        else if(list instanceof Vector){
            name = "Vector";
        }
        return name;
    }
    
    public static void main(String[] args) {
        insertToList(arrayList);
        insertToList(linkedList);
        insertToList(vector);
        
        System.out.println("--------------------------------------");
        
        readList(arrayList);
        readList(linkedList);
        readList(vector);
        
        System.out.println("--------------------------------------");
        
        deleteFromList(arrayList);
        deleteFromList(linkedList);
        deleteFromList(vector);
    }
}

        運作結果:

🎜🎜🎜

插入 100000元素ArrayList花费 3900 毫秒
插入 100000元素LinkedList花费 15 毫秒
插入 100000元素Vector花费 3933 毫秒
--------------------------------------
读取100000元素ArrayList花费 0 毫秒
读取100000元素LinkedList花费 8877 毫秒
读取100000元素Vector花费 16 毫秒
--------------------------------------
删除100000元素ArrayList花费 4618 毫秒
删除100000元素LinkedList花费 16 毫秒
删除100000元素Vector花费 4759 毫秒

从上面的运行结果我们可以清晰的看出ArrayList、LinkedList、Vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, E element),delete、get方法各位如有兴趣可以研究研究。

首先我们先看三者之间的源码：

ArrayList

public void add(int index, E element) {
        rangeCheckForAdd(index);   //检查是否index是否合法

        ensureCapacityInternal(size + 1);  //扩容操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);    //数组拷贝
        elementData[index] = element;   //插入
        size++;
    }

rangeCheckForAdd、ensureCapacityInternal两个方法没有什么影响，真正产生影响的是System.arraycopy方法，该方法是个JNI函数，是在JVM中实现的。声明如下：

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

目前LZ无法看到源码，具体的实现不是很清楚，不过System.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着ArrayList的add(int index, E element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。

LinkedList

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)     //插入位置在末尾
            linkLast(element);
        else                   
            linkBefore(element, node(index));
    }

该方法比较简单，插入位置在末尾则调用linkLast方法，否则调用linkBefore方法，其实linkLast、linkBefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：

Node<E> node(int index) {
        if (index < (size >> 1)) {    //如果index 小于 size/2 则从头开始查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {   //如果index 大于 size/2 则从尾部开始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

所以linkedList的插入动作比ArrayList动作快就在于两个方面。1：linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

Vector

Vector的实现机制和ArrayList一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：

public void add(int index, E element) {
        insertElementAt(element, index);
    }
    
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

        上面是针对ArrayList、LinkedList、Vector三者之间的add（int index,E element)方法的解释，解释了LinkedList的插入动作要比ArrayList、Vector的插入动作效率为什么要高出这么多！至于delete、get两个方法LZ就不多解释了。

        同时LZ在写上面那个例子时发现了一个非常有趣的现象，就是linkedList在某些时候执行add方法时比ArrayList方法会更慢！至于在什么情况？为什么会慢LZ下篇博客解释，当然不知道这个情况各位是否也遇到过？？

2.2、Vector和ArrayList的区别

        四、更多

        java提高篇（二一）-----ArrayList

        java提高篇（二二）-----LinkedList

        java提高篇（二九）-----Vector

        Java提高篇（三一）-----Stack

---

以上是JavaList PHP中文網（www.php.cn）！