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

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

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

ArrayList

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

LinkedList

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

將A的后繼改為C

將C的前驅(qū)改為A

將C的后繼改為B

將B的前驅(qū)改為C。

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

    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()方法，用于克隆當(dāng)前ArrayList實例。
其方法實現(xiàn)如下：

    /**
     * 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();
        }
    }

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

在ArrayList的構(gòu)造函數(shù)中，可以看到有這樣一個構(gòu)造函數(shù)：

    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);
    }

這個構(gòu)造函數(shù)用另外一個集合中的元素來構(gòu)造ArrayList。
但是，注意到其中一句注釋
c.toArray might (incorrectly) not return Object[] (see 6260652)
說c的toArray()方法有可能不返回類型為Object[]的數(shù)組。并且，在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中，數(shù)組是不具備有兼容性的，舉個例子：

    /**
     *
     *
     * @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卻沒有這樣的等同關(guān)系。其實在Arrays類中也有另外一個ArrayList類，只不過它是個內(nèi)部類，Arrays.asList就是返回的這個內(nèi)部的ArrayList。源碼如下所示:

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

而這個內(nèi)部的ArrayList，其toArray方法是調(diào)用clone來實現(xiàn)的。如下：

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

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

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

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

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

但是不能這樣做：

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