关于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 机制