ArrayListとLinkedListの比較


1、ArrayList実装は配列に基づいて実装され、これはArrayListのソースコードによって見ることができる.
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private transient Object[] elementData;

    private int size;
    
    /* */
}

ArrayListは、Listインタフェースの長さが可変な配列実装である.
2、LinkedListはListとDequeインタフェースの双方向チェーンテーブルの実現であるが、Javaにはポインタの概念がなく、ソースコードを表示する.
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

    /**
     *  , 
     */
    public LinkedList() {
        header.next = header.previous = header;
    }

    /* 、 */

    /**
    * LinkedList 
    */
    private static class Entry<E> {
	E element;
	Entry<E> next;
	Entry<E> previous;

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }
 
    /**
    * LinkedList 
    */
    public E getFirst() {
	if (size==0)
	    throw new NoSuchElementException();

	return header.next.element;
    }

}

LinkedListは、プライベート静的クラスEntryを使用してチェーンテーブルに使用されるデータメンバーを定義します.Entryクラスでは、各クラスメンバーは、データ部分に加えて、前のチェーンテーブル要素と後のチェーンテーブル要素をそれぞれ指すEntryタイプの参照変数(C++のポインタに似ている)を2つ含み、LinkedListのチェーンテーブル構造を構成している.
 
注意:ArrayListとLinkedListの実装は同期していません.