やあ！最新のレッスンはすべてArrayListに専念しました。このデータ構造は非常に便利で便利です。たくさんのタスクを処理できます。しかし、Java には他にも多くのデータ構造があります。なぜ？何よりも、タスクの範囲は膨大であり、最も効率的なデータ構造はタスクごとに異なるためです。今日は、新しい構造であるJava LinkedList、二重リンク リストについて説明します。
![リンクリスト - 1]()
これがどのように構成されているのか、二重リンクと呼ばれる理由、 ArrayListとの違いを見てみましょう。Java LinkedList内の要素は、実際には単一のチェーン内のリンクです。各要素には、データに加えて、前後の要素への参照も格納されます。これらの参照を使用すると、ある要素から別の要素に移動できます。作成方法は次のとおりです。
![リンクリスト - 2]()
新しい要素を追加する方法を見てみましょう。これはadd()メソッドを使用して行われます。
![リンクリスト - 3]()
結果として、str2とstr1 は、リストのこのノードに格納されている 次のリンクと前のリンクを介してリンクされます。![リンクリスト - 4]()
これで、二重リンク リストの主な概念を理解できるはずです。このリンクのチェーンは、まさにLinkedList要素を単一のリストにします。ArrayListとは異なり、LinkedList には配列や配列のようなものが内部にありません。ArrayList を扱うすべての (ほとんどの) 作業は、結局のところ内部配列を操作することになります。Java LinkedListを使用した作業つまり、リンクを変更することになります。これは、リストの中央に要素を追加すると非常に明確にわかります。
![リンクリスト - 5]()
![リンクリスト - 6]()
![リンクリスト - 7]()
リンクを更新すると、望ましい結果が得られます。 ArrayList![リンクリスト - 8]()
の削除操作とは異なり、ここでは配列要素をシフトしたり、実行したりする必要はありません。その種類のものなら何でも。str1とstr3のリンクを更新するだけです。それらは相互に指すようになり、str2 はリンクのチェーンから 「ドロップアウト」され、リストの一部ではなくなりました。
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);
}
}
新しい要素を追加する方法を見てみましょう。これはadd()メソッドを使用して行われます。
earlBio.add(str2);
結果として、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);
}
}
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);
}
}
リンクを更新すると、望ましい結果が得られます。 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 + '\'' +
'}';
}
}
- 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());
}
- 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);
}
- 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));
}
- 十分なスペースがあるかどうかを確認します（挿入時）
- そうでない場合は、新しい配列を作成し、そこにデータをコピーします（挿入時）
- 要素を削除/挿入し、他のすべての要素を右/左に移動します (操作の種類に応じて)。そして、このプロセスの複雑さはリストのサイズに大きく依存します。10 個の要素をコピー/移動することと、100 万個の要素で同じことを行うことはまったく別のことです。
理論的には
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));
}
}
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));
}
}
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
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());
}
}
}
- 特定のコレクションの理論上の利点のすべてが現実に常に機能するわけではありません (リストの中央に関係する例でこれを確認しました)。
- コレクションの選択に関しては、極端な立場を採用しないでください (「ArrayListは常に高速です。これを使用すれば、間違いはありません。長い間LinkedListを使用している人はいません」)。
|
さらに読む: |
|---|
GO TO FULL VERSION