摘要：概述列表是一款即實用又常用的數據結構，用來存儲線性結構的數據。在中對的支持主要有兩種，也是最常用的兩種。本文主要分析的源碼。的底層主要是基于鏈表來實現的。但是返回的卻沒有這樣的等同關系。那么其方法返回的只是一個類型的數組，而不是類型。

列表(list)是一款即實用又常用的數據結構，用來存儲線性結構的數據。在JDK中對List的支持主要有兩種，也是最常用的兩種。一種是ArrayList，一種是LinkedList。

而且這兩種list的區別也經常出現在節操公司的面試題中。節操高一點可能還會問某種list的具體實現，下面說說這兩種List的區別。本文主要分析ArrayList的源碼。

ArrayList

ArrayList的底層主要是基于數組來實現的。
眾所周知，數組是有get√到RandomAccess技能的，也就是說，array[index]這個操作的時間復雜度為O(1)。
但是，在數組上進行增刪操作，就需要比較費力了，往數組中插入一項，需要將其后面的所有項都向后移動一個單元，刪除數組的一項，則需要把后面的所有項都向前移動一位。
最好的情況下，你要插入或者刪除的那一項剛好位于數組的末端，那么就無需再移動任何數據。
所以，如果增刪操作比較多，則不應該選用基于數組實現的ArrayList。

LinkedList

LinkedList的底層主要是基于鏈表來實現的。
鏈表的優勢就是增刪操作不需要像ArrayList一樣拷貝數組(移動意味著拷貝)，只需要更改前后節點的引用。菊葛麗子，節點A和節點B中間需要插入一個節點C。一開始，A的后繼是B，B的前驅是A(不明白前驅后繼這兩個術語請查找數據結構方面的書)，要插入C時，只需要做以下幾個操作：

將A的后繼改為C

將C的前驅改為A

將C的后繼改為B

將B的前驅改為C。

刪除操作同理可推。
但是，LinkedList要進行隨機查找可就麻煩了，必須得先從鏈表的一端(從頭部或者尾部)開始找，我要查找第10個，它必須先找到第1個，然后第2個，... ，第9個，然后才是第十個。因此，LinkedList適合增刪操作比較多的場景。
可以看看JDK源碼中LinkedList的訪問函數：

    Node node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

翻開ArrayList的源碼，可以看到其中有一個clone()方法，用于克隆當前ArrayList實例。
其方法實現如下：

    /**
     * Returns a shallow copy of this ArrayList instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this ArrayList instance
     */
    public Object clone() {
        try {
            @SuppressWarnings("unchecked")
                ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn"t happen, since we are Cloneable
            throw new InternalError();
        }
    }

可以看到，先調用了super.clone()方法復制了一個全新的對象，并把它賦值給v。由于java.lang.Object.clone()只是一種淺復制，所以，v的elementData引用的還是當前ArrayList的elementData的引用，這就意味著，在v上做操作，會影響原來的ArrayList的值。這也是為什么需要再跟上這么一個語句的原因v.elementData = Arrays.copyOf(elementData, size);。這句話的作用是對原來ArrayList的elementData進行一個數組拷貝，然后賦值給v的elementData，這樣，v的elementData就是原先ArrayList的elementData的一個副本，不再是內存中同一塊數組。在v上的操作也不會影響到原先的ArrayList。這才是ArrayList的clone()方法真正想做的事情。

在ArrayList的構造函數中，可以看到有這樣一個構造函數：

    public ArrayList(Collection c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

這個構造函數用另外一個集合中的元素來構造ArrayList。
但是，注意到其中一句注釋
c.toArray might (incorrectly) not return Object[] (see 6260652)
說c的toArray()方法有可能不返回類型為Object[]的數組。并且，在jdk的bug列表中編號為6260652的bug可以找到解釋:

A DESCRIPTION OF THE PROBLEM :
The Collection documentation claims thatcollection.toArray()is "identical in function" tocollection.toArray(new Object[0]);
However, the implementation of Arrays.asList does not follow this: If created with an array of a subtype (e.g. String[]), its toArray() will return an array of the same type (because it use clone()) instead of an Object[].
If one later tries to store non-Strings (or whatever) in that array, an ArrayStoreException is thrown.
Either the Arrays.asList() implementation (which may return an array of component type not Object) or the Collection toArray documentation (which does not allow argumentless toArray() to return arrays of subtypes of Object) is wrong.

在Java中，數組是不具備有兼容性的，舉個例子：

    /**
     *
     *
     * @author Bean
     * @date 2015年7月15日 下午5:14:35
     * @version 1.0
     *
     */
    public class Box {
    
        public static void main(String[] args) {
            Object[] obj1 = new Object[1];
            obj1[0] = new Student();
            obj1[0] = new Person();
            
            Object[] obj2 = new Person[1];
            obj2[0] = new Person();
            obj2[0] = new Student();
            
            Object[] obj3 = new String[1];
            obj3[0] = new Person(); 
        }
    }
    
    class Person {
    }
    
    class Student extends Person {
    }

在main方法的最后一行將會拋出一個異常

Exception in thread "main" java.lang.ArrayStoreException: cn.com.beansoft.box.Person
    at cn.com.beansoft.box.Box.main(Box.java:34)

在Collection的API中，聲稱toArray()與toArray(new Object[0])方法是等同的。但是Arrays.asList返回的List卻沒有這樣的等同關系。其實在Arrays類中也有另外一個ArrayList類，只不過它是個內部類，Arrays.asList就是返回的這個內部的ArrayList。源碼如下所示:

    public static  List asList(T... a) {
        return new ArrayList<>(a);
    }

而這個內部的ArrayList，其toArray方法是調用clone來實現的。如下：

   public Object[] toArray() {
        return a.clone();
   }

所以，如果Arrays.asList(T... array)里面的T不是Object類型，而是String類型。那么其toArray方法返回的只是一個String[]類型的數組，而不是Object[]類型。

java.util.ArrayList這個類，本來就是個泛型類。如果它底層的數組類型不是Object[]類型，那么實現泛型存儲就是一件無法實現的事了。

上面所說的Java中數組是類型不兼容的，說白了就是在Java中我們可以這樣做：

    Object o = new Person();
    o = new String();

但是不能這樣做：

    Object[] obj3 = new String[1];
    obj3[0] = new Person();