1. 概要

コレクションに関しては、Java標準ライブラリには豊富なオプションが用意されています。 これらのオプションの中には、ArrayListおよびLinkedListとして知られる2つの有名なList実装があり、それぞれ独自のプロパティとユースケースがあります。

このチュートリアルでは、これら2つが実際にどのように実装されているかを見ていきます。 次に、それぞれのアプリケーションを評価します。

2. ArrayList

内部的には、ArrayListは配列を使用してListインターフェイスを実装しています。 Javaでは配列は固定サイズであるため、ArrayListは初期容量のある配列を作成します。 途中で、デフォルトの容量よりも多くのアイテムを格納する必要がある場合は、その配列が新しくより広々とした配列に置き換えられます。

そのプロパティをよりよく理解するために、このデータ構造を3つの主要な操作(アイテムの追加インデックスによる取得インデックスによる削除)に関して評価してみましょう。

2.1. 追加

空のArrayListを作成する場合、はバッキング配列をデフォルト容量(現在は10)で初期化します。

その配列がまだいっぱいになっていないときに新しいアイテムを追加するのは、そのアイテムを特定の配列インデックスに割り当てるのと同じくらい簡単です。 この配列インデックスは、実際にリストに追加しているため、現在の配列サイズによって決定されます。

backingArray[size] = newItem;
size++;

したがって、の最良の場合と平均的な場合、追加操作の時間計算量はO(1) であり、これはかなり高速です。 ただし、バッキングアレイがいっぱいになると、addの実装の効率が低下します。

新しいアイテムを追加するには、まず容量の大きい新しいアレイを初期化し、既存のすべてのアイテムを新しいアレイにコピーする必要があります。現在の要素をコピーした後でのみ、新しいアイテムを追加できます。 したがって、最初に n 要素をコピーする必要があるため、最悪の場合、時間計算量は O(n)になります。

理論的には、新しい要素の追加はamortized一定時間で実行されます。 つまり、 n 要素を追加するには、 O(n)時間が必要です。 ただし、コピーのオーバーヘッドが原因で、一部の単一の追加のパフォーマンスが低下する場合があります。 

2.2. インデックスによるアクセス

インデックスでアイテムにアクセスするのは、ArrayListが本当に優れているところです。 インデックスiのアイテムを取得するには、バッキング配列からithインデックスにあるアイテムを返す必要があります。 その結果、 インデックス操作によるアクセスの時間計算量は常にO(1)です。 

2.3. インデックスで削除

ArrayList、からインデックス6を削除するとします。これは、バッキング配列の要素15に対応します。

目的の要素を削除済みとしてマークした後、その後のすべての要素を1つのインデックスだけ戻す必要があります。 明らかに、要素が配列の先頭に近いほど、より多くの要素を移動する必要があります。 したがって、時間計算量は O(1) 最良の場合との上) 平均および最悪の場合。

2.4. アプリケーションと制限

通常、 ArrayList は、 List の実装が必要な場合、多くの開発者にとってデフォルトの選択肢です。 実際のところ、読み取りの数が書き込みの数よりもはるかに多い場合は、実際には賢明な選択です。

場合によっては、同じ頻度の読み取りと書き込みが必要になります。可能なアイテムの最大数の見積もりがある場合でも、ArrayListを使用することは理にかなっています。 その場合は、ArrayListを初期容量で初期化できます。

int possibleUpperBound = 10_000;
List<String> items = new ArrayList<>(possibleUpperBound);

この見積もりにより、多くの不要なコピーと配列の割り当てを防ぐことができます。

さらに、 配列は、Javaではint値によってインデックスが付けられます。 したがって、232を超える要素をJava配列に格納することはできず、その結果、ArrayListに格納することはできません。

3. LinkedList

LinkedList は、その名前が示すように、リンクされたノードのコレクションを使用して要素を格納および取得します。 たとえば、4つの要素を追加した後のJava実装の外観は次のとおりです。

各ノードは2つのポインターを維持します。1つは次の要素を指し、もう1つは前の要素を参照します。 これを拡張すると、二重リンクリストには、最初と最後のアイテムを指す2つのポインターがあります。

繰り返しになりますが、同じ基本的な操作に関してこの実装を評価してみましょう。

3.1. 追加

新しいノードを追加するには、まず、現在の最後のノードを新しいノードにリンクする必要があります。

そして最後のポインタを更新します:

これらの操作はどちらも簡単であるため、追加操作の時間計算量は常に O(1)です。

3.2. インデックスによるアクセス

LinkedListは、ArrayListとは対照的に、高速ランダムアクセスをサポートしていません。 したがって、インデックスで要素を見つけるには、リストの一部をトラバースする必要があります手動で

最良の場合、要求されたアイテムがリストの最初または最後に近い場合、時間計算量は次のように速くなります。 O(1)。 ただし、平均的なシナリオと最悪のシナリオでは、 の上) 多くのノードを次々に調べる必要があるため、アクセス時間。

3.3. インデックスで削除

アイテムを削除するには、最初にリクエストされたアイテムを見つけてから、リストからリンクを解除する必要があります。 したがって、アクセス時間によって時間計算量が決まります。つまり、 O(1)が最良の場合、 O(n)が平均および最悪のシナリオです。

3.4. アプリケーション

LinkedListsは、加算率が読み取り率よりもはるかに高い場合に適しています。

また、ほとんどの場合、最初または最後の要素が必要な場合に、読み取りが多いシナリオで使用できます。 LinkedListDequeインターフェースも実装しており、コレクションの両端への効率的なアクセスをサポートしています。

一般に、それらの実装の違いがわかっている場合は、特定のユースケースに合わせて簡単に選択できます。

たとえば、多くの時系列イベントをリストのようなデータ構造に格納するとします。 私たちは毎秒イベントのバーストを受け取ることを知っています。

また、定期的にすべてのイベントを次々に調べて、いくつかの統計を提供する必要があります。 このユースケースでは、追加レートが読み取りレートよりもはるかに高いため、LinkedListの方が適しています。

また、すべての項目を読み取るため、 O(n)上界を打ち負かすことはできません。

4. 結論

このチュートリアルでは、最初に、ArrayListLinkListsがJavaでどのように実装されているかについて詳しく説明しました。

また、これらのそれぞれについてさまざまなユースケースを評価しました。