ArrayList源码分析

凉白开

2020-04-11

ArrayList源码分析

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

ArrayList继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口

方法：

一、构造方法

1.无参构造

/**
     * 第一种、调用ArrayList(10)默认初始化一个大小为10的Object数组
     (DEFAULTCAPACITY_EMPTY_ELEMENTDATA=10)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

ArrayList()：构造一个厨师容量为10的空列表

2.有参构造

/**
     *第二种
     */
    public ArrayList(int initialCapacity) {
        //如果用户初始化大小小于0抛异常
		//否则新建一个用户初始值大小的Object数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

ArrayList( int initialCapcity )：构造一个具有初始容量值的空列表

/**
     * 第三种、将容器数组化处理并将这个数组值赋给Object数组
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //当c.toArray返回的不是Object类型的数组时，进行下面转化
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 用空数组替换
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList(Collection<?extend E> c)：构造一个包含指定元素的列表

二、增删改查操作

1.增加元素

//第一步：
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  
        elementData[size++] = e;
        return true;
    }
//第二步：
 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
//第三步：
 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 如果添加元素后大于当前数组的长度，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
//第四步：(扩容)
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //将数组的长度增加原来数组的一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果扩充一半后仍然不够，则newCapacity=minCapacity;(minCapacity实际元素的个数)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//第一步：
public void add(int index, E element) {
        rangeCheckForAdd(index);
		//检查index的值是否在0到size之间，可以为size。
        ensureCapacityInternal(size + 1);  //看elementData的长度是否足够，不够扩容
    	//将elementData从index开始后面的元素往后移一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//第二步：(多了判断index是否超出范围)
 private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
//第三步：
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
//第四步：(判断是否需要扩容)
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
     	// 如果添加元素后大于当前数组的长度，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
//第五步：(扩容)
   private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
       //将数组的长度增加原来数组的一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
       //如果扩充一半后仍然不够，则newCapacity=minCapacity;(minCapacity实际元素的个数)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add(E e)：添加一个元素到列表的末尾。
add( int index, E element ) :在指定的位置添加元素
addAll( Collection<? extends E> c )：添加一个集合到元素的末尾.以上返回类型是boolean
ensureCapcity（int minCapcity）：确保列表中含有minCapcity的最小容

2.删除元素

public E remove(int index) {
    	//第一步：如果index>=size抛出异常
        rangeCheck(index);
        modCount++;
    	//第二步：获取删除元素的值
        E oldValue = elementData(index);
		//第三步：将index后面所有元素往前移一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;
		//第四步：返回要删除的元素
        return oldValue;
    }

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

remove(Object o)：删除列表中第一个出现O的元素
removeAll（Collection<?> c）：删除列表中包含C的所有元素
removeIf（Predictcate<? super E> filter）：删除列表中给定谓词的所有元素
removeRange( int from,int to )：删除从from到to的所有元素
clear（）：清除所有的元素。返回类型为void

3.更改元素

//第一步：
public E set(int index, E element) {
    	//检查index是否小于size，如果不是抛异常
        rangeCheck(index);
        E oldValue = elementData(index);
    	//覆盖ArrayList中index上的元素
        elementData[index] = element;
    	//返回被覆盖的元素
        return oldValue;
}
//第二步：
private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//第一步：
public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
//第二步：
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

//1)修改次数加1
//2)强elementData中空余的空间(包括null值)去除，
//例如：数组长度为10，其中只有前三个元素有值，其他为空，那么调用该方法之后，数组长度变为3
public void trimToSize() {
    	//修改次数加1
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)? 
                EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
        }
    }

public Object[] toArray() {return Arrays.copyOf(elementData, size);}
//第一种方式(最常用)
Integer[] integer=arrayList.toArray(new Integer[0]);
//第二种方式(容易理解)
Integer[] integer=new Integer[arrayList.size()];
arrayList.toArray(integer);

retainAll( Collection<?> c )：仅仅保留列表中和C相同的元素，相当于&运算
set（int index,E element）：用element替换index位置上的元素。
size()：返回此列表的元素数
sort(Comparator<? super E> c)：按照指定的排序规则排序
subList( int from , int to )：返回从from到to之间的列表
toArray()：将列表转化为数组
trimToSize( )：修改当前实例的容量是列表的当前大小。

4.查元素

contains()

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

contains（Object o）：如果包含元素o,则返回为true
get（int index）:返回指定索引的元素
indexOf( Object o )：返回此列表中指定元素的第一次出现的索引，如果列表不包含此元素，返回-1
lastindexOf( Object o ):返回此列表中指定元素的最后一次出现的索引，如果列表不包含此元素，返回-1
isEmpty（）：如果列表为空，返回true.
iterator()：返回列表中元素的迭代器
listIterator（）：返回列表的列表迭代器（按适当的顺序）
listIterator(int index)：从适当的位置返回列表的列表迭代器（按照正确的顺序）

5.遍历元素

public class Test01 {
    public static void main(String[] args) {
        List<String> list1=new ArrayList<>();
        list1.add("A");
        list1.add("B");
        list1.add("C");
        
        //第一种遍历方式：迭代器
        Iterator<String> iterator=list1.iterator();
        while (iterator.hasNext()){
            String result=iterator.next();
            System.out.println(result);
        }
        
        //第二种遍历方式：通过下标遍历
        for (int i = 0; i < list1.size(); i++) {
            String result=list1.get(0);
            System.out.println(result);
        }
        //第三种遍历方式：for-each
        for (String a:list1) {
            System.out.println(a);
        }
    }
}

第二种遍历的效率是最高的。

三种方式时间差对比：

package com.woniu.chapter23;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @Author: Aweicy
 * @Date: 2020/4/110:33
 */
public class Test01 {
    public static void main(String[] args) {
        List<String> list1=new ArrayList<>();
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("A");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        list1.add("B");
        list1.add("C");
        Long time1=System.currentTimeMillis();
        //第一种遍历方式：迭代器
        Iterator<String> iterator=list1.iterator();
        while (iterator.hasNext()){
            String result=iterator.next();
            System.out.println(result);
        }
        Long time2=System.currentTimeMillis();
        System.out.println(time2-time1);
        Long time3=System.currentTimeMillis();
        //第二种遍历方式：通过下标遍历
        for (int i = 0; i < list1.size(); i++) {
            String result=list1.get(0);
            System.out.println(result);
        }
        Long time4=System.currentTimeMillis();
        System.out.println(time4-time3);
        Long time5=System.currentTimeMillis();
        //第三种遍历方式：for-each
        for (String a:list1) {
            System.out.println(a);
        }
        Long time6=System.currentTimeMillis();
        System.out.println(time6-time5);
    }
}

5毫秒
3毫秒
5毫秒

三、与LinkList、Vector对比区别

分析得出下面结论：

ArrayList 本质上是一个可改变大小的数组.当元素加入时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问.元素顺序存储 ,随机访问很快，删除非头尾元素慢，新增元素慢而且费资源 ,较适用于无频繁增删的情况 ,比数组效率低，如果不是需要可变数组，可考虑使用数组 ,非线程安全.
LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于ArrayList. 适用于：没有大规模的随机读取，有大量的增加/删除操作.随机访问很慢，增删操作很快，不耗费多余资源 ,允许null元素,非线程安全.
Vector （类似于ArrayList）但其是同步的，开销就比ArrayList要大。如果你的程序本身是线程安全的，那么使用ArrayList是更好的选择。 Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%.

四、总结

ArrayList总体来说比较简单，不过ArrayList还有以下一些特点：

ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了private void writeObject(java.io.ObjectOutputStream s)、private void readObject(java.io.ObjectInputStream s) 方法
ArrayList基于数组方式实现，无容量的限制（会扩容）
添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
线程不安全，会出现fall-fail。
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)
remove(Object o)需要遍历数组
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
contains(E)需要遍历数组
使用iterator遍历可能会引发多线程异常