ArrayListとLinkedListの比較
1842 ワード
1、ArrayList実装は配列に基づいて実装され、これはArrayListのソースコードによって見ることができる.
ArrayListは、Listインタフェースの長さが可変な配列実装である.
2、LinkedListはListとDequeインタフェースの双方向チェーンテーブルの実現であるが、Javaにはポインタの概念がなく、ソースコードを表示する.
LinkedListは、プライベート静的クラスEntryを使用してチェーンテーブルに使用されるデータメンバーを定義します.Entryクラスでは、各クラスメンバーは、データ部分に加えて、前のチェーンテーブル要素と後のチェーンテーブル要素をそれぞれ指すEntryタイプの参照変数(C++のポインタに似ている)を2つ含み、LinkedListのチェーンテーブル構造を構成している.
注意:ArrayListとLinkedListの実装は同期していません.
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の実装は同期していません.