从源码看ArrayList使用(一)

约定不等于承诺〃 2022-11-19 04:09 196阅读 0赞

ArrayList是基于数组实现的List接口，实现所有可选列表操作，并允许所有元素，包括null对象。 除了实现`List`接口之外，该类还提供了一些方法来处理内部用于存储列表的数组的大小。 每个ArrayList实例都有一个*容量* 。 容量是用于存储列表中的元素的数组的大小。 它总是至少与列表大小一样大。 如果添加元素时发现当前容量已满，则ArrayList会自动扩容，扩充容量为当前容量的0.5倍。ArrayList是线程非同步的，即多线程情况下操作不安全，如果要在多线程情况下使用ArrayList，可以选择使用Collections.synchronizedList()方法使list同步或换线程同步的Vector类。

ArrayList方法较多，这篇文章聊聊构造方法、添加、删除、遍历、包含方法。

### ArrayList构造方法 ###

ArrayList提供三个构造方法

*  ArrayList() 构建默认容量为10的列表
 *  ArrayList(int initialCapacity) 构建指定容量的列表
 *  ArrayList(Collection<? extends E> c) 将一个集合中元素构建为列表

/**
         * 默认的初始容量.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * list为空时的数组实例.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * 用于默认大小的空实例的共享空数组实例. We
         * 我们区别它从EMPTY_ELEMENTDATA到添加第一个元素要扩容多少次
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         * 存储ArrayList元素的数组缓冲区.
         * ArrayList的容量是该数组的长度. 
         * 当第一个元素添加时，任何空DEFAULTCAPACITY_EMPTY_ELEMENTDATA容量都将恢复到默认容量
         */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * ArrayList大小 (包含的元素个数).
         *
         * @serial
         */
        private int size;
    
        /**
         * 构建指定容量的list列表
         * @param  列表的容量大小
         * @throws 容量为负数时抛出IllegalArgumentException异常
         */
        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);
            }
        }
    
        /**
         * 构建一个空list，默认容量为10
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        /**
         * 构建一个list，包含集合中的所有元素
         * 按照集合的迭代器返回他们的顺序
         *
         * @param 待转换为list的元素集合
         * @throws 集合为空时抛出NullPointerException异常
         */
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

### 添加元素 ###

ArrayList添加元素提供四个方法

*  add(E e) 列表尾部插入元素
 *  add(int index, E element) 列表指定位置插入元素
 *  addAll(Collection<? extends E> c) 
 *  addAll(int index, Collection<? extends E> c)

/**
         * 列表尾部添加元素
         *
         * @param 添加到列表尾部的元素
         * @return 添加成功返回true
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        /**
         * 插入元素到列表指定的位置
         * 当前位置的元素(如果有)和任何后续元素向右移动一位(坐标位置加1)
         *
         * @param index 被插入的指定的索引位置
         * @param element 插入的元素信息
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        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++;
        }
    
        /**
         * 将指定集合中的所有元素追加到此列表尾部，按指定集合的迭代器返回它们的顺序排列。
         * 如果在操作过程中，指定的集合发生了修改操作，可能会有意想不到的行为
         * (这意味着，如果指定的列表是当前列表，且当前列表非空时，这个调用可能会产生未定义的行为)
         *
         * @param c 指定的集合
         * @return 如果当前列表因此而改变返回true
         * @throws 如果指定结合c为空抛NullPointerException异常
         */
        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;
        }
    
        /**
         * 从指定位置开始，将指定集合中的所有元素插入此列表。
         * 当前位置的元素(如果有)和任何后续元素向右移动一位(坐标位置加1)
         * 新元素将按指定集合的迭代器返回的顺序出现在列表中。
         *
         * @param index 指定集合中第一个元素要插入的位置
         * @param c 指定的集合
         * @return 如果这个操作使当前列表改变返回true
         * @throws IndexOutOfBoundsException {@inheritDoc}
         * @throws 如果指定集合为空则抛出NullPointerException异常
         */
        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;
        }

看一个添加元素的方法源代码，看一下add(E e）

/**
         * 列表尾部添加元素
         *
         * @param 添加到列表尾部的元素
         * @return 添加成功返回true
         */
        public boolean add(E e) {
            // 确保容量够用
            ensureCapacityInternal(size + 1);  // modCount次数增加
            // 将新元素连接到数组尾部，原数组size++即为新元素坐标位置
            elementData[size++] = e;
            // 添加成功，返回成功true标识
            return true;
        }
    
        /**
         * 确保容量够用
         *
         * @param minCapacity 最小容量数值
         */
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        
        /**
         * 计算容量值
         * @param elementData 已存元素数组长度
         * @param minCapacity 最小容量数值
         */
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            // 若已存元素数组elementData 为空
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                // 返回默认容量10 和 最小容量minCapacity较大值
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            // 列表修改次数加1
            modCount++;
    
            // 如果最小容量 大于 缓冲数组长度，则须要扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        /**
         * 增加列表容量，使其至少可以保存minimum个元素
         *
         * @param minCapacity 最小容量值
         */
        private void grow(int minCapacity) {
            // 取到当前列表长度
            int oldCapacity = elementData.length;
            // 新容量 = 当前容量oldCapacity + (oldCapacity >> 1)
            // (oldCapacity >> 1) 即对当前容量右移一位，即除以2，扩容部分为当前容量0.5倍
            // 新容量 = oldCapacity + 0.5*oldCapacity = 1.5*oldCapacity 
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 如果新容量小于最小容量minCapacity 
            if (newCapacity - minCapacity < 0)
                // 将minCapacity 设置为新容量
                newCapacity = minCapacity;
            // 如果新容量大于最大数组大小
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                // 大容量处理，将结果值作为新的容量
                newCapacity = hugeCapacity(minCapacity);
            // 将原数组内容拷贝到新的扩容后数组中
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        
        /**
         * 大容量处理
         *
         * @param minCapacity 最小容量值
         */
        private static int hugeCapacity(int minCapacity) {
            // 若最小容量小于0，抛出异常
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            // 如果最小容量大于最大数组大小，则返回int型最大值，否则返回list可允许最大数组大小
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

### 替换元素 ###

ArrayList替换元素提供了一个方法

/**
         * 把指定位置index上面的元素替换为指定元素element
         *
         * @param index 被替换的元素位置
         * @param element 指定位置被存储的新元素
         * @return 指定位置的旧元素
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
    
        /**
         * 检查指定索引是否在范围内.  如果不在，抛出运行时异常
         * 这个方法不检查索引为负数的情况
         * 索引总是在数组使用之前调用，如果索引为负数，则抛出ArrayIndexOutOfBoundsException异常
         */
        private void rangeCheck(int index) {
            // 如果索引大于当前list的size，即有效元素的个数
            if (index >= size)
                // 抛出索引越界异常IndexOutOfBoundsException
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

### 删除元素 ###

ArrayList删除元素提供了三个方法

*  remove(int index)  删除指定位置元素
 *  remove(Object o)  删除指定元素
 *  removeAll(Collection<?> c) 删除集合中所包含元素

/**
         * 删除指定索引位置的元素
         * 该位置之后的元素统一左移一位 (坐标位置减1)
         *
         * @param index 被删除元素的坐标位置
         * @return 该坐标位置被删除掉的元素
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E remove(int index) {
            // 检查索引有效
            rangeCheck(index);
    
            // 列表修改次数加1
            modCount++; 
    
            // 获取到index位置的元素
            E oldValue = elementData(index);
            
            // 要移动的元素个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                // 从源数组elementData第index+1位置开始拷贝数据，拷贝numMoved个元素
                // 拷贝到目标数组elementData中，从index位置开始存放
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            // 数组拷贝后，原数组elementData最后一个位置元素则为无效元素
            // 将该位置引用置为null，方便垃圾回收器回收掉该对象
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    
        /**
         * 删除列表中第一次出现的指定元素,如果该元素存在于列表中
         * 如果列表不包含该元素, 列表不做改变
         * 更正式地说, 删除列表中包含该元素的最小索引
         * 如果列表包含该元素，则返回true (等效地, 列表因为此次调用而改变).
         *
         * @param 待删除的元素信息
         * @return 如果列表包含该元素，则返回true
         */
        public boolean remove(Object o) {
            // 若元素为null
            // 则遍历列表，找到第一个为null的元素，删除该位置元素，返回true
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                // 若元素非null，则遍历列表
                // 找到第一个等于(equals)该元素的位置，删除该位置元素，返回true
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
        /*
         * 私有的删除方法，跳过边界的检查且不返回被删除的元素
         */
        private void fastRemove(int index) {
            // 列表修改次数加1
            modCount++;
            // 计算要移动的元素个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                // 数组拷贝
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            // 最后一个元素引用置null，使垃圾回收器及时回收
            elementData[--size] = null; // clear to let GC do its work
        }
    
        /**
         * 从列表中删除指定集合包含的所有元素
         *
         * @param c 包含所有要从列表中删除的元素的集合
         * @return 如果列表因此次调用改变了则返回true
         * @throws 如果此列表的元素的类与指定的集合不兼容抛出ClassCastException异常
         * @throws 如果此列表包含空元素，并且指定的集合不允许空元素（ optional ）
         *         或者如果指定的集合为空，抛出NullPointerException异常
         */
        public boolean removeAll(Collection<?> c) {
            // 断言，判断指定集合非空
            Objects.requireNonNull(c);
            // batchRemove方法源码改期读
            return batchRemove(c, false);
        }

获取元素

ArrayList获取元素只提供一个get(int index)方法

/**
         * 返回列表指定位置的元素信息
         *
         * @param  index 待返回元素的坐标位置
         * @return 返回index位置的元素
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E get(int index) {
            // 检查索引有效
            rangeCheck(index);
            
            // 返回索引位置的元素
            return elementData(index);
        }

### 列表遍历 ###

ArrayList遍历有三种方式

*  普通for循环 for(；；)
 *  for-each 循环
 *  迭代器Iterator

List<String> list = new ArrayList<>();
    		list.add("001");
    		list.add("002");
    		list.add("003");
    		
    		// 普通for循环
    		for(int i=0; i<list.size(); i++) {
    			String element = list.get(i);
    			System.out.println(element);
    		}
    		
    		// for-each循环
    		for (String element : list) {
    			System.out.println(element);
    		}
    		
    		// 迭代器方法一，使用默认迭代器
    		Iterator<String> itr = list.iterator();
    		while (itr.hasNext()) {
    			String element = itr.next();
    			System.out.println(element);
    		}
    		
    		// 迭代器方法二，使用listIterator
    		itr = list.listIterator();
    		while (itr.hasNext()) {
    			String element = itr.next();
    			System.out.println(element);
    		}

### 包含某元素 ###

ArrayList包含某元素，有三种方式判断

*  contains(Object o) 是否包含，返回true或false
 *  indexOf(Object o) 返回该元素第一次出现索引位置
 *  lastIndexOf(Object o) 返回该元素最后一次出现索引位置

/**
         * 返回true，如果列表中包含该元素
         * 更正式地说, 返回true 是在 列表中至少包含一个该元素
         * 且满足 o==null?e==null:o.equals(e)
         *
         * @param o 被测试是否包含在list中的元素
         * @return <tt>true</tt> if this list contains the specified element
         */
        public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }
    
        /**
         * 返回该元素在列表中第一次出现的位置
         * 如果不包含该元素，则返回-1
         * 更正式地说, 返回该元素最小索引位置且 o==null?e==null:o.equals(e)
         * 或者 返回-1，当列表中不包含该元素时
         */
        public int indexOf(Object o) {
            // 该元素为null，顺序遍历列表，若i位置元素等于该元素，返回i 
            if (o == null) {
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
                // 该元素非空，顺序遍历列表，若i位置元素等于该元素，返回i 
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
    
            // 列表遍历结束未找到元素，返回-1
            return -1;
        }
    
        /**
         * 返回元素在列表中最后一次出现的位置
         * 如果未找到该元素，则返回-1
         * 更正式地说, 返回该元素最大索引位置且 o==null?e==null:o.equals(e)
         * 或者 返回-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;
        }