Java リンクリスト

やあ！最新のレッスンはすべてArrayListに専念しました。このデータ構造は非常に便利で便利です。たくさんのタスクを処理できます。しかし、Java には他にも多くのデータ構造があります。なぜ？何よりも、タスクの範囲は膨大であり、最も効率的なデータ構造はタスクごとに異なるためです。今日は、新しい構造であるJava LinkedList、二重リンク リストについて説明します。 これがどのように構成されているのか、二重リンクと呼ばれる理由、 ArrayListとの違いを見てみましょう。Java LinkedList内の要素は、実際には単一のチェーン内のリンクです。各要素には、データに加えて、前後の要素への参照も格納されます。これらの参照を使用すると、ある要素から別の要素に移動できます。作成方法は次のとおりです。

public class Main {

   public static void main(java.lang.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 Canada");

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

       System.out.println(earlBio);

   }
}

出力: [Hello World! 私の名前はアールです。Java が大好きで、カナダに住んでいます。] リストは次のようになります。 新しい要素を追加する方法を見てみましょう。これはadd()メソッドを使用して行われます。

earlBio.add(str2);

コードのこの時点では、リストは 1 つの要素 ( String str1 )で構成されています。図で次に何が起こるかを見てみましょう: 結果として、str2とstr1 は、リストのこのノードに格納されている 次のリンクと前のリンクを介してリンクされます。 これで、二重リンク リストの主な概念を理解できるはずです。このリンクのチェーンは、まさにLinkedList要素を単一のリストにします。ArrayListとは異なり、LinkedList には配列や配列のようなものが内部にありません。ArrayList を扱うすべての (ほとんどの) 作業は、結局のところ内部配列を操作することになります。Java LinkedListを使用した作業つまり、リンクを変更することになります。これは、リストの中央に要素を追加すると非常に明確にわかります。

public class Main {

   public static void main(java.lang.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 Canada");

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

       System.out.println(earlBio);

   }
}

ご覧のとおり、オーバーロードされたadd()メソッドを使用すると、新しい項目に特定のインデックスを指定できます。この場合、 str1とstr3の間にString str2を追加します。これは内部で起こることです: 内部リンクを変更した後、str2 がリストに正常に追加されました: これで 3 つの要素すべてが接続されました。次のリンクを介して、チェーンの最初の要素から最後の要素に移動し、再び戻ることができます。挿入についてはかなり慣れていますが、要素の削除についてはどうすればよいでしょうか? 原理は全く同じです。削除する要素の「左側と右側」の 2 つの要素内のリンクを更新するだけです。

public class Main {

   public static void main(java.lang.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 Canada");

       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() (既存の要素を置き換える) などのメソッドがあります。サイズ()。それらの多くは内部で異なる動作をしますが ( 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'}] 結局、リストの一番上は「Ford」になります 。そして最後に「フィアット」。

• PeakFirst()、PeakLast() : これらのメソッドはリスト内の最初/最後の要素を返します。リストが空の場合は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 on the list?");
   System.out.println(cars);
}

出力: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} リストには何が残っていますか? [車{model='ブガッティ ヴェイロン'}]

• 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 taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

出力: LinkedList にかかった時間 (ミリ秒) = 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 taken by 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));

ArrayList [2_000_000] は特定のメモリ アドレスです ( 結局のところ、リストには内部配列があります)。ただし、LinkedListには配列がありません。リンクのチェーンに沿って要素番号 2_000_000 を検索します。LinkedList の場合、これはメモリ アドレスではなく、到達する必要があるリンクです ( 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.... その結果、リストの途中で挿入 (削除) するたびに、 , 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("The 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 今度は、まったく異なる結果が得られます。 ArrayList ではリストの先頭に 100 万項目を挿入するのに 43 秒以上かかりましたが、LinkedList では0.1 秒で完了しました。 LinkedList は、毎回リンクのチェーンを経由してリストの中央に到達する必要がないため、ここでは利点がありました。リストの先頭で必要なインデックスがすぐに見つかるため、アルゴリズムが異なることがすでに利点となります。:) 実際、「ArrayListとLinkedList」の議論は非常に広く広まっており、現在のレベルではこれについては深く掘り下げません。覚えておく必要がある主な点は次のとおりです。

• 特定のコレクションの理論上の利点のすべてが現実に常に機能するわけではありません (リストの中央に関係する例でこれを確認しました)。
• コレクションの選択に関しては、極端な立場を採用しないでください (「ArrayListは常に高速です。これを使用すれば、間違いはありません。長い間LinkedListを使用している人はいません」)。

LinkedListの作者である Joshua Blochでさえ、これが事実であると言っていますが。:) それでも、この見方は 100% 正しいわけではなく、私たちはこれを確信しています。前の例では、LinkedList は400 (!) 倍高速でした。もう 1 つは、 LinkedList が最適な選択肢となる状況は実際にはほとんどないということです。しかし、それらは存在しており、適切なタイミングでLinkedList が作成されます。あなたに十分な報酬を与えることができます。レッスンの冒頭で述べたことを忘れないでください。最も効率的なデータ構造はタスクごとに異なります。タスクの条件をすべて把握するまでは、どのデータ構造が最適であるかを 100% 確信することは不可能です。これらのコレクションについては後ほど詳しく説明するので、選択が容易になります。ただし、最も単純で最も効果的なオプションは常に同じです。プログラムで使用される実際のデータで両方を試してください。そうすれば、両方のタイプのリストがどのように機能するかを自分の目で確認できるようになり、間違いなく失敗することはなくなります。:)学んだことを強化するには、Java コースのビデオ レッスンを視聴することをお勧めします。