JavaのLinkedList

こんにちは！最近の講義はすべてArrayListリストの学習に費やされています。このデータ構造は非常に便利で、多くの問題を解決できます。ただし、Java には他にも多くのデータ構造があります。なぜ？まず第一に、既存のタスクの範囲は非常に広く、タスクごとに異なるデータ構造が最も効果的であるためです。今日は、新しい構造である二重リンクリストLinkedListについて説明します。これがどのように機能するのか、二重接続と呼ばれる理由、そしてArrayListとの違いを理解してみましょう。LinkedListでは、要素は実際にはチェーン内のリンクです。各要素には、保存されるデータに加えて、前後の要素へのリンクがあります。これらのリンクを使用すると、ある要素から別の要素に移動できます。次のように作成されます。

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

結論：

[Hello World! My name is Earl, I love Java, I live in Moscow]

リストの構造は次のようになります。 新しい要素がどのように追加されるかを見てみましょう。これは、 を使用して行われますadd()。

earlBio.add(str2);

このコード行の時点では、リストは 1 つの要素 ( string ) で構成されていますstr1。図で次に何が起こるかを見てみましょう: 結果としてstr2、str1それらに保存されているリンクを介して接続されるようになりnext、そしてprevious: これで、二重リンクリストの主なアイデアを理解する必要があります。LinkedListこのリンクのチェーンのおかげで、要素は1 つのリストになります。の内部にはLinkedList、 のArrayListような配列はありません。ArrayListのすべての作業は(概して) 内部配列の操作に帰着します。 すべての作業はLinkedListリンクの変更に帰着します。 これは、リストの中央に要素を追加すると非常に明確にわかります。

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

ご覧のとおり、オーバーロードされたメソッドを使用すると、add()新しい要素に特定のインデックスを指定できます。この場合、と のstr2間に行を追加します。これは内部で何が起こるかです: そして、内部リンクを変更した結果、要素はリストに正常に追加されます: これで、3 つの要素すべてがリンクされました。チェーンに沿った最初の要素から最後の要素に移動し、戻ることができます。挿入については大体わかりましたが、要素の削除についてはどうすればよいでしょうか? 動作原理は同じです。削除される要素の「側面」にある 2 つの要素のリンクを再定義するだけです。 str1str3str2next

public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

インデックス 1 の要素 (リストの中央にあります) を削除すると、次のようになります。 リンクを再定義すると、望ましい結果が得られます。 削除とは異なり、ArrayList配列要素などのシフトはありません。str1要素と要素の参照を再定義するだけですstr3。現在、それらは相互に指しているため、オブジェクトはstr2このリンクのチェーンから「ドロップアウト」され、リストの一部ではなくなります。

メソッドの概要

メソッドLinkedListと多くの類似点があります。ArrayListたとえばadd()、 、remove()、indexOf()、clear()、contains()(リストに含まれる要素)、set()(置換による要素の挿入) などのメソッドsize()は両方のクラスに存在します。add()(例とでわかったようにremove()) それらの多くは内部的には異なりますが、最終的には同じことを行います。ただし、LinkedListリストの先頭と末尾を操作するための別のメソッドがあり、これらは には存在しませんArrayList。

• addFirst(), addLast(): リストの先頭/末尾に要素を追加するメソッド

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

結論：

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

その結果、フォードがリストのトップとなり、フィアットが最下位となった。

• peekFirst(), peekLast(): リストの最初/最後の要素を返します。nullリストが空の場合に戻ります。

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

結論：

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): リストの最初/最後の要素を返し、それをリストから削除します。nullリストが空の場合に返す

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println("What's left on the list?");
   System.out.println(cars);
}

結論：

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): リスト要素の配列を返します。

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

結論：

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

LinkedListこれで、それがどのように機能するか、および とどのように異なるかが わかりましたArrayList。それを使用する利点は何ですかLinkedList? まず第一に、リストの中央を操作します。途中での挿入と削除は、LinkedListよりもはるかに簡単ですArrayList。隣接する要素のリンクを再定義するだけで、不要な要素がリンクの連鎖から「抜け落ち」ます。私たちにいる間ArrayList：

• 十分なスペースがあるかどうかを確認してください（挿入時）
• 十分でない場合は、新しい配列を作成し、そこにデータをコピーします (貼り付け時)
• 要素を削除/挿入し、他のすべての要素を右/左にシフトします (操作の種類に応じて)。さらに、このプロセスの複雑さはリストのサイズに大きく依存します。10 個の要素をコピー/移動することと、100 万個の要素で同じことを行うことはまったく別のことです。

つまり、プログラム内でリストの中央で挿入/削除操作が頻繁に発生する場合は、LinkedListよりも高速になるはずですArrayList。

理論的には

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for(int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

結論：

Время работы для LinkedList (в мorсекундах) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for (int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

結論：

Время работы для ArrayList (в миллисекундах) = 181

突然！LinkedListリストの中央に 100 個の要素を挿入するという、より効率的であるはずの操作を実行しているように見えます。そして、リストは巨大です - 5,000,000 要素:ArrayList要素を挿入するたびに、数百万の要素を移動する必要がありました。彼の勝利の理由は何でしょうか？ まず、要素はArrayList一定の時間内にアクセスされます。次のことを示す場合:

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

[2_000_000]の場合、ArrayList内部に配列があるため、これはメモリ内の特定のアドレスになります。一方、LinkedListアレイはそうではありません。リンクのチェーンに沿って要素番号 2_000_000 を検索します。彼にとって、これはメモリ内のアドレスではなく、まだ到達する必要があるリンクです。

fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………

その結果、リストの途中で挿入（削除）するたびに、ArrayListアクセスすべきメモリ内の正確なアドレスはすでにわかっていますが、LinkedListそれでも正しい場所を「見つける」必要があります。 第二に、物質は「それ自体」の構造の中にありますArrayList。内部配列の展開、すべての要素のコピー、および要素のシフトは、特別な内部関数 - によって実行されますSystem.arrayCopy()。このジョブ用に特別に最適化されているため、非常に高速に動作します。しかし、目的のインデックスまで「ストンピング」する必要がない状況では、LinkedList実際にはより良く表示されます。たとえば、挿入がリストの先頭に行われる場合です。そこに 100 万個の要素を挿入してみましょう。

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       //write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //calculate the difference
       System.out.println("Result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

結論：

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

全く違う結果になりました！リストの先頭に 100 万個の要素を挿入するには43 秒以上かかりましたArrayListが、LinkedList挿入は 0.1 秒で完了しました。LinkedListこの状況では、リンクのチェーンを毎回リストの中央まで「実行」する必要がなかったのはまさに事実でした。彼はリストの先頭で必要なインデックスをすぐに見つけました。そこでは動作原理の違いがすでに彼の側にありました :) 実際、「ArrayList対LinkedList」の議論は非常に広範囲に広がっており、現時点ではこれについては深く掘り下げません。レベル。覚えておく必要がある主な点は次のとおりです。

• 「紙の上の」特定のコレクションのすべての利点が実際に機能するわけではありません（リストの真ん中の例を使用してこれを調べました）
• コレクションを選択するときは、極端に考えるべきではありません (「ArrayListいつでも高速です。使用すれば間違いはありません。LinkedList長い間誰も使用していません。」)。

作者のLinkedListJoshua Bloch ですらそう言っていますが :) ただし、この見方は 100% 正しいわけではなく、私たちはこれを確信しています。前の例では、LinkedList400 倍 (!) 高速に動作しました。LinkedListもう 1 つは、それが最良の選択となる状況は実際にはほとんどないということです。しかし、彼らは存在しており、適切なタイミングでLinkedList真剣にあなたを助けてくれるでしょう。講義の冒頭で話した内容を忘れないでください。タスクごとに異なるデータ構造が最も効果的です。問題の状況がすべて判明するまでは、どのデータ構造がより優れているかを 100% の自信を持って言うことは不可能です。後でこれらのコレクションについて詳しく知ることになり、選択が容易になります。ただし、最も単純で最も効果的なオプションは常に同じです。プログラムの実際のデータで両方をテストします。そうすれば、両方のリストの結果を自分の目で確認できるので、間違いなく失敗することはありません:)