ArrayList源码解析

ArrayList是我们使用得最多的一个集合类之一

一般用来做包装DTO到view层来显示数据.

 

ArrayList继承了AbstractList类,实现了List,RandomAccess,Cloneable接口

 

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

内部结构是一个Object类型的数组

 

private transient Object[] elementData;

 ArrayList的大小，也就是元素个数

 

private int size;

 

下面是几个构造函数:

1.自定义初始化容量的构造函数:

 

 public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)//初始化容量不能小于0,抛出IllegalArgumentException异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];//根据参数初始化一个数组,底层是个object数组
    }

 2.默认构造函数:

调用上面的构造函数,默认初始化内部数组大小为10

 

    public ArrayList() {
	this(10);//默认初始容量是10
    }

 3.collection转换的构造函数:

 

    public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();//调用toArray()方法把collection转换成数组
	size = elementData.length;//把数组的长度赋值给ArrayList的size属性
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	if (elementData.getClass() != Object[].class)
	    elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

 返回ArrayList的大小:

 

    public int size() {
	 return size;
    }

 

判断是否为空:

 

    public boolean isEmpty() {
	return size == 0;//就是看当前size是否为0
    }

 找出一个元素第一次出现的下标:

 

    public int indexOf(Object o) {
    	//由于数组的下标是从0开始的，所以判断是否存在只要大于0就可以了
	if (o == null) {
	    for (int i = 0; i < size; i++)//注意这里是size属性而不是elementData的length
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = 0; i < size; i++)
		if (o.equals(elementData[i]))//equals方法来判断
		    return i;
	}
	return -1;//没有的话返回-1
    }

 

判断是否包含一个元素:

    public boolean contains(Object o) {
	return indexOf(o) >= 0;//不存在是-1
    }

 

元素最后一次出现的下标:

   public int lastIndexOf(Object o) {
	if (o == null) {
	    for (int i = size-1; i >= 0; i--)//注意这里的i是等于数组长度减1,从数组的最后一位开始
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = size-1; i >= 0; i--)
		if (o.equals(elementData[i]))
		    return i;
	}
	return -1;
    }

 重新分配ArrayList空间为元素多少的真实大小:

注意size一般和内部结构的数组长度是不一样的,通过上面的构造函数我们知道内部数组初始化容量是10,

而size是在add（）方法后才加一，这个方法是保证列表的大小和内部数组的大小一致

    public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }

 如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数

因为每次重新分配空间都是比较消耗时间的,所以如果能预计list可能的大小
的话可以通过自己的控制ArrayList的大小来提高效率

 public void ensureCapacity(int minCapacity) {//注意是public类型,也就是说可以我门自己来重新分配空间
modCount++;
int oldCapacity = elementData.length;//老的容量
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;//把当前数组临时保存起来
    int newCapacity = (oldCapacity * 3)/2 + 1;//加1是为了保证oldCapacity为1或者0的情况下
        if (newCapacity < minCapacity)//是按1.5被来增加容量的
    newCapacity = minCapacity;
           // minCapacity is usually close to size, so this is a win:
           elementData = Arrays.copyOf(elementData, newCapacity);
}
   }

 

clone一个副本:

 

    public Object clone() {
	try {
	    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();
	}
    }

 转换为数组:

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);//调用Arrays.copyOf()方法
    }

 下面是转换为泛型数组:

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 

范围检查:臭名昭著的 IndexOutOfBoundsException异常

    private void RangeCheck(int index) {
	if (index >= size)//数组越界,这里没有判断小于0的情况
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }

 通过下标得到一个元素:

 

    public E get(int index) {
	RangeCheck(index);//先检查是否越界

	return (E) elementData[index];//返回的是数组中的下标    }

 通过下标和一个元素赋值，返回的是原先的值:

    public E set(int index, E element) {
	RangeCheck(index);//先检查是否越界

	E oldValue = (E) elementData[index];//通过临时变量把当前下标的值保存
	elementData[index] = element;//赋值
	return oldValue;//注意返回的是当前下标的原先值
    }

 

添加一个新的元素到末尾,前面说道新增方法都要先调用ensureCapacity方法:

    public boolean add(E e) {
	ensureCapacity(size + 1); //大小加一 // Increments modCount!!
	elementData[size++] = e;//size默认是0所以是从0开始赋值
	return true;
    }

 API文档中的说明是:将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素（如果有）以及所有后续元素（将其索引加 1）。通俗的说法是在指定位置插入元素，指定元素和后面的元素后移

这个方法和set(int index, E element) 不一样,set只是把元素赋值给指定的下标同时返回下标的原先值.

add(int index, E element)的判断越界是通过元素的大小来判断的

所以如果

ArrayList list=new ArrayList();
list.add(1, 8);
//报错，因为size元素大小还是0
//如果l
list.add(0,"")//就可以

 

如果一致add同一下标所有后续元素索引加1

如下:

	ArrayList list=new ArrayList();
	list.add(0, 8);
	list.add(0, 8);
	list.add(0, 8);
	System.out.println(list);
	//结果为[8, 8, 8]

 

:

    public void add(int index, E element) {
	if (index > size || index < 0)//判断是否越界,注意这里是以元素的个数来判断的
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	//源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到
	//目标数组中的 destPos 到 destPos+length-1 位置
	elementData[index] = element;
	size++;//元素加一
    }

 删除指定位置的元素，返回被删除的元素，由于ArrayList采用一个对象数组存储元素，所以在删除一个元素时需要把后面的元素前移。删除一个元素时只是把该元素在elementData数组中的引用置为null，具体的对象的销毁由垃圾收集器负责

    public E remove(int index) {
	RangeCheck(index);//判断是否越界

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;//新的数组长度
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;//返回删除前的数据
    }

 内部删除方法,跳过越界检查,不返回删除元素的值:ArrayList内部调用的删除方法

   /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }

 删除指定元素:

    public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }

 清空列表:

    public void clear() {
	modCount++;

	// Let gc do its work
	for (int i = 0; i < size; i++)
	    elementData[i] = null;

	size = 0;//设定元素大小为0
    }

 

添加集合c中的元素到ArrayList的末尾，添加成功返回true，如果集合c为空，返回false。

   public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);//添加到列表的末尾
        size += numNew;
	return numNew != 0;
    }

 

在指定位置插入集合中的所有元素，和上面一个方法基本差不多，指定位置元素和以后的都要后移

 

    public boolean addAll(int index, Collection<? extends E> c) {
	if (index > size || index < 0)//判断越界 
	    throw new IndexOutOfBoundsException(
		"Index: " + index + ", Size: " + size);

	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount

	int numMoved = size - index;
	if (numMoved > 0)//两种情况
	    System.arraycopy(elementData, index, elementData, index + numNew,
			     numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);//这里是等于0的情况也就是说直接在数组后面加
	size += numNew;
	return numNew != 0;
    }

 

删除指定范围的元素

1. protected void removeRange(int fromIndex, int toIndex) {
   modCount++;
   int numMoved = size - toIndex;
          System.arraycopy(elementData, toIndex, elementData, fromIndex,
                           numMoved);
   
   // Let gc do its work
   int newSize = size - (toIndex-fromIndex);
   while (size != newSize)
       elementData[--size] = null;
      }

    

    

     

    

      结合API文档和网上搜索来的ArrayList的特效来总结下:

      API文档是如此介绍ArrayList的：

   接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

    Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差。

    

   List允许有相同的元素

   ArrayList的方法都没有同步，所以在多线程中是不安全的，必须自己同步

   toArray()方法返回的是和原列表相同的对象，也就是说:
   arrayList.toArray()[0]==arrayList.get(0)返回的是true(假定arrayList不空)。

   clone()方法是一个浅拷贝。

   API文档:

   在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量
   可以通过自己调用ensureCapacity()提高效率

   创建同步线程的ArrayList

   List list = Collections.synchronizedList(new ArrayList(...));

    

   ArrayList提供了4种添加方法:

   	list.add(e);
   	list.add(index, element);
   	list.addAll(c);
   	list.addAll(index, c);

    每次添加都调用ensureCapacity()方法,扩大容量是每次是1.5倍

    

   	list.set(index, element);
   	list.add(index, element);

    set是用指定的元素替代此列表中指定位置上的元素

   add是将指定的元素插入此列表中的指定位置。向右移动当前位于该位置的元素

    

   对于新增和删除操作add和remove,ArrayList要移动数据。所以性能不是很好

   而访问数据是直接根据数组下标来获得数据的，所以速度很快

    

    移除ArrayList内重复数据:

   	public static void removeDuplicate(List arlList) {
   		HashSet h = new HashSet(arlList);
   		arlList.clear();
   		arlList.addAll(h);
   	}

    除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个 ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。