LinkedList コレクションの紹介

1. 歴史LinkedList

Java には、C++ 言語から継承した別のコレクション クラスがあります。これはLinkedList「リンクリスト」を実装するクラスです。

外見上、 はLinkedListと同じように見えますArrayList。クラスLinkedListには、クラスと同じメソッドがすべて含まれていますArrayList。LinkedList原則として、 an の代わりにa をいつでも使用できArrayList、すべてが機能します。

では、なぜ別のリスト クラスが必要なのでしょうか?

答えはLinkedListクラスの内部構造にすべて関係しています。配列の代わりに、二重リンクリストを使用します。それが何であるかについては、後ほど説明します。

クラスLinkedListの内部構造が異なるため、リストの途中に要素を最も速く挿入できます。

インターネットでは、ArrayListとLinkedListクラスの比較がよく見つかります。

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

すべてが十分に明らかであるように思えます。リストに要素を頻繁に挿入する必要がある場合は、LinkedList; を使用してください。まれな場合は、ArrayList を使用します。しかし現実は少し異なります。

2. 誰も使わないLinkedList

誰も使いませんLinkedList。

このクラスの作成者でさえ、LinkedList最近ツイートしました：「実際に使っている人はいますかLinkedList？私がそれを書きましたが、私は決して使いません。」

それで、どういうことですか？

まず、クラスArrayListはリストの中央に要素を非常に迅速に挿入できるようになりました。リストの途中に要素を挿入する場合は、挿入ポイントの後のすべての要素をリストの末尾に向かって 1 ずつシフトする必要があります。これには時間がかかりました。

しかし今ではすべてが変わってしまいました。配列のすべての要素はメモリの同じブロック内で互いに近くにあるため、要素をシフトする操作は非常に高速な低レベル コマンドによって実行されます。System.arraycopy()

さらに、今日のプロセッサには、通常、配列全体を保持できる大規模なキャッシュが搭載されているため、配列要素をメモリ内ではなくキャッシュ内でシフトできます。100 万個の要素が 1 ミリ秒で簡単にシフトされます。

次に、イテレータを使用して要素を挿入すると、クラスは要素をすばやく挿入できます。LinkedListイテレータを使用して を実行しLinkedList、常に新しい要素を挿入 (または既存の要素を削除) する場合、操作は非常に高速になります。

LinkedListループ内のオブジェクトに要素を単純に追加する場合、高速な各挿入操作には、低速な「要素の取得」操作が伴います。

現実はこれにはるかに近いです。

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

操作から要素を取得するのにLinkedListこれほど時間がかかるのはなぜですか?

の構造を少し理解すれば、その質問に答えることができますLinkedList。

3. どのようにLinkedList構成されているか

LinkedListは とは内部構造が異なりますArrayList。要素を格納するための内部配列はありません。代わりに、二重インクリストと呼ばれるデータ構造を使用します。

二重リンクリストの各要素には、前の要素と次の要素への参照が格納されます。これは店の行列に似ており、各人は自分の前に立っている人も後ろに立っている人も覚えています。

このようなリストはメモリ内では次のようになります。

先頭と末尾 (背景が灰色のセル) はfirstとlast変数で、Nodeオブジェクトへの参照を保存します。

中央には、Nodeオブジェクト (変数ではなくオブジェクト) のチェーンがあります。それぞれは次の 3 つのフィールドで構成されます。

• prev—前のオブジェクト (背景が黄色のセル) への参照Node(リンク) を保存します。
• value—リストのこの要素の値を保存します (背景が緑色のセル)。
• next—次のオブジェクト（青色の背景のセル）への参照（リンク）を保存します。Node

next2 番目のオブジェクト (アドレス F24) は、最初のオブジェクトの次 ( ) であり、 prev3 番目のオブジェクトの前のオブジェクト ( ) です。3 番目のオブジェクトの黄色のフィールドにはアドレス F24 が含まれ、最初のオブジェクトの青色のフィールドにはアドレス F24 が含まれています。

1 番目と 3 番目のオブジェクトからの矢印は、同じ 2 番目のオブジェクトを指しています。したがって、このように矢印を描く方が正確です。

4. リンクリストに要素を挿入する

このように誰かをラインに追加するには、隣り合った 2 人の人の許可を得る必要があります。一人目は新人を「私の後ろの人」と覚え、二人目は「私の前の人」と覚えます。

必要なのは、隣接する 2 つのオブジェクトの参照を変更することだけです。

2 番目と 3 番目のオブジェクトの参照を変更することで、リストに新しい項目を追加しました。新しいオブジェクトは、古い 2 番目のオブジェクトにとっては次のオブジェクトであり、古い 3 番目のオブジェクトにとっては前のオブジェクトです。そしてもちろん、新しいオブジェクト自体は正しい参照を保存する必要があります。その前のオブジェクトは古い 2 番目のオブジェクトで、次のオブジェクトは古い 3 番目のオブジェクトです。

要素の削除はさらに簡単です。たとえば、リストから 100 番目のオブジェクトを削除したい場合は、101 番目のオブジェクトを指すように 99 番目のオブジェクトのフィールドを変更し、101 番目のオブジェクトのフィールドを変更するだけnextですprev。オブジェクトが 99 番目を指すようにします。それでおしまい。

しかし、100 番目のオブジェクトを取得するのはそれほど簡単ではありません。

5. リストから要素を削除する

リンクされたリストの 100 番目の要素を取得するには、次の操作を行う必要があります。

最初のオブジェクトを取得します。これは、オブジェクトfirst内の変数を使用して実行しますLinkedList。1 番目のオブジェクトのフィールドnextには 2 番目のオブジェクトへの参照が格納されます。これで 2 番目のオブジェクトが取得されます。2 番目のオブジェクトには 3 番目のオブジェクトへの参照があり、以下同様に続きます。

100 番目のオブジェクトへの参照を取得する必要がある場合は、1 番目から 100 番目までのすべてのオブジェクトを順番に移動する必要があります。そして、リスト内の 100 万番目の要素が必要な場合は、100 万を超えるオブジェクトを次々に反復処理する必要があります。

また、これらのオブジェクトが異なる時点でリストに追加された場合、それらはメモリの異なる部分に配置され、同時にプロセッサのキャッシュに到達する可能性は低くなります。これは、リンクされたリストの要素の反復処理が遅いだけでなく、非常に遅いことを意味します。

それが私たちが取り組んでいることです。

では、なぜこの遅いLinkedList仕組みを教えているのでしょうか?

さて、就職面接では、とどのようLinkedListに違うのかArrayListを尋ねられるでしょう。絶対。