ArrayListとLinkedList

ArrayList && LinkedList#

ArrayList#

一、概説：#

AbstractList を継承し、List インターフェースを実装している。これは配列キューで、関連する追加、削除、変更、遍歴などの機能を提供する。
リストインターフェースの他に、このクラスは配列のサイズを操作してリスト内の配列のサイズを保存する方法を提供する。
Serializableインターフェースを実装しており、これは ArrayList がシリアライズをサポートし、シリアライズを通じて転送できることを意味する。

1. 時間計算量：#

ArrayList はRandomAccessインターフェースを実装しており、ランダムアクセス機能を提供する。
メソッドsize、isEmpty、get、set、iteratorおよびlistIteratorの呼び出しは定数時間である。
追加と削除の時間計算量は O (N)。他のすべての操作も線形時間計算量である。

2. 容量：#

各 ArrayList には容量があり、容量の大きさは少なくとも List 要素の長さであり、デフォルトでは 10 に初期化され、容量は自動的に増加する。
事前に配列要素が多いことがわかっている場合は、要素を追加する前にensureCapacity()メソッドを呼び出して容量を増加させ、後の容量自動増加のオーバーヘッドを減少させることができる。
初期容量を持つコンストラクタを使用してこの容量を初期化することもできる。

3. スレッド非安全：#

ArrayList はスレッド安全ではなく、マルチスレッド環境ではVectorまたはCopyOnWriteArrayListを選択することができ、Collections.synchronizedListを使用して通常の ArrayList をスレッド安全なバージョンの配列コンテナにラップすることもできる。

二、LinkedList#

内部で双方向リストを使用して実装され、頭と尾の 2 つのポインタを保持し、LinkedList の他の操作。

ArrayList と LinkedList の違い#

LinkedList は List および Deque インターフェースを実装しており、一般に双方向リストと呼ばれる。ArrayList は List インターフェースを実装しており、動的配列である。
LinkedList はデータの挿入と削除時に効率が高く、ArrayList は特定のインデックスのデータを検索する際に効率が高い。
LinkedList は ArrayList よりも多くのメモリを必要とする。前後の 2 つのポインタを維持する必要があるため。

三、考察#

1. ArrayList の挿入削除は必ず遅いのか？#

必ずしもそうではなく、挿入削除の位置が配列の末端からどれだけ離れているかによる。例えば、ちょうど尾部に挿入する場合、時間計算量は O (1) である。

2. ArrayList の遍歴と LinkedList の遍歴性能比較はどうか？#

遍歴に関してはArrayListはLinkedListよりもはるかに速い。ArrayListの遍歴の最大の利点はメモリの連続性であり、CPU の内部キャッシュ構造は連続したメモリセグメントをキャッシュし、メモリの読み取り性能のオーバーヘッドを大幅に削減できる。

3. ArrayList はどのように拡張されるのか？#

要素を追加する場合、まずcalculateCapacity()メソッドが必要な容量を計算し、ensureExplicitCapacityメソッドが内部でgrowメソッドを呼び出して拡張を行う。grow メソッドの具体的な実装は次の通り：

private void grow(int minCapacity) {
    // オーバーフローを意識したコード
    int oldCapacity = elementData.length;
    // 元の容量の1.5倍に拡張
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 拡張後の容量が十分かどうかを判断し、不足している場合はminCapacityを容量サイズとして使用
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 予想値がデフォルトの最大値を超えているかどうかを確認し、オーバーフローをチェック
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 配列をnewCapacityの新しい連続メモリ空間に指し、データをコピー
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. ArrayList のデフォルトの最大配列サイズはなぜ`Integer.MAX_VALUE - 8`なのか？#

配列オブジェクトには、配列のサイズを表すための追加のメタデータがあり、この部分のメタデータを保存するために追加の 8 バイトが必要である。

5. ArrayList はスレッド安全か？#

ArrayList はスレッド安全ではなく、マルチスレッド環境ではVectorを選択するか、Collections.synchronizedListを使用して通常の ArrayList をスレッド安全なバージョンの配列コンテナにラップすることができる。原理は似ており、どちらも直接synchronizedでロックをかける。CopyOnWriteArrayListはスレッド安全であり、読み書き分離のメカニズムを実現しており、読み取りが多く書き込みが少ないシナリオに適している。原理の参考: CopyOnWriteArrayList 実装原理及びソースコード分析

6. 配列はキューに適しているか？#

キューは一般に FIFO である。ArrayList をキューとして使用する場合、配列の尾部にデータを追加し、配列の頭部からデータを削除する必要がある。逆も可能である。しかし、いずれにせよ、配列のデータ移動に関わる操作が常にあり、これは性能を消費する。定長配列は非常に適している。例えば、ArrayBlockingQueueの内部実装は環状キューであり、定長キューであり、内部は定長配列を使用して実装されている。また、有名な Disruptor オープンソースライブラリも環状配列を使用して超高性能キューを実現している。

7. 配列と ArrayList の違いは何か？いつ配列を使用すべきか？#

配列は基本型とオブジェクト型を含むことができ、ArrayList はオブジェクト型のみを含むことができる。
配列のサイズは固定されており、ArrayList のサイズは動的に変化する。
ArrayList はより多くのメソッドと機能を提供している。例えば：addAll ()、removeAll ()、iterator () など。

四、参考リンク#

無数の罠を持つ Java 面接問題の ArrayList