Listインタフェースの基本特性

java.util.ListインタフェースはCollectionを継承し、順序付きのシーケンスとして機能します。主な特徴は以下の通りです：

• 要素の順序を保持し、追加順序が保存されます
• インデックスを用いた要素のアクセスが可能です
• 重複した要素の保存が許可されます
• null値の要素を保存できます

Listインタフェースの主要メソッド

以下のメソッドが定義されています：

// 要素数の取得
int size();

// 空チェック
boolean isEmpty();

// 要素の検索
boolean contains(Object obj);

// イテレータの取得
Iterator<E> iterator();

// インデックスによる要素取得
E get(int index);

// インデックスによる要素更新
E set(int index, E element);

// インデックスによる要素追加
void add(int index, E element);

// インデックスによる要素削除
E remove(int index);

// 要素のインデックス検索
int indexOf(Object obj);

主要実装クラスの比較

Listインタフェースの主な実装クラスは以下の3つです：

• ArrayList: 配列を基盤とした実装、要素の検索が高速だが、追加/削除が遅い
• LinkedList: 双方向リンクリストを基盤とした実装、追加/削除が高速だが、検索が遅い
• Vector: ArrayListと同様の実装だが、スレッドセーフ

ArrayListの実装詳細

ArrayListは内部的に配列を用いた実装で、要素の追加時に自動で容量を拡張します。

内部構造

private transient Object[] storage;
private int itemCount;
private int modificationCount;

要素追加の実装

public boolean add(E element) {
    ensureCapacity(itemCount + 1);
    storage[itemCount++] = element;
    return true;
}

private void ensureCapacity(int requiredSize) {
    if (storage.length < requiredSize) {
        int newCapacity = storage.length * 3 / 2 + 1;
        storage = Arrays.copyOf(storage, newCapacity);
    }
}

要素削除の実装

public E remove(int index) {
    rangeCheck(index);
    modificationCount++;
    E oldValue = storage[index];
    int numMoved = itemCount - index - 1;
    if (numMoved > 0) {
        System.arraycopy(storage, index + 1, storage, index, numMoved);
    }
    storage[--itemCount] = null;
    return oldValue;
}

LinkedListの実装詳細

LinkedListは双方向リンクリストを用いた実装で、要素の追加/削除が高速です。

ノード構造

private static class Node<E> {
    E value;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E value, Node<E> next) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
}

要素追加の実装

public void addFirst(E element) {
    Node<E> oldFirst = first;
    first = new Node<>(null, element, oldFirst);
    if (oldFirst == null) {
        last = first;
    } else {
        oldFirst.prev = first;
    }
    itemCount++;
    modificationCount++;
}

要素検索の実装

public E get(int index) {
    checkIndex(index);
    Node<E> node = getNode(index);
    return node.value;
}

private Node<E> getNode(int index) {
    if (index < (itemCount >> 1)) {
        Node<E> current = first;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    } else {
        Node<E> current = last;
        for (int i = itemCount - 1; i > index; i--) {
            current = current.prev;
        }
        return current;
    }
}

Vectorの実装詳細

VectorはArrayListと同様の実装ですが、すべてのメソッドにsynchronized修飾子が付与されており、スレッドセーフです。

容量管理の実装

private void ensureCapacityHelper(int minCapacity) {
    if (minCapacity > storage.length) {
        int newCapacity = storage.length * 2;
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        storage = Arrays.copyOf(storage, newCapacity);
    }
}

AbstractListの役割

AbstractListはListインタフェースの抽象クラスで、共通の実装を提供します。

基本構造

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    protected int modificationCount = 0;
    
    abstract public E get(int index);
    
    public boolean add(E element) {
        add(size(), element);
        return true;
    }
}

イテレータの実装

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

private class ListIterator implements Iterator<E> {
    private int cursor = 0;
    private int lastRet = -1;
    private int expectedModCount = modificationCount;
    
    public boolean hasNext() {
        return cursor < size();
    }
    
    public E next() {
        checkForComodification();
        int i = cursor;
        E next = get(i);
        lastRet = i;
        cursor = i + 1;
        return next;
    }
    
    private void checkForComodification() {
        if (modificationCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}