关于java:列表容器ArrayList学习基于Java8

概述

ArrayList是jdk提供的非线程平安的基于数组的列表容器，是最频繁应用的Java容器之一。本文次要介绍一下ArrayList的内部结构和运行机制。

继承与实现

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

1. ArrayList继承了AbstractList抽象类，AbstractList提供了get,set,add,remove等形象的列表办法，提供给ArrayList或这LinkedList依据底层存储构造具体实现。
2. ArrayList实现了List接口，这样就能够实例化一个List类型的变量，其具体实现为ArrayList。
3. RandomAccess只是一个标记接口，没有任何办法，用于示意该类反对疾速随机拜访——能够应用工夫复杂度O(1)拜访任意元素。
4. Cloneable接口，想应用Object.clone()办法就要实现这个接口。
5. Serializable接口，序列化接口。

成员变量和办法

transient Object[] elementData;
private int size;

ArrayList底层是一个Object数组，应用size示意一共保留了多少个元素（不等于elemetnData.length)。

常见操作

  public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

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

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

因为底层是数组，增加、拜访和删除操作都比较简单。查看拜访索引或者容量，而后批改数组。

扩容

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!! modCount记录了汇合的批改次数
        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++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

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

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

对list进行扩容，newCapacity = oldCapacity + (oldCapacity >> 1)即新容量为原来的1.5倍。如果数组容量大于ArrayList最大容量，无奈再进行扩容。

遍历

Iterator次要的作用是为容器提供一个遍历元素的形式并且屏蔽容器的底层实现。如果没有迭代器，遍历ArrayList就须要拜访其底层数组，遍历LinkedList就须要拜访它的节点，裸露外部细节。Iterator屏蔽了底层细节，其根本应用：

    List list = new ArrayList();
    for (Iterator i=list.iterator(); i.hasNext();)
          i.next();

ArrayList实现了两个外部迭代器类Itr和ListItr，而后通过iterator()和listIterator()返回给用户应用。

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such

cursor指向下一个next()须要返回元素的索引，lastRet指向曾经拜访过的上一个元素的索引，lastRet== -1时代表上一个元素曾经被remove()删除了。next()执行之后迭代器remove()才晓得删除的是什么元素。

本文是迁徙旧文浅学——ArrayList机制