概述

列表(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时，只需要做以下几个操作：

  1. 将A的后继改为C
  2. 将C的前驱改为A
  3. 将C的后继改为B
  4. 将B的前驱改为C。

  删除操作同理可推。
  但是，LinkedList要进行随机查找可就麻烦了，必须得先从链表的一端(从头部或者尾部)开始找，我要查找第10个，它必须先找到第1个，然后第2个，... ，第9个，然后才是第十个。因此，LinkedList适合增删操作比较多的场景。
  可以看看JDK源码中LinkedList的访问函数：

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

深拷贝与浅拷贝

翻开ArrayList的源码，可以看到其中有一个clone()方法，用于克隆当前ArrayList实例。
其方法实现如下：

    /**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone() {
        try {
            @SuppressWarnings("unchecked")
                ArrayList<E> v = (ArrayList<E>) 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()方法真正想做的事情。

toArray的坑

在ArrayList的构造函数中，可以看到有这样一个构造函数：

java    public ArrayList(Collection<? extends E> 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中，数组是不具备有兼容性的，举个例子：

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。源码如下所示:

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

而这个内部的ArrayList，其toArray方法是调用clone来实现的。如下：

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

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

java.util.ArrayList这个类，本来就是个泛型类。如果它底层的数组类型不是Object[]类型，那么实现泛型存储就是一件无法实现的事了。

上面所说的Java中数组是类型不兼容的，说白了就是在Java中我们可以这样做：

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

但是不能这样做：

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