ArrayListとLinkedList分析

まずArrayListソースコードを見てみましょう

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
// 
 private transient E[] elementData;

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

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

これにより、最下位層は配列で維持され、デフォルトの配列サイズは10であり、ArrayListにオブジェクトを追加すると、追加されたオブジェクトが10を超えると配列によって指向されることがわかります.

  public boolean add(E o) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = o;
	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;
	    elementData = (E[])new Object[newCapacity];
	    System.arraycopy(oldData, 0, elementData, 0, size);
	}
    }

元の長さの1.5倍に1を加えた新しいオブジェクト配列が生成され、このプロセスが再び繰り返されると
LinkedListを見てみましょう

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

   /**
     * Appends the specified element to the end of this list.
     *
     * @param o element to be appended to this list.
     * @return <tt>true</tt> (as per the general contract of
     * <tt>Collection.add</tt>).
     */
    public boolean add(E o) {
	addBefore(o, header);
        return true;
    }
   private Entry<E> addBefore(E o, Entry<E> e) {
	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
    }

   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の下位層は双方向チェーンテーブルで実現されていることは明らかであり、LinkedListにオブジェクトを追加すると、実際に下位層にEntryオブジェクトが生成され、追加されたオブジェクトをそのメンバー変数elementに付与し、Entryは前後参照を構築し、前後リンクが維持されるのはオブジェクト自体ではなく、実はEntryオブジェクトである
上から見える
ArrayListは配列で実現されているのでクエリの効率は高く,LinkedListはチェーンテーブルで実現されているので,その挿入と削除の効率は高いが,どちらもスレッドセキュリティではないため,実際の開発では同期が必要である.