ArrayList详解

àì夳堔傛蜴生んèń 2022-08-21 02:19 124阅读 0赞

1、简介

ArrayList是Java集合框架中的一个重要的类，它继承于AbstractList，实现了List接口，是一个长度可变的集合，提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了RandomAccess接口，可以对元素进行快速访问。实现了Serializable接口，说明ArrayList可以被序列化，还有Cloneable接口，可以被复制。和Vector不同的是，ArrayList不是线程安全的。

下图是ArrayList的结构层次：

![20160311083300211][]

2、主要方法详解

ArrayList底层使用的是Java数组来存储集合中的内容，这个数组是Object类型的：

transient Object[] elementData;

同时，elementData的访问级别为包内私有，是为了使内部类能够访问到其中的元素。

使用int类型的size表示数组中元素的个数：

private int size;

为了对应不同的构造函数，ArrayList使用了不同的数组：

/**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

代码中有个常量，表示数组的默认容量，大小为10：

/**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;

（1）构造函数

常量EMPTY\_ELEMENTDATA和DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA是为了初始化elementData的。如果为无参构造函数，使用DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA；如果为含参构造函数，使用EMPTY\_ELEMENTDATA：

public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

使用上述构造函数，elementData中没有元素，size为0，不过elementData的长度有可能不同。

ArrayList还提供了使用集合构造的构造函数：

public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

函数首先将集合c转化为数组，然后检查转化的类型，如果不是Object\[\]类型，使用Arrays类中的copyOf方法进行复制；同时，如果c中没有元素，使用EMPTY\_ELEMENTDATA初始化。

（2）trimToSize()

由于表示集合中元素个数的size和表示集合容量的elementData.length可能不同，在不太需要增加集合元素的情况下容量有浪费，可以使用trimToSize方法减小elementData的大小。代码如下：

public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

代码中有个modCount，这个是继承自AbstractList中的字段，表示数组修改的次数，数组每修改一次，就要增加modCount。可以看到，ArrayList的底层使用Object\[\]类型的数组存储内容，使用Arrays类来处理数组中的内容。

（3）ensureCapacity(int minCapacity)

这个方法可以用来保证数组能够包含给定参数个元素，也就是说如果需要的话可以扩大数组的容量。主要代码：

public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }

首先检查是不是DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，如果是的话，说明长度为10，如果不是，将minExpand设为0，比较与minCapacity的大小，然后调用私有函数进行操作：

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }

首先minCapacity和默认大小（10）比较，如果需要扩大容量，继续调用：

private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

然后比较minCapacity和当前长度的大小，如果需要扩容，调用grow方法：

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

这里，首先增加容量为原来的1.5倍，如果还不够，就用给定的容量minCapacity。同时，ArrayList设置了数组的最大长度MAX\_ARRAY\_SIZE = Integer.MAX\_VALUE - 8，如果没超出，使用Arrays类进行复制，不够的元素使用null。如果超出最大长度，调用函数检查是否溢出：

private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

如果没有溢出就得到合适的minCapacity值，然后复制。

（4）size()

函数返回集合中元素的数量：

public int size() {
            return size;
        }

（5）isEmpty()

函数返回集合是否为空，检查size是否为0，即使容量不为0（没有元素）：

public boolean isEmpty() {
            return size == 0;
        }

（6）contains(Object o)

检查集合中是否包含给定的元素：

public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }

使用indexOf方法，如果返回值非负，表示集合中函数这个元素。

（7）indexOf(Object o)

函数返回集合中给定元素的第一次出现的位置，如果没有就返回-1：

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

首先检查o是否为null，如果为null，就返回集合中第一个null元素的位置；如果不为null，就是用equals函数进行相等性检查。之所以这样，是因为如果直接对null调用equals方法，会抛出空指针异常。同时也不能循环遍历数组中的元素调用equals方法检查是否相等，因为ArrayList集合中允许有null元素的存在。

（8）lastIndexOf(Object o)

函数返回给定元素最后一次出现的位置，如果没有就返回-1：

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

原理和indexOf一样，不过对集合元素遍历的时候是倒序遍历的。

（9）clone()

复制集合：

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

本质上就是使用Arrays类进行元素的复制。

（10）toArray()

将集合转化为数组：

public Object[] toArray() {
            return Arrays.copyOf(elementData, size);
        }

也是使用Arrays的复制操作。

（11）toArray(T\[\] a)

转化为数组，和上一个不同的是，上一个返回的数组是Object\[\]类型的，这个函数返回的数组类型根据参数确定：

@SuppressWarnings("unchecked")
        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;
        }

（12）get(int index)

返回指定位置的元素，这里用到了一个私有函数：

@SuppressWarnings("unchecked")
        E elementData(int index) {
            return (E) elementData[index];
        }

函数返回数组中指定位置的元素，不过这个函数没有进行下标范围检查，这个工作由另一个私有函数完成：

private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

对于get方法来说，首先调用rangeCheck检查下标，然后调用elementData返回元素：

public E get(int index) {
            rangeCheck(index);
    
    
            return elementData(index);
        }

（13）set(int index,E element)

设置给定位置的元素为给定的元素，然后返回原来的元素：

public E set(int index, E element) {
            rangeCheck(index);
    
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

同样，函数也先进行下标检查。

（14）add(E e)

添加元素：

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

首先确保有足够的容量，然后再末尾添加元素。

（15）add(int index,E element)

在指定位置添加元素：

public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

（16）remove(int index)

删除指定位置的元素，然后返回这个元素：

public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

（17）remove(Object o)

删除指定的元素，如果集合中有，则删除第一次出现的并返回true；如果没有，集合不变并返回false：

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

在找到集合中的元素后，函数调用私有方法fastRemove来删除这个元素：

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; // clear to let GC do its work
        }

（18）clear()

清空集合，将所有元素设为null，并把size设为0：

public void clear() {
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

（19）addAll(Collection<? extends E> c)

添加给定集合中的所有元素到集合中，从末尾开始添加：

public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

首先把c集合转为数组，然后确保容量，最后复制。

（20）add(int index,Collection<? extends E> c)

在指定位置开始添加指定集合中的所有元素：

public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(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);
            size += numNew;
            return numNew != 0;
        }

原理和上一个一样，不同的是复制的位置。

（21）removeRange(int fromIndex,int toIndex)

删除给定范围内的所有元素：

protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
    
            // clear to let GC do its work
            int newSize = size - (toIndex-fromIndex);
            for (int i = newSize; i < size; i++) {
                elementData[i] = null;
            }
            size = newSize;
        }

（22）removeAll和retainAll

这两个函数都给一个集合参数c，removeAll删除集合中所有在集合c中出现过的元素；retainAll保留所有在集合c中出现的元素。两个函数都调用私有函数batchRemove()：

public boolean removeAll(Collection<?> c) {
            Objects.requireNonNull(c);
            return batchRemove(c, false);
        }
    
        public boolean retainAll(Collection<?> c) {
            Objects.requireNonNull(c);
            return batchRemove(c, true);
        }

batchRemove函数如下：

private boolean batchRemove(Collection<?> c, boolean complement) {
            final Object[] elementData = this.elementData;
            int r = 0, w = 0;
            boolean modified = false;
            try {
                for (; r < size; r++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
                // Preserve behavioral compatibility with AbstractCollection,
                // even if c.contains() throws.
                if (r != size) {
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                if (w != size) {
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }

函数对集合中的元素进行遍历，首先复制集合中的元素，然后检查是否符合complement的要求进行保留。在finally中，复制元素到集合中。并修改相应的size。

（23）ListIterator<E> listIterator()和ListIterator<E> listIterator(int index)

这两个函数返回在集合上的一个迭代器，不同是第一个是关于所有元素的，第二个是从指定位置开始的。这里ArrayList使用了内部类ListItr，

public ListIterator<E> listIterator(int index) {
            if (index < 0 || index > size)
                throw new IndexOutOfBoundsException("Index: "+index);
            return new ListItr(index);
        }
    
        public ListIterator<E> listIterator() {
            return new ListItr(0);
        }

（24）Iterator<E> iterator()

也返回一个迭代器，使用了内部类Itr，继承于ListItr：

public Iterator<E> iterator() {
            return new Itr();
        }

（25）List<E> subList(int fromIndex, int toIndex)

返回一个从fromIndex到toIndex的子集合：

public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new SubList(this, 0, fromIndex, toIndex);
        }

使用了内部类SubList。

3、例子

三种遍历方式：

<span style="white-space:pre">	</span>Integer[] nums={2,1,3,6,0,4,5,8,7,9};
    	List<Integer> list=new ArrayList<>();
    <span style="white-space:pre">	</span>list=Arrays.asList(nums);
    	//使用RandomAccess方式：
    	System.out.println("#1:");
    	for(int i=0;i<list.size();i++)
    	{
    		System.out.print((int)list.get(i));
    	}
    	//使用foreach：
    	System.out.println("\n#2:");
    	for (Integer integer : list) {
    		System.out.print(integer);
    	}
    	//使用Iterator：
    	System.out.println("\n#3:");
    	Iterator<Integer> it=list.iterator();
    	while(it.hasNext())
    	{
    		System.out.print((int)it.next());
    	}

结果：

\#1:  
2136045879  
\#2:  
2136045879  
\#3:  
2136045879

[20160311083300211]: /images/20220731/8325c8153c66407f97e07888ed8dd17b.png