のArrayList

2534 ワード

まず、クラス定義を参照してください.
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable



 private transient Object[] elementData;


 public ArrayList(int initialCapacity) {
 super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
 this.elementData = new Object[initialCapacity];
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
 this(10);
    }

 
パラメトリック構造法を使用すると、ArrayListは長さ10のObject[]配列を初期化します.
次にadd関数を見てみましょう
 public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

 public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 
add関数を呼び出すと現在の配列の長さ+1となり、ensureCapacity関数により配列サイズが利用可能か否かが判断する、利用可能サイズを超えるとArrayList下位層に新たな配列が生成され、長さは元の配列の1.5倍+1となり、注目すべきはArraysである.copyOf(elementData, newCapacity);
削除関数を見てみましょう
 public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }

 
配列要素を削除する場合は、Systemも行います.arraycopy..削除された要素の後続の要素を前に移動するには
 
まとめ:
ArrayList:1)ArrayList下位層は配列実装を用い,パラメータを持たない構造手法を用いてArrayListオブジェクトを生成すると,実際には下位層に長さ10のObject型配列が生成される2)生成された配列が10を超えると,ArrayList下位層は元の配列の1.5倍+1の長さの新しい配列を生成し,元の配列の要素を新しい配列にコピーし,さらに、その後に追加された内容はいずれも新しい配列の中に入れられ、新しい配列が追加された要素を収容できない場合は、この手順3)ArrayList要素の削除操作に対して、削除された要素の後の要素を前に移動する必要があり、コストが比較的高い