JavaのLinkedList
リンクされたリストは、 収集フレームワーク java.util パッケージに存在します。このクラスは、二重リンク リスト データ構造の実装です。
通常のリンク リストと二重 LinkedList の主な違いは、二重リンク リストには、単一リンク リストにある次のポインタおよびデータとともに、通常は前のポインタと呼ばれる追加のポインタが含まれていることです。
LinkedList のコンストラクター:
LinkedList を作成するには、LinkedList クラスのオブジェクトを作成する必要があります。 LinkedList クラスは、リストの作成を可能にするさまざまなコンストラクターで構成されています。このクラスで使用できるコンストラクターは次のとおりです。
1. LinkedList(): このコンストラクターは、空のリンク リストを作成するために使用されます。 ll という名前の空の LinkedList を作成したい場合は、次のように作成できます。
LinkedList ll = 新しい LinkedList();
2. LinkedList(コレクション C): このコンストラクターは、コレクションのイテレーターによって返される、指定されたコレクションのすべての要素を含む順序付きリストを作成するために使用されます。 ll という名前の LinkedList を作成したい場合は、次のように作成できます。
LinkedList ll = 新しい LinkedList(C);
Java LinkedList のメソッド:
| 方法 | 説明 |
|---|---|
| add(int インデックス, E 要素) | このメソッドは、指定された要素をこのリスト内の指定された位置に挿入します。 |
| add(そしてそして) | このメソッドは、指定された要素をこのリストの末尾に追加します。 |
| addAll(int インデックス, コレクション c) | このメソッドは、指定されたコレクション内のすべての要素を、指定された位置からこのリストに挿入します。 |
| addAll(コレクションc) | このメソッドは、指定されたコレクション内のすべての要素を、指定されたコレクションのイテレータによって返される順序でこのリストの末尾に追加します。 |
| addFirst(E e) | このメソッドは、指定された要素をこのリストの先頭に挿入します。 |
| addLast(E e) | このメソッドは、指定された要素をこのリストの末尾に追加します。 |
| クリア（） | このメソッドは、このリストからすべての要素を削除します。 |
| クローン（） | このメソッドは、この LinkedList の浅いコピーを返します。 |
| contains(オブジェクト o) | このリストに指定された要素が含まれている場合、このメソッドは true を返します。 |
| 降順イテレータ() | このメソッドは、この両端キュー内の要素の反復子を逆の順序で返します。 |
| 要素（） | このメソッドは、このリストの先頭 (最初の要素) を取得しますが、削除はしません。 |
| get(int インデックス) | このメソッドは、このリスト内の指定された位置にある要素を返します。 |
| getFirst() | このメソッドは、このリストの最初の要素を返します。 |
| getLast() | このメソッドは、このリストの最後の要素を返します。 |
| IndexOf(オブジェクトo) | このメソッドは、このリスト内で指定された要素が最初に出現するインデックスを返します。このリストにその要素が含まれていない場合は -1 を返します。 |
| lastIndexOf(オブジェクトo) | このメソッドは、このリスト内で指定された要素が最後に出現したインデックスを返します。このリストにその要素が含まれていない場合は -1 を返します。 |
| listIterator(int インデックス) | このメソッドは、リスト内の指定された位置から始まる、このリスト内の要素のリスト反復子を (適切な順序で) 返します。 |
| オファー(E e) | このメソッドは、指定された要素をこのリストの末尾 (最後の要素) として追加します。 |
| OfferFirst(E および) | このメソッドは、指定された要素をこのリストの先頭に挿入します。 |
| OfferLast(E e) | このメソッドは、指定された要素をこのリストの最後に挿入します。 |
| ピーク（） | このメソッドは、このリストの先頭 (最初の要素) を取得しますが、削除はしません。 |
| ピークファースト() | このメソッドは、このリストの最初の要素を取得しますが、削除はしません。このリストが空の場合は null を返します。 |
| ピークラスト() | このメソッドは、このリストの最後の要素を取得しますが、削除はしません。このリストが空の場合は null を返します。 |
| ポーリング() | このメソッドは、このリストの先頭 (最初の要素) を取得して削除します。 |
| ポールファースト() | このメソッドは、このリストの最初の要素を取得して削除します。このリストが空の場合は null を返します。 |
| ポールラスト() | このメソッドは、このリストの最後の要素を取得して削除します。このリストが空の場合は null を返します。 |
| ポップ（） | このメソッドは、このリストで表されるスタックから要素をポップします。 |
| プッシュ(Eと) | このメソッドは、このリストで表されるスタックに要素をプッシュします。 |
| 取り除く（） | このメソッドは、このリストの先頭 (最初の要素) を取得して削除します。 |
| 削除(int インデックス) | このメソッドは、このリスト内の指定された位置にある要素を削除します。 |
| 削除(オブジェクトo) | このメソッドは、指定された要素が最初に出現した場合、このリストからそれを削除します。 |
| 削除最初() | このメソッドは、このリストから最初の要素を削除して返します。 |
| RemoveFirstOccurrence(オブジェクト o) | このメソッドは、このリスト内で最初に出現した指定された要素を削除します (リストを先頭から末尾まで走査するとき)。 |
| 削除最後() | このメソッドは、このリストから最後の要素を削除して返します。 |
| RemoveLastOccurrence(オブジェクト o) | このメソッドは、このリスト内で最後に出現した指定された要素を削除します (リストを先頭から末尾まで走査するとき)。 |
| set(int インデックス, E 要素) | このメソッドは、このリスト内の指定された位置にある要素を指定された要素に置き換えます。 |
| サイズ（） | このメソッドは、このリスト内の要素の数を返します。 |
| スプリッテレータ() | このメソッドは、このリスト内の要素に対して遅延バインディングおよびフェイルファストの Spliterator を作成します。 |
| toArray() | このメソッドは、このリスト内のすべての要素を適切な順序 (最初の要素から最後の要素まで) で含む配列を返します。 |
| toArray(T[] a) | このメソッドは、このリスト内のすべての要素を適切な順序 (最初の要素から最後の要素まで) で含む配列を返します。返される配列のランタイム型は、指定された配列のランタイム型です。 |
| toString() | このメソッドは、このリスト内のすべての要素を適切な順序 (最初の要素から最後の要素まで) で含む文字列を返します。各要素はカンマで区切られ、文字列は角かっこで囲まれます。 |
上記の操作の実装は次のとおりです。
ジャワ
// Java Program to Demonstrate> // Implementation of LinkedList> // class> > // Importing required classes> import> java.util.*;> > // Main class> public> class> GFG {> > > // Driver code> > public> static> void> main(String args[])> > {> > // Creating object of the> > // class linked list> > LinkedList ll => new> LinkedList();> > > // Adding elements to the linked list> > ll.add(> 'A'> );> > ll.add(> 'B'> );> > ll.addLast(> 'C'> );> > ll.addFirst(> 'D'> );> > ll.add(> 2> ,> 'E'> );> > > System.out.println(ll);> > > ll.remove(> 'B'> );> > ll.remove(> 3> );> > ll.removeFirst();> > ll.removeLast();> > > System.out.println(ll);> > }> }> |
出力
[D, A, E, B, C] [A]
上の図では、 AbstractList 、 CopyOnWriteArrayList 、および AbstractSequentialList はリスト インターフェイスを実装するクラスです。前述の各クラスには個別の機能が実装されています。彼らです：
- AbstractList: このクラスは、変更不可能なリストを実装するために使用されます。そのために必要なのは、この AbstractList クラスを拡張し、get() メソッドと size() メソッドのみを実装することだけです。 CopyOnWriteArrayList: このクラスはリスト インターフェイスを実装します。これは ArrayList の拡張バージョンであり、リストの新しいコピーを作成することによってすべての変更 (追加、設定、削除など) が実装されます。
LinkedList でさまざまな操作を実行する:
- 要素の追加
- 要素の更新
- 要素の削除
- 要素の反復処理
- Array(); へ
- サイズ（）;
- First() を削除します。
- last() を削除します。
操作 1: 要素の追加
ArrayList に要素を追加するには、add() メソッドを使用します。このメソッドは、さまざまなパラメーターに基づいて複数の操作を実行するためにオーバーロードされます。彼らです：
- add(Object): このメソッドは、LinkedList の最後に要素を追加するために使用されます。 add(int index, Object): このメソッドは、LinkedList の特定のインデックスに要素を追加するために使用されます。
上記の操作の実装は次のとおりです。
ジャワ
// Java program to add elements> // to a LinkedList> > import> java.util.*;> > public> class> GFG {> > > public> static> void> main(String args[])> > {> > LinkedList ll => new> LinkedList();> > > ll.add(> 'Geeks'> );> > ll.add(> 'Geeks'> );> > ll.add(> 1> ,> 'For'> );> > > System.out.println(ll);> > }> }> |
出力
[Geeks, For, Geeks]
操作 2: 要素の変更
要素を追加した後、要素を変更したい場合は、 set() メソッドを使用して行うことができます。 LinkedList にはインデックスが付けられているため、変更したい要素は要素のインデックスによって参照されます。したがって、このメソッドはインデックスと、そのインデックスに挿入する必要がある更新された要素を受け取ります。
上記の操作の実装は次のとおりです。
ジャワ
// Java program to change elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > > public> static> void> main(String args[])> > {> > LinkedList ll => new> LinkedList();> > > ll.add(> 'Geeks'> );> > ll.add(> 'Geeks'> );> > ll.add(> 1> ,> 'Geeks'> );> > > System.out.println(> 'Initial LinkedList '> + ll);> > > ll.set(> 1> ,> 'For'> );> > > System.out.println(> 'Updated LinkedList '> + ll);> > }> }> |
出力
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]
操作 3: 要素の削除
LinkedList から要素を削除するには、remove() メソッドを使用します。このメソッドは、さまざまなパラメーターに基づいて複数の操作を実行するためにオーバーロードされます。彼らです：
- Remove(Object): このメソッドは、LinkedList からオブジェクトを単純に削除するために使用されます。このようなオブジェクトが複数ある場合は、最初に出現したオブジェクトが削除されます。 Remove(int Index): LinkedList にはインデックスが付けられているため、このメソッドは整数値を受け取り、LinkedList 内の特定のインデックスに存在する要素を単純に削除します。要素を削除すると、要素のインデックスが更新され、LinkedList のオブジェクトも更新され、要素の削除後に新しいリストが生成されます。
上記の操作の実装は次のとおりです。
ジャワ
// Java program to remove elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > > public> static> void> main(String args[])> > {> > LinkedList ll => new> LinkedList();> > > ll.add(> 'Geeks'> );> > ll.add(> 'Geeks'> );> > ll.add(> 1> ,> 'For'> );> > > System.out.println(> 'Initial LinkedList '> + ll);> > > // Function call> > ll.remove(> 1> );> > > System.out.println(> 'After the Index Removal '> + ll);> > > ll.remove(> 'Geeks'> );> > > System.out.println(> 'After the Object Removal '> > + ll);> > }> }> |
出力
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]
操作 4: LinkedList の反復
LinkedList を反復処理するには複数の方法があります。最も有名な方法は、基本的な for ループを get() メソッドと組み合わせて使用し、特定のインデックスにある要素を取得する方法と高度な for ループを使用する方法です。
上記の操作の実装は次のとおりです。
ジャワ
// Java program to iterate the elements> // in an LinkedList> > import> java.util.*;> > public> class> GFG {> > > public> static> void> main(String args[])> > {> > LinkedList ll> > => new> LinkedList();> > > ll.add(> 'Geeks'> );> > ll.add(> 'Geeks'> );> > ll.add(> 1> ,> 'For'> );> > > // Using the Get method and the> > // for loop> > for> (> int> i => 0> ; i System.out.print(ll.get(i) + ' '); } System.out.println(); // Using the for each loop for (String str : ll) System.out.print(str + ' '); } }> |
出力
Geeks For Geeks Geeks For Geeks
操作 4: toArray(); を使用して、リストを To Array にリンクしました。
ジャワ
import> java.util.*;> public> class> GFG2 {> > public> static> void> main(String[] args)> > {> > LinkedList list=> new> LinkedList();> > list.add(> 123> );> > list.add(> 12> );> > list.add(> 11> );> > list.add(> 1134> );> > System.out.println(> 'LinkedList: '> + list);> > Object[] a = list.toArray();> > System.out.print(> 'After converted LinkedList to Array: '> );> > for> (Object element : a)> > System.out.print(element+> ' '> );> > }> }> |
出力
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134
オペレーション 5-size();
ジャワ
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> > public> static> void> main(String args[]) {> > LinkedList list => new> LinkedList();> > list.add(> 'Geeks for Geeks '> );> > list.add(> 'is best '> );> > // Displaying the size of the list> > System.out.println(> 'The size of the linked list is: '> + list.size());> > }> }> |
出力
The size of the linked list is: 2
操作 7 –removeFirst();
ジャワ
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> > public> static> void> main(String args[]) {> > > LinkedList list => new> LinkedList();> > list.add(> 10> );> > list.add(> 20> );> > list.add(> 30> );> > System.out.println(> 'LinkedList:'> + list);> > System.out.println(> 'The remove first element is: '> + list.removeFirst());> > // Displaying the final list> > System.out.println(> 'Final LinkedList:'> + list);> > }> }> |
出力
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]
操作 8-removelast();
ジャワ
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> > public> static> void> main(String args[])> > {> > > LinkedList list => new> LinkedList();> > list.add(> 10> );> > list.add(> 20> );> > list.add(> 30> );> > System.out.println(> 'LinkedList:'> + list);> > // Remove the tail using removeLast()> > System.out.println(> 'The last element is removed: '> + list.removeLast());> > // Displaying the final list> > System.out.println(> 'Final LinkedList:'> + list);> > // Remove the tail using removeLast()> > System.out.println(> 'The last element is removed: '> + list.removeLast());> > // Displaying the final list> > System.out.println(> 'Final LinkedList:'> + list);> > }> }> |
出力
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]
Java の LinkedList クラスは Java Collections Framework の一部であり、List インターフェイスのリンク リスト実装を提供します。これにより、各要素がその先行要素および後続要素にリンクされる、二重リンク リスト データ構造内の要素の格納と取得が可能になります。
Java で LinkedList を使用する方法を示す簡単な例を次に示します。
ジャワ
import> java.util.LinkedList;> > public> class> LinkedListExample {> > public> static> void> main(String[] args) {> > // Create a new linked list> > LinkedList linkedList => new> LinkedList();> > > // Add elements to the linked list> > linkedList.add(> 1> );> > linkedList.add(> 2> );> > linkedList.add(> 3> );> > > // Add an element to the beginning of the linked list> > linkedList.addFirst(> 0> );> > > // Add an element to the end of the linked list> > linkedList.addLast(> 4> );> > > // Print the elements of the linked list> > for> (> int> i : linkedList) {> > System.out.println(i);> > }> > }> }> |
出力
0 1 2 3 4
Java で LinkedList を使用する利点:
- 動的なサイズ: Vector と同様、LinkedList のサイズは動的に拡大または縮小できるため、初期サイズの設定について心配する必要はありません。
- 効率的な挿入と削除: LinkedList は、挿入ポイントまたは削除ポイントの後にすべての要素を移動するのではなく、要素間のリンクを変更するだけでよいため、リストの途中で要素を挿入または削除する場合に効率的なデータ構造です。
- 柔軟な反復: リンク リストを使用すると、各要素が先行要素と後続要素の両方への参照を持っているため、リストをどちらの方向にも効率的に反復できます。
Java で LinkedList を使用する場合の欠点:
- パフォーマンス: LinkedList は、個々の要素にアクセスする場合、ArrayList よりもパフォーマンスが遅くなります。これは、目的の要素に到達するにはリストをトラバースする必要があるのに対し、ArrayList ではインデックスを使用して目的の要素に簡単にアクセスできるためです。
- メモリ オーバーヘッド: 各要素がその先行要素および後続要素へのリンクに追加のメモリを必要とするため、LinkedList は ArrayList よりも多くのメモリを必要とします。
参考書：
Java Collections Framework と LinkedList について学ぶのに適した参考書は、Naftalin と Wadler による Java Collections です。この本では、LinkedList を含む Java コレクション フレームワークについて包括的に説明し、これらのクラスを効果的に使用する方法を理解するのに役立つ多くの例と演習が含まれています。
