ArrayList

継承

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable

内部構造と初期化

最下層は可変配列

 /**
 * Default initial capacity.
 * 初期化容量、これは初期化時には使用されないことが判明しているが、拡張時には使用される。
 */
 private static final int DEFAULT_CAPACITY = 10;

 transient Object[] elementData; 

transient キーワードは、elementData 配列がシリアライズされないようにするためのもので、 writeObject の実装をオーバーライドします。

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
 *// Write out element count, and any hidden stuff*
 int expectedModCount = modCount;
 s.defaultWriteObject();
 *// Write out array length*
 s.writeInt(elementData.length);
 *// Write out all elements in the proper order.*
 for (int i=0; i<size; i++)
 s.writeObject(elementData[i]);
 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
}

これはシリアライズを高速化し、シリアライズ後のファイルサイズを小さくします。

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

渡されたパラメータのコンストラクタ・メソッドは、対応する長さの配列を構築し、それが0より小さい場合はエラーをスローします。

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

 /**
 * Constructs an empty list with an initial capacity of ten.
 * 初期サイズ10の空のリストを作る。
 */
 public ArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

ここでは参照コンストラクタはなく、空の Object 配列を初期化します。

内部構造はオブジェクトの配列です。

拡張

に要素を追加していくことになります。

要素を追加すると、1. 配列の長さが長くなります。

public boolean add(E e) {
 ensureCapacityInternal(size + 1); // Increments modCount!! 1 長さを増やす
 elementData[size++] = e; // 配列に要素を追加する
 return true;
 }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 return Math.max(DEFAULT_CAPACITY, minCapacity); //DEFAULT_CAPACITY=10，配列が空なら10を返す
 }
 return minCapacity;
 }
 private void ensureCapacityInternal(int minCapacity) {
 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }
 private void ensureExplicitCapacity(int minCapacity) {
 modCount++; //modCountデフォルトは0
 // overflow-conscious code
 if (minCapacity - elementData.length > 0) //必要な長さが元の配列の長さより大きい場合は、それを拡張する必要がある。
 grow(minCapacity);
 }

拡張方法

private void grow(int minCapacity) {
 // overflow-conscious code
 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity + (oldCapacity >> 1); // .5 
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);
 // minCapacity is usually close to size, so this is a win:
 elementData = Arrays.copyOf(elementData, newCapacity);//コピーを作る
 }

まとめ

1.ArrayListはnullを格納できます；

2.ArrayListスレッドは安全ではありません；

3.ArrayListは実際にはObjectの配列です；

4.ArrayListは毎回1.5倍に拡張されます；

5.ArrayListは本質的に配列なので、クエリは非常に高速です；

6.ArrayListの基礎となる配列のストア/テイク要素の効率は非常に高く、検索、時間の複雑さはO (1)ですが、要素の挿入と削除の効率は低いようで、時間の複雑さはO (n)です。

LinkedList

継承

public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable

内部構造と初期化

最下層は、以下のような双方向リンクテーブルです。

双方向連鎖表：連鎖表の一種で、各データノードに直接の後継者と直接の前任者への2つのポインタを持つもの。

連鎖表の末尾要素の最後のノードが連鎖表の先頭ノードで、連鎖表の先頭ノードの前のノードが連鎖表の末尾ノードです。

transient int size = 0; //セットの長さ
transient Node<E> first;//双方向リンクリストの先頭ノード
transient Node<E> last;//双方向リンクリストの末尾ノード

パラメータなしコンストラクタ

public LinkedList() {
 }

リストコンストラクタを渡します。

public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
 }

addAllのソースコード解析

public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);//境界外チェック
 Object[] a = c.toArray();//Arrayに設定する
 int numNew = a.length;
 if (numNew == 0)
 return false;
 Node<E> pred, succ;//末尾挿入で、前ノードと後ノードの挿入位置を取得する
 if (index == size) {//末尾を初期化し、あとはインデックスをつけるだけだ。=size
 //末尾からの追加：前任ノードは元の末尾ノードであり、後任ノードはnullである。
 succ = null;
 pred = last;
 } else {
 // 指定した位置から追加する:後継ノードはインデックス位置のノードであり、後継ノードはインデックス位置のノードの前のノードである。
 succ = node(index);
 pred = succ.prev;
 }
 //サイクリック挿入
 for (Object o : a) {
 @SuppressWarnings("unchecked") E e = (E) o;
 Node<E> newNode = new Node<>(pred, e, null);
 if (pred == null) 
 //空のチェーン挿入
 first = newNode;
 else //が空でない場合、predの現在の要素への次のポインタが返される。
 pred.next = newNode;
 pred = newNode;//最後に、newNodeは、次のループで使うためにpredに代入され、後ろに移動する。
 }
 if (succ == null) {
 //挿入が末尾からの場合、最後の要素が最後に挿入された要素として設定される。
 last = pred; //ループの後でhead要素が空であれば、最後の要素がheadに代入され、tailとheadの相関関係が形成される。
 } else {
 // 末尾から挿入されない場合は、末尾のデータをノードの
 pred.next = succ;
 succ.prev = pred;
 }
 size += numNew;
 modCount++;
 return true;
 }

双方向チェイン・テーブルは、Node クラス・エンティティの実装を定義する内部クラスです。

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

LinkedListは双方向リンクリスト構造で、各ノードはNodeを保持します。

Nodeには3つの属性があります。

next:次のノードへの参照。

prev:前のノードを指す、前のノードへの参照

これは連鎖したテーブル構造を形成します。

Addメソッド

LinkedList は List インターフェースと Deque インターフェースを実装しています。

つまり、LinkedListは、要素を末尾に追加することも、指定したインデックス位置に追加することも、コレクション全体を追加することもできます；

また、ヘッドとテールの両方に追加することもできます。

//末尾に要素を追加する
public boolean add(E e) {
 linkLast(e);
 return true;
 }

 /**
 * Links e as last element.
 */
 void linkLast(E e) {
 final Node<E> l = last;// 最後の要素を取得する
 final Node<E> newNode = new Node<>(l, e, null);// 最後の要素を前任者とする新しいノードを作成する
 last = newNode;// 最後のノードを挿入すべきノードに更新する
 if (l == null)
 // 空のリンクリストの場合、最初のノードを更新して、挿入するノードにもする。
 first = newNode;
 else
 // リストが空でない場合：次のノードを挿入するノードに向ける。
 l.next = newNode;
 size++;// サイズと修正数を更新して、挿入完了。
 modCount++;
 }

private void linkFirst(E e) {
 final Node<E> f = first;
 final Node<E> newNode = new Node<>(null, e, f);
 first = newNode;
 if (f == null)
 last = newNode;
 else
 f.prev = newNode;
 size++;
 modCount++;
 }

を追加します。

public void add(int index, E element) {
 checkPositionIndex(index);
 if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));
 }

void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 final Node<E> pred = succ.prev; // 挿入された要素の先行ノードを取得する
 final Node<E> newNode = new Node<>(pred, e, succ);// succの点を前任者とし、succノードを後任者とする新しいノードを作る
 succ.prev = newNode;// 挿入位置の先行ノードを新しいノードに更新する。
 if (pred == null)
 first = newNode;// predがnullの場合、そのノードはheadノードに挿入されることを意味し、最初のheadノードをリセットしなければならない。 
 else
 pred.next = newNode;// predがnullでなければ、predの後継の newNodeへのポインタで十分である。
 size++;
 modCount++;
 }

拡張

下部の双方向リンクテーブルで実装されているため、サイズの初期化や拡張のメカニズムはありません。

まとめ

1.LinkedListはNULLを格納できます；

2.LinkedListスレッドは安全ではありません；

3.LinkedListは実際には循環双方向リストです；

4.LinkedListには拡張メカニズムも初期化もありません；

5.LinkedListは基本的に双方向リンクリストなので、クエリが遅く、追加と削除が速くなります；

6.LinkedListのルックアップ、時間の複雑さはO（n）であり、挿入、削除の時間の複雑さはO（n）です。

ArrayListLinkedListとの比較

1.LinkedListとArrayListの違いは、主にArrayとLinkedListのデータ構造の違いに由来します。 ArrayListは配列の実装に基づいており、LinkedListは二重リンクリストの実装に基づいています。

2.LinkedListがノードへのポインタを一歩一歩移動させるのに対して、ArrayListはランダムに配置することができるため、ランダムアクセスの取得と設定には、LinkedListよりもArrayListの方が適しています。

シナリオ

使用シナリオ

1.アプリケーションでデータへのランダムアクセスが多い場合は、LinkedListオブジェクトよりもArrayListオブジェクトの方が好まれます；

2.挿入や削除の操作が多く、データの読み込みが少ないアプリケーションでは、ArrayListオブジェクトよりもLinkedListオブジェクトの方が好まれます；

3.ArrayListの挿入、削除操作は、LinkedListよりも遅いとは限らないことに注意してください。

すると、ArrayListはより少ないデータを移動させるだけでよくなり、LinkedListはリストの最後まで調べる必要があります。

その代わり時間がかかるので、LinkedListよりもArrayListの方が速くなります。

言葉の後ろに書く

あなたはシュラウド、あなたは月の光。