Java ArrayList学习笔记

曾经终败给现在 2022-07-14 12:43 160阅读 0赞

## 前言 ##

最近我在学习Java基础，发现经常使用的ArrayList比较重要，所以特地做一个笔记以备查阅。笔记会参考很多前辈的文章（附链接），并且这篇笔记将会逐步更新。（本文参考的是Java 1.8.0\_45版本）

## 定义 ##

官方文档的定义：

> Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

翻译：  
它是List接口的一种可变数组的实现。实现了所有可选的list操作，并且允许包含所有的元素，包括null。除了实现了List接口，这个类提供了方法去操作在内部使用去存储list的数组的大小。（这个类大题与Vector相同，除了它是非同步的。）

ArrayList是最常用的数据结构之一了。它在 [关于Java集合的小抄][Java]里的描述(节选)：

> ArrayList超出限制时会增加50%容量，用System.arraycopy（）复制到新的数组。默认第一次插入元素时创建大小为10的数组。  
> 按数组下标访问元素－get（i）、set（i,e） 的性能很高。  
> 如果按下标插入元素、删除元素－add（i,e）、 remove（i）、remove（e），则要用System.arraycopy（）来复制移动部分受影响的元素，性能就变差了。  
> 越是前面的元素，修改时要移动的元素越多。直接在数组末尾加入元素－常用的add（e），删除最后一个元素则无影响。

关于自动扩容

> 当数组容量不够用时，创建一个比原数组容量大的新数组，将数组中的元素转移到新数组，再将新的元素也放入新数组，最后将新数组赋给原数组即可。

## 主要函数 ##

### 构造函数 ###

代码如下：

/** * Constructs a new instance of {@code ArrayList} with the specified * initial capacity. * * @param capacity * the initial capacity of this {@code ArrayList}. */
        public ArrayList(int capacity) {
            if (capacity < 0) {
                throw new IllegalArgumentException("capacity < 0: " + capacity);
            }
            array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
        }
    
        /** * Constructs a new {@code ArrayList} instance with zero initial capacity. */
        public ArrayList() {
            array = EmptyArray.OBJECT;
        }
    
        /** * Constructs a new instance of {@code ArrayList} containing the elements of * the specified collection. * * @param collection * the collection of elements to add. */
        public ArrayList(Collection<? extends E> collection) {
            if (collection == null) {
                throw new NullPointerException("collection == null");
            }
    
            Object[] a = collection.toArray();
            if (a.getClass() != Object[].class) {
                Object[] newArray = new Object[a.length];
                System.arraycopy(a, 0, newArray, 0, a.length);
                a = newArray;
            }
            array = a;
            size = a.length;
        }

如上面代码所示，ArrayList有三个构造函数。  
第一个构造函数的参数是容量，当参数为0的时候，形成一个容量为0的Object数组；否则生成一个容量为参数的Object数组。  
第二个就是我们常见的，不做赘述。  
第三个构造函数的参数是collection相关类，首先声明局部变量a为当前对象toArray的值（返回当前容器中的所有元素，以数组的形式），如果当前局部变量a的类型正好是Object\[\]类的话，那么就直接进行赋值操作；否则就进行System.arraycopy操作，System.arraycopy操作把a数组中的元素全部拷贝到了newArray（类型为Object\[\]）里，然后同样进行赋值操作。

### add函数 ###

代码如下：

/** * Adds the specified object at the end of this {@code ArrayList}. * * @param object * the object to add. * @return always true */
        @Override public boolean add(E object) {
            Object[] a = array;
            int s = size;
            if (s == a.length) {
                Object[] newArray = new Object[s +
                        (s < (MIN_CAPACITY_INCREMENT / 2) ?
                         MIN_CAPACITY_INCREMENT : s >> 1)];
                System.arraycopy(a, 0, newArray, 0, s);
                array = a = newArray;
            }
            a[s] = object;
            size = s + 1;
            modCount++;
            return true;
        }
    
        /** * Inserts the specified object into this {@code ArrayList} at the specified * location. The object is inserted before any previous element at the * specified location. If the location is equal to the size of this * {@code ArrayList}, the object is added at the end. * * @param index * the index at which to insert the object. * @param object * the object to add. * @throws IndexOutOfBoundsException * when {@code location < 0 || location > size()} */
        @Override public void add(int index, E object) {
            Object[] a = array;
            int s = size;
            if (index > s || index < 0) {
                throwIndexOutOfBoundsException(index, s);
            }
    
            if (s < a.length) {
                System.arraycopy(a, index, a, index + 1, s - index);
            } else {
                // assert s == a.length;
                Object[] newArray = new Object[newCapacity(s)];
                System.arraycopy(a, 0, newArray, 0, index);
                System.arraycopy(a, index, newArray, index + 1, s - index);
                array = a = newArray;
            }
            a[index] = object;
            size = s + 1;
            modCount++;
        }

从代码中可以看出，ArrayList类重载了两个add函数。  
第一个add函数的参数是需要被add的元素。它的作用是把当前这个元素添加到数组的尾端。在函数体内，size是ArrayList中元素的数量，a.length是当前数组的长度。如果size与a.length不相同，也就是size < a.length，那么就直接插入到数组的末尾。当size==a.length的时候，也就是ArrayList已经放满了，那么它就需要扩容。在上面的代码中，执行的是

Object[] newArray = new Object[s + (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];

在这里新建了一个数组newArray，它的容量是这样设置的：如果当前数组的长度小于MIN\_CAPACITY\_INCREMENT（常量）的一半，那么就扩容使新容量为原来的容量加上MIN\_CAPACITY\_INCREMENT的值；否则扩容为原来容量的1.5倍。

第二个add函数是把某个元素插入到特定的位置，就不再赘述了（代码如上）。但是在这里加一句：当当前元素的数量小于数组的长度时，插入也是很麻烦的，要把整个数组从index往后的元素全部向后移一位。所以ArrayList的插入效率应该是不高的。

### newCapacity函数 ###

在上文可以看出，newCapacity函数就是负责进行扩容的，它的作用应该与

Object[] newArray = new Object[s + (s < (MIN_CAPACITY_INCREMENT / 2) ?MIN_CAPACITY_INCREMENT : s >> 1)];

相似，其代码如下：

private static int newCapacity(int currentCapacity) {
            int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
                    MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
            return currentCapacity + increment;
        }

不知道为什么上一块代码为何不直接引用newCapacity函数~  
newCapacity函数解析应该和add中的某一段一样：如果当前数组的长度小于MIN\_CAPACITY\_INCREMENT（常量）的一半，那么就扩容使新容量为原来的容量加上MIN\_CAPACITY\_INCREMENT的值；否则扩容为原来容量的1.5倍。

### addAll函数 ###

/** * Adds the objects in the specified collection to this {@code ArrayList}. * * @param collection * the collection of objects. * @return {@code true} if this {@code ArrayList} is modified, {@code false} * otherwise. */
        @Override public boolean addAll(Collection<? extends E> collection) {
            Object[] newPart = collection.toArray();
            int newPartSize = newPart.length;
            if (newPartSize == 0) {
                return false;
            }
            Object[] a = array;
            int s = size;
            int newSize = s + newPartSize; // If add overflows, arraycopy will fail
            if (newSize > a.length) {
                int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
                Object[] newArray = new Object[newCapacity];
                System.arraycopy(a, 0, newArray, 0, s);
                array = a = newArray;
            }
            System.arraycopy(newPart, 0, a, s, newPartSize);
            size = newSize;
            modCount++;
            return true;
        }
    
        /** * Inserts the objects in the specified collection at the specified location * in this List. The objects are added in the order they are returned from * the collection's iterator. * * @param index * the index at which to insert. * @param collection * the collection of objects. * @return {@code true} if this {@code ArrayList} is modified, {@code false} * otherwise. * @throws IndexOutOfBoundsException * when {@code location < 0 || location > size()} */
        @Override
        public boolean addAll(int index, Collection<? extends E> collection) {
            int s = size;
            if (index > s || index < 0) {
                throwIndexOutOfBoundsException(index, s);
            }
            Object[] newPart = collection.toArray();
            int newPartSize = newPart.length;
            if (newPartSize == 0) {
                return false;
            }
            Object[] a = array;
            int newSize = s + newPartSize; // If add overflows, arraycopy will fail
            if (newSize <= a.length) {
                 System.arraycopy(a, index, a, index + newPartSize, s - index);
            } else {
                int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
                Object[] newArray = new Object[newCapacity];
                System.arraycopy(a, 0, newArray, 0, index);
                System.arraycopy(a, index, newArray, index + newPartSize, s-index);
                array = a = newArray;
            }
            System.arraycopy(newPart, 0, a, index, newPartSize);
            size = newSize;
            modCount++;
            return true;
        }

同样是重载了两个addAll的函数。  
第一个addAll函数把一个Collection对象的元素插入到数组的后面。基本原理与add其实很类似。  
第二个addAll函数也不再赘述。

### get函数与set函数 ###

代码如下：

@SuppressWarnings("unchecked") @Override public E get(int index) {
            if (index >= size) {
                throwIndexOutOfBoundsException(index, size);
            }
            return (E) array[index];
        }

/** * Replaces the element at the specified location in this {@code ArrayList} * with the specified object. * * @param index * the index at which to put the specified object. * @param object * the object to add. * @return the previous element at the index. * @throws IndexOutOfBoundsException * when {@code location < 0 || location >= size()} */
        @Override public E set(int index, E object) {
            Object[] a = array;
            if (index >= size) {
                throwIndexOutOfBoundsException(index, size);
            }
            @SuppressWarnings("unchecked") E result = (E) a[index];
            a[index] = object;
            return result;
        }

get函数很直接，因为是ArrayList是数组，其实直接通过索引取值即可。  
set函数同样是通过索引改变相应元素的内容。  
所以可以看出ArrayList的存取效率应该是非常快的。

### remove函数 ###

代码如下：

/** * Removes the object at the specified location from this list. * * @param index * the index of the object to remove. * @return the removed object. * @throws IndexOutOfBoundsException * when {@code location < 0 || location >= size()} */
        @Override public E remove(int index) {
            Object[] a = array;
            int s = size;
            if (index >= s) {
                throwIndexOutOfBoundsException(index, s);
            }
            @SuppressWarnings("unchecked") E result = (E) a[index];
            System.arraycopy(a, index + 1, a, index, --s - index);
            a[s] = null;  // Prevent memory leak
            size = s;
            modCount++;
            return result;
        }
    
        @Override public boolean remove(Object object) {
            Object[] a = array;
            int s = size;
            if (object != null) {
                for (int i = 0; i < s; i++) {
                    if (object.equals(a[i])) {
                        System.arraycopy(a, i + 1, a, i, --s - i);
                        a[s] = null;  // Prevent memory leak
                        size = s;
                        modCount++;
                        return true;
                    }
                }
            } else {
                for (int i = 0; i < s; i++) {
                    if (a[i] == null) {
                        System.arraycopy(a, i + 1, a, i, --s - i);
                        a[s] = null;  // Prevent memory leak
                        size = s;
                        modCount++;
                        return true;
                    }
                }
            }
            return false;
        }

重载了两个remove函数。  
第一个remove函数的参数是索引，就是删除当前索引的元素。其实其本质就是复制了一个新数组，被操作的数组从index + 1这个位置开始的右侧所有元素，整体向左移动一位，同时把a\[s\]（也就是原数组末尾元素）的元素 置为null。  
第二个remove函数的参数是当前需要被删除的元素。如果传入的参数是null，那么对当前的数组进行遍历，如果遍历到一个元素的值是null，那么就把这个元素移除，并且用复制元素（System.arraycopy）的方式让当前null元素的位置右侧的元素整体向左移动一位。如果传入的参数不是null的时候，那么同样地对当前的数组进行遍历，如果找到一个元素equals(参数)为true的话，进行与上面同样地复制操作，完成删除。  
由上面可以看出，删除操作remove同样涉及到了数组的复制，所以ArrayList的remove操作的效率应该没有get，set那么高。

## 小结 ##

ArrayList类中还有一些函数没有列举在上面，后面我会把它们补充出来（有时间的话）。因为ArrayList几乎是我最常用的容器，所以我特意写了一篇笔记写下了自己的理解，也参考了其他前辈的文章（他们的java版本应该与我不一样，具体的函数实现可能略有差别）。因为是自己的一些语言，可能有些地方写的不是很清楚，如果哪里写的不对的话请指出，谢谢。

> 参考：  
> [关于Java集合的小抄][Java]  
> [Java ArrayList工作原理及实现][Java ArrayList]  
> [ArrayList原理及实现学习总结][ArrayList]

[Java]: http://calvin1978.blogcn.com/articles/collection.html
[Java ArrayList]: http://yikun.github.io/2015/04/04/Java-ArrayList%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
[ArrayList]: http://blog.csdn.net/jianyuerensheng/article/details/51192811