ArrayListの仕組みと内部実装の詳細解説

ArrayListの概要

ArrayListは、Javaコレクションフレームワークにおいて最も基本的なデータ構造の一つであり、内部的には可変長の配列として実装されています。通常の配列と異なり、要素の追加に応じて動的に容量を拡張できる特性を持っています。大量の要素を追加する予定がある場合は、ensureCapacityメソッドを事前に呼び出すことで、頻繁な配列再割り当てによるパフォーマンス低下を防ぐことができます。

ArrayListは以下のインターフェースを実装しています：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
  • List: 要素の追加、削除、検索などの基本操作をサポートし、インデックスによるアクセスが可能
  • RandomAccess: 高速なランダムアクセスが可能であることを示すマーカーインターフェース
  • Cloneable: インスタンスの複製が可能であることを示す
  • Serializable: 直列化が可能で、オブジェクトをバイトストリームとして保存・転送できる

ArrayListとVectorの比較

ArrayListとVectorはどちらもListインターフェースを実装していますが、重要な違いがあります：

  • ArrayList: 非同期な実装であり、高速だがスレッドセーフではない。頻繁な検索操作に適している
  • Vector: 同期化された実装でスレッドセーフだが、パフォーマンス面で劣る。レガシーなクラス

null値の格納について

ArrayListはnull値を格納することが可能です。ただし、null値の格納は推奨されません。後続の処理でnullチェックを忘れるとNullPointerExceptionが発生するリスクがあるためです。

List<String> items = new ArrayList<>();
items.add(null);
items.add("sample");
System.out.println(items);  // 出力: [null, sample]

ArrayListとLinkedListの違い

比較項目ArrayListLinkedList
スレッドセーフ非同期（非安全）非同期（非安全）
内部構造Object配列双方向連結リスト
ランダムアクセスO(1)で高速O(n)で低速
先頭への挿入・削除O(n)O(1)
メモリ効率末尾に予備容量各要素に前後参照を持つため多く消費

ArrayListの内部実装の解析

JDK 8をベースにArrayListの主要な実装を確認します。

フィールド定義

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    private static final long serialVersionUID = 8683452581122892189L;
    
    // デフォルトの初期容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 空の配列（空のインスタンス用）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    // デフォルトコンストラクタで使用される空の配列
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    // データを格納する配列
    transient Object[] elementData;
    
    // 要素数
    private int size;
    
    // 配列の最大サイズ
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

コンストラクタ

ArrayListには3つのコンストラクタが存在します：

// 指定した初期容量で作成
public ArrayList(int initCapacity) {
    if (initCapacity > 0) {
        this.elementData = new Object[initCapacity];
    } else if (initCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("不正な容量: " + initCapacity);
    }
}

// デフォルトコンストラクタ
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// コレクションから作成
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;
    }
}

デフォルトコンストラクタを使用した場合、初期状態では空の配列が割り当てられ、最初の要素が追加された時点で容量10に拡張されます。

容量拡張メカニズム

ArrayListの核心となる拡張プロセスを詳しく見ていきます。

add メソッド

public boolean add(E element) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = element;
    return true;
}

容量計算と拡張判定

private static int calculateCapacity(Object[] data, int minCap) {
    if (data == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCap);
    }
    return minCap;
}

private void ensureCapacityInternal(int minCap) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCap));
}

private void ensureExplicitCapacity(int minCap) {
    modCount++;
    if (minCap - elementData.length > 0)
        grow(minCap);
}

grow メソッド - 実際の拡張処理

private void grow(int minCap) {
    int oldCap = elementData.length;
    // 新容量は旧容量の約1.5倍
    int newCap = oldCap + (oldCap >> 1);
    
    if (newCap - minCap < 0)
        newCap = minCap;
    
    if (newCap - MAX_ARRAY_SIZE > 0)
        newCap = hugeCapacity(minCap);
    
    elementData = Arrays.copyOf(elementData, newCap);
}

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

拡張の際、新しい容量はoldCapacity + (oldCapacity >> 1)で計算され、これは元の容量の約1.5倍となります。ビットシフト演算を使用することで、整数除算よりも高速に計算できます。

拡張のタイミング例

  • 最初の要素追加時: minCapacity = 10, elementData.length = 0 → 拡張発生、容量は10
  • 2〜10番目の要素追加時: 容量は10のまま
  • 11番目の要素追加時: minCapacity = 11, elementData.length = 10 → 拡張発生、容量は15

配列操作の主要メソッド

要素の取得と設定

public E get(int idx) {
    rangeCheck(idx);
    return elementData(idx);
}

public E set(int idx, E element) {
    rangeCheck(idx);
    E oldVal = elementData(idx);
    elementData[idx] = element;
    return oldVal;
}

@SuppressWarnings("unchecked")
E elementData(int idx) {
    return (E) elementData[idx];
}

要素の挿入

public void add(int idx, E element) {
    rangeCheckForAdd(idx);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, idx, elementData, idx + 1, size - idx);
    elementData[idx] = element;
    size++;
}

要素の削除

public E remove(int idx) {
    rangeCheck(idx);
    modCount++;
    E oldVal = elementData(idx);
    int moveCount = size - idx - 1;
    if (moveCount > 0)
        System.arraycopy(elementData, idx + 1, elementData, idx, moveCount);
    elementData[--size] = null;  // GC用
    return oldVal;
}

System.arraycopyとArrays.copyOfの違い

System.arraycopy

ネイティブメソッドであり、高速な配列コピーを行います。既存の配列間でデータをコピーする際に使用します。

public static native void arraycopy(
    Object src,  int srcPos,
    Object dest, int destPos,
    int length
);

// 使用例: 要素の挿入時
int[] arr = {0, 1, 2, 3, 0, 0, 0, 0, 0, 0};
System.arraycopy(arr, 2, arr, 3, 3);
arr[2] = 99;
// 結果: [0, 1, 99, 2, 3, 0, 0, 0, 0, 0]

Arrays.copyOf

内部でSystem.arraycopyを呼び出し、新しい配列を作成して返します。配列の拡張や縮小に適しています。

public static <T> T[] copyOf(T[] original, int newLen) {
    return (T[]) copyOf(original, newLen, original.getClass());
}

// 使用例
int[] source = {0, 1, 2};
int[] expanded = Arrays.copyOf(source, 10);
// expanded.length = 10

ensureCapacityメソッドの活用

大量の要素を追加する前にこのメソッドを呼び出すことで、パフォーマンスを向上させることができます。

public void ensureCapacity(int minCap) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0 : DEFAULT_CAPACITY;
    if (minCap > minExpand) {
        ensureExplicitCapacity(minCap);
    }
}

パフォーマンステストの例：

List<Integer> data = new ArrayList<>();
final int COUNT = 10_000_000;

// ensureCapacityなし
long t1 = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
    data.add(i);
}
long t2 = System.currentTimeMillis();
System.out.println("なし: " + (t2 - t1) + "ms");

// ensureCapacityあり
List<Integer> data2 = new ArrayList<>();
data2.ensureCapacity(COUNT);
long t3 = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
    data2.add(i);
}
long t4 = System.currentTimeMillis();
System.out.println("あり: " + (t4 - t3) + "ms");

重要な補足

Javaのサイズ取得方法の違い：

  • length: 配列の長さを取得するプロパティ
  • length(): 文字列の長さを取得するメソッド
  • size(): コレクションの要素数を取得するメソッド

タグ: Java arraylist コレクションフレームワーク データ構造 配列

5月20日 23:13 投稿

ホットタグ

©2026 異端開発室