浅谈ArrayList

ArrayList结构图

arraylist.png

ArrayList主要方法

• public boolean add(E e);
• public E set(int index, E element)
• public boolean remove(Object o);
• public E get(int index);

ArrayList解读主要方法

首先来看看add方法源码：

 public boolean add(E e) {
        //判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
       // 添加元素       
       elementData[size++] = e;
        return true;
    }

来看一下ensureCapacityInternal这个方法：

private void ensureCapacityInternal(int minCapacity) {
        // 如果数据为空（集合里没有元素），minCapacity取默认长度
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

来看一下ensureExplicitCapacity这个方法：

private void ensureExplicitCapacity(int minCapacity) {
        // 这个值是为了判断ConcurrentModificationException异常的
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(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容量
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

在看一下底层的调用：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

来看一下public E set(int index, E element)源码

 public E set(int index, E element) {
      //判断index位置
        rangeCheck(index);
      //获取index位置的元素
        E oldValue = elementData(index);
        //把新的元素放入index位置，返回原来的元素
        elementData[index] = element;
        return oldValue;
    }
//判断index位置
 private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

再看看remove的源码：

   public E remove(int index) {
        //校验删除位置是否合理
        rangeCheck(index);
      // 同add理由一样
        modCount++;
       // 保存待删除元素
        E oldValue = elementData(index);
        // 判断删除位置：如果>0不在尾部需要调用System.arraycopy，否则在尾部直接删除
        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;
    }

最后看一下get方法：

public E get(int index) {
        // 校验删除位置是否合理
        rangeCheck(index);
        //返回index位置的元素
        return elementData(index);
    }

好了看了一下，也就是add方法比较复杂，remove和get都比较简单。

ArrayList遍历介绍

常用的三种遍历方式：

       //one  foreach  遍历
        for (Object o : list) {
            System.out.println(o);
        }
        // two 随机访问
        for (int i = 0; i <list.size(); i++) {
            System.out.println(list.get(i));
        }
        //three 迭代器的遍历
        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

ArrayList其他特性介绍

我们来介绍一下ArrayList的一些小特效：

• ArrayList底层是利用数组来实现的 Object[] elementData，因此ArrayList拥有数组的特性，因为数组是逻辑上连续的，物理上也是连续的，因此查询比较方便，删除比较麻烦；然而LinkedList底层是利用链表来实现的，它拥有链表的特性，因为链表只是逻辑上连续的物理上非连续的所以它的添加和删除比较快，查询就比较麻烦。
• ArrayList默认的初始值是10，private static final int DEFAULT_CAPACITY = 10;每次扩容的容量为： int newCapacity = oldCapacity + (oldCapacity >> 1);约1.5倍
• ArrayList是会抛出 ConcurrentModificationException异常的