Geekly Articles each Day

LinkedListの裏側には何がありますか？

こんにちは、habrachitateli！

ArrayListの仕組みは理解できます。 このテーマには多くの記事があり、そのうちのいくつかは素晴らしい写真で説明されているため、初心者でもすぐに明らかになります。 このテーマに関する最高の記事に、 「写真のデータ構造」を含めます。 ArrayList "はtarzan82によって書かれました 。

同じ作者がLinkedListの仕組みについて説明していますが、Java 7のリリースでは一部のデータが古くなっているため、 tarzan82の数字を使用してこのコレクション内で何が起こっているかを詳細に理解することはすでに困難です。 はい、そして他の情報源では明確な写真に出会えなかったため、この記事を書くというアイデアが生まれました。

したがって、 LinkedListはListとDequeの 2つのインターフェイスを実装するクラスです。 これにより、任意の（ nullを含む）要素から双方向キューを作成できます。 リンクリストに配置される各オブジェクトは、ノード（ノード）です。 各ノードには、要素、前のノードと次のノードへのリンクが含まれます。 実際、リンクリストは一連のノードで構成され、各ノードは、作成時に定義されたタイプのオブジェクトを格納するように設計されています。

シンプルで馴染みのあるコード行を作成するとどうなるかを考えてみましょう。

1.リンクリストを作成する


LinkedList<Integer> numbers = new LinkedList<>();

このコードは、 LinkedListクラスのオブジェクトを作成し、 数値リンクに保存します。 作成されたオブジェクトは、整数（ Integer ）を格納するように設計されています。 このオブジェクトは空ですが。

LinkedListクラスには3つのフィールドが含まれます。

 //  transient   ,      //  transient int size = 0; transient Node<E> first; transient Node<E> last;



2.リンクリストの最後にオブジェクトを追加する


 numbers.add(8);

このコードは、以前に作成されたリストの最後に番号8を追加します。 「フード」の下で、このメソッドは、タイプIntegerのオブジェクトの作成、新しいノードの作成、このノードの項目フィールドでクラスIntegerのオブジェクトの設定、リストの末尾へのノードの追加、隣接ノードへのリンクの設定を提供する他の多くのメソッドを呼び出します。

LinkedListは、ネストされた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; } }

オブジェクトがリストに追加されるたびに、1つの新しいノードが作成され、リンクリストのフィールドの値（ size 、 first 、 last ）も変更されます。

最初の要素を追加する場合、前の要素と次の要素が存在しないノードが作成されます。 nullの場合、コレクションのサイズは1増加し、作成されたノードはコレクションの最初と最後の要素として設定されます。

コレクションに別のアイテムを追加します。

 numbers.add(5);

最初に、新しい要素（番号5）のノードが作成され、コレクションの既存の要素（番号8のノード）へのリンクが前の要素として確立され、作成されたノードの次の要素はnullのままです。 また、この新しいノードは最後にリンクリストの変数に保存されます。

図に見られるように 4、コレクションの最初の要素（インデックス0の下）は、これまでのところ、次の要素としてnullを参照しています 。 これで、このリンクが置き換えられ、最初の要素がコレクションの2番目の要素（インデックス1の下）を参照し始め、コレクションのサイズも増加します。

3.リンクリストの中央にオブジェクトを追加する


 numbers.add(1, 13);

LinkedListを使用すると、リストの中央にアイテムを追加できます。 これを行うには、 add（index、element）メソッドを使用します。indexは、要素要素が挿入されるリスト内の場所です。

add（要素）メソッドと同様に、このメソッドは他のいくつかのメソッドを呼び出します。 最初に、 インデックスの値がチェックされます。これは、リストのサイズ以下の正数でなければなりません。 インデックスがこれらの条件を満たさない場合、 IndexOutOfBoundsExceptionがスローされます。

次に、 インデックスがコレクションのサイズに等しい場合、実際には既存のリストの最後に要素を挿入する必要があるため、段落2で説明したアクションが実行されます。

インデックスがリストのサイズと等しくない場合、この挿入の前に指定されたインデックスを持つ要素の前で挿入が実行されます。 この場合、値が5のノードの前。

まず、 ノード（インデックス）メソッドを使用して、新しいノードを挿入する必要があるインデックスの下に現在あるノードを特定します。 このノードの検索は、リストの半分の単純なforループを使用して実行されます（インデックス値に応じて-最初から要素まで、または最後から要素まで）。 次に、新しい要素（番号13）のノードが作成され、前の要素へのリンクが要素の番号が8のノードに設定され、次の要素へのリンクが要素の番号が5のノードに設定されます。

これで、リンクが連続して置き換えられます：新しい要素に続く要素については、前の要素へのリンクが置き換えられ（値13のノードを指すようになります）、新しい要素の前のものについては、次の要素へのリンクが置き換えられます（値5のノードを指します）。 そして最後になりましたが、リストのサイズが大きくなります：

4.リストからオブジェクトを削除する


リストから1つの要素を削除するために、 LinkedListクラスは、戻り値のタイプ、スローされた例外の有無、および削除する要素を指定するメソッドが異なる最大 10個のメソッドを提供します。

値によってリンクリストからアイテムを削除することを検討してください。 以下のリストから値5のアイテムを削除します。

 numbers.remove(Integer.valueOf(5));

次の行で値が5の要素を削除しようとすると、 remove（オブジェクト）メソッドで受け入れられる値は正確にオブジェクトであることに注意してください。
 numbers.remove(5);

それからIndexOutOfBoundsExceptionを取得します、なぜなら コンパイラーはインデックスとして番号5を取り、 remove（インデックス）メソッドを呼び出します。

では、 remove（オブジェクト）メソッドを呼び出すとどうなりますか？ まず、目的のオブジェクトがリストのノードに格納されているすべての要素と順番に比較され、ゼロノードから開始されます。 要素が目的のオブジェクトと等しいノードが見つかった場合、要素が最初に格納されるのは個別の変数です。 次に、隣接するノードのリンクが再定義され、相互に指すようになります。

次に、削除されたオブジェクトを含むノードの値がゼロになり、コレクションのサイズも小さくなります。

ここで、メモリ内の削除されたノードから要素を保存したポイントに戻ります。 このデータを他のどこでも使用しなかった場合、なぜこれを行ったのでしょうか。 事実、 remove（オブジェクト）メソッドによって呼び出されたunlink（ノード）メソッドによって返されたデータは必要なかったため、作業の結果として考慮しているメソッドは削除された要素を返しません。 ただし、 unlink（ノード）メソッドも呼び出すremove（インデックス）メソッドを使用すると、この要素の値は、最初にunlink（ノード）メソッドによって、次にremove（インデックス）メソッドによって順番に返されます 。 削除された要素の値を返す他のメソッドでも同様の状況が観察され、内部のリンクを切断する他のメソッドのみが呼び出されます： poll（） 、 pollFirst（） 、 remove（）およびremoveFirst（）メソッド、これはunlinkFirst（ノード）メソッド、およびpollLastメソッド（）およびremoveLast（）は、 unlinkLast（ノード）メソッドです。

したがって、このコレクションを使用するかどうかを決定するときにLinkedListについて覚えておくべきことは次のとおりです。


参照資料


LinkedListソースコード（JDK 8）
LinkedListドキュメント

Source: https://habr.com/ru/post/J337558/

More articles:


All Articles