Javaのコレクションフレームワーク - ArrayListの内部実装

概要

ArrayListは、配列に基づいており自動拡張可能な動的配列です。その自動拡張機能により、開発において最も一般的に使用されるコレクションクラスの一つとなっています。

クラス図

ArrayListが実装しているインターフェースや継承している抽象クラスは以下の通りです。

• java.util.List - リストとしての基本的な操作を提供します。
• java.util.RandomAccess - ランダムアクセスが高速であることを示すマーカーインターフェースです。
• java.io.Serializable - シリアライズが可能であることを示します。
• java.lang.Cloneable - クローンを作成できることを示します。

さらに、ArrayListはjava.util.AbstractListを継承しており、これはリストの基本的な操作を提供しています。

プロパティ

ArrayListは主に2つのプロパティを持っています。

• elementData - リストの要素を保持する配列。
• size - リストに現在含まれている要素の数。

transient Object[] elementData;
private int size;

コンストラクタ

#ArrayList(int initialCapacity)

指定された初期容量を持つArrayListを作成します。

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

#ArrayList(Collection<? extends E> c)

指定されたコレクションからArrayListを作成します。

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()

初期容量が10のArrayListを作成します。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

要素の追加

#add(E e)

リストの最後に要素を追加します。

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

#add(int index, E element)

指定した位置に要素を挿入します。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

配列の拡張

#grow()

配列を拡張し、新しい配列を返します。

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

要素の削除

#remove(int index)

指定した位置の要素を削除します。

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

#remove(Object o)

最初に見つかった指定の要素を削除します。

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

複数の要素の追加と削除

#addAll(Collection<? extends E> c)

コレクションのすべての要素を追加します。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    System.arraycopy(a, 0, elementData, s, numNew);
    size = s + numNew;
    return true;
}

#removeAll(Collection<?> c)

コレクションに含まれるすべての要素を削除します。

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

要素の検索

#indexOf(Object o)

指定した要素の最初のインデックスを見つけます。

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null)
                return i;
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i]))
                return i;
        }
    }
    return -1;
}

イテレータ

#iterator()

イテレータを作成します。

public Iterator<E> iterator() {
    return new Itr();
}

#listIterator(int index)

指定した位置から開始するリストイテレータを作成します。

public ListIterator<E> listIterator(int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}