Javaのリンクリストデータ構造

さまざまな目的のためにさまざまなデータ構造が作成されます。ArrayListについてご存知かもしれません(まだご存じでない場合は、まず読んでおくことをお勧めします)。この記事では、 LinkedListについて学び、このコレクションが何に役立つのかを理解します。LinkedList Java 8 (またはそれ以降のバージョンの言語) クラスコードソース (Oracle Web サイトまたは IDE、IDEA の場合: クラス名に crtl+B) を調べると、次の宣言が表示されます。


public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

現時点で、コードから得られる最も重要な情報は、LinkedList がListインターフェイスとDequeインターフェイスを実装しているという事実です。List インターフェイスは項目の追加順序を保持し、インデックスによる項目へのアクセスを許可します。「通常の」キューは、要素の末尾への追加と先頭からの抽出をサポートします。Deque は双方向のキューであり、両側からの要素の追加と削除をサポートします。スタックとキューを組み合わせたものと考えることができます。 LinkedList Java データ構造 - 2

したがって、LinkedList はこれら 2 つの実装であり、null を含む任意のオブジェクトで構成される双方向キューを作成できます。リンクリスト要素のコレクションです。これはクラスのコードソースで確認できます。今回はフィールドに注目してください。


transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

通常はNode と呼ばれるすべての要素には、オブジェクトと 2 つの隣接するオブジェクト (前と次) への参照が含まれます。したがって、メモリの使用という点ではあまり効率的ではありません。 LinkedList は LinkedList Java データ構造 - 3

実際には双方向構造であるため、両側から要素を簡単に追加または削除できます。

LinkedList コンストラクター

コードソースに戻ると、 LinkedListに 2 つのコンストラクターがあることがわかります。

パラメータなしのLinkedList() は、空のリストを構築するために使用されます。
>LinkedList(Collection<? extends E> c) は、指定されたコレクションの要素を、コレクションのイテレータによって返される順序で含むリストを作成するためのものです。

リンクリスト宣言

実際、リンクリスト (Java またはその他の言語) は一連のノードで構成されます。すべてのノードは、作成時に定義されたタイプのオブジェクトを格納するように設計されています。LinkedListを作成するには、次の Java コードを実行します。


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

一連の整数と隣接するものへのリンクを保持するオブジェクトがあります。ただし、現時点では空いています。

LinkedList の主な操作

通常どおり、コレクションの場合は、要素をLinkedListに(末尾または途中に)追加し、そこから削除して、インデックスによって要素を取得できます。では、次のとおりです。

add(E element)指定された要素をこのリストの末尾に追加します。
add(int index, E element)指定された位置に要素を挿入します。
get(int index)このリスト内の指定された位置にある要素を返します。
Remove(int Index)位置 Index にある要素を削除します。
Remove(Object o)最初に出現した ? を削除します。o存在する場合、このリストの要素。
Remove()リストの最初の要素を取得して削除します。

Java でのリンクリストの実装、要素の追加と削除。例

これらの操作を実際に試してみましょう。まず、Java LinkedList の実装です。文字列の LinkedList を作成し、そこに 3 つの要素を追加します。次に、1 つを削除し、真ん中に 1 つ追加します。


public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

このプログラムを実行した結果:


my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedListはCollectionフレームワークの一部であり、要素を削除するために Iterator を使用することも、リスト用の特別な反復子であるListIteratorを使用することもできます。さらに、イテレータを使用した操作には、挿入/削除操作の優れたパフォーマンスというLinkedListクラスの主な利点があります。Iterator を使用すると、一定の時間を得ることができます。この記事の後半で、 ArrayListとLinkedList+Iteratorを比較するコード例を書きます。

Iterator.remove() は、このイテレータによって返された最後の要素を削除します。
ListIterator.add(E element) はリストに要素を挿入します

Java LinkedList の例: イテレーターの仕組み

ここに小さな Java LinkedListサンプルコードがあり、イテレータを介して追加と削除を試します。


public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

このプログラムを実行した結果:


linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

その他の Java LinkedList操作:

addFirst()、 addLast() リストの先頭/末尾に要素を追加します。
clear() はリストからすべての要素を削除します
contains(Object o) は、リストに o 要素が含まれる場合に true を返します。
IndexOf(Object o) は、最初に出現した o 要素のインデックスを返します。それがリストにない場合は -1 を返します。
set(int index, E element) は、インデックス位置の要素を要素に置き換えます。
size()リスト内の要素の数を返します。
toArray() は、リストの最初の要素から最後の要素までのすべての要素を含む配列を返します。

ところで、 Java の LinkedList は2 サイズのキューなので、スタック固有の操作があります。

Pop()はスタック (リストで表される) から要素をポップします。
Push(E e)要素をスタックにプッシュします (このリストで表されます)。

LinkedList を逆にする方法: 例

ここでは、人気がありながらも初心者にとって簡単なタスクの小さな例を示します。LinkedListがあるので、それを逆にする必要があります。最も簡単なアルゴリズムは、 LinkedList を逆の順序で調べて、すべての要素を新しいリストに入れることです。ただし、もっと良い方法が見つかるかもしれません? 逆リンクリスト Java プログラムのコードは次のとおりです。


public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

結果：


[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList と ArrayList: 最初のものをいつ使用するか

LinkedListとArrayList はどちらもListインターフェイスの実装です。LinkedList は二重リンクリストを使用してこれを実装します。ArrayList は、動的にサイズ変更される配列を使用してこれを実装します。すでにご存知のとおり、LinkedListのすべてのノードにはオブジェクトと隣接ノードへの 2 つの参照が含まれています。これは、Java LinkedListの場合、要素間の参照を保存するために追加のメモリコストがかかることを意味します。ArrayList は、動的にサイズ変更される配列を使用してこれを実装します。LinkedList 操作とArrayList操作の一部は同じように見えますが、動作方法が異なります。ArrayList内この場合、 LinkedList内の内部配列、つまり参照を使用して操作します。 ArrayList は最も人気のあるList実装です。これらの操作は一定時間で実行されるため、インデックスアクセスが優先される場合は、必ずArrayList を使用する必要があります。リストの末尾への追加も平均して一定時間内に行われます。さらに、ArrayList には、多数の要素を格納するための追加コストがかかりません。挿入および削除操作がリストの最後以外で行われる場合、その操作の速度を短所としてカウントすることができます。リンクリストこれは、いくつかの点で挿入および削除操作のパフォーマンスの場合により便利です。イテレータを使用すると、一定時間で実行されます。インデックスによるアクセス操作は、先頭から末尾（どちらか近い方）に向かって目的の要素を検索して実行されます。ただし、要素間の参照を保存するための追加コストを忘れないでください。ここでは、アルゴリズムランタイムを使用した標準的なLinkedListおよびArrayList操作を示します。N は、リストにすでに存在する項目の数を指します。O(N) は、最悪の場合、たとえばリストに新しい要素を挿入する場合など、必要な位置が見つかるまでリスト全体を「ウォークスルー」する必要があることを意味します。○(1)項目の数に関係なく、操作が一定時間で実行されることを意味します。

LinkedList の時間計算量

LinkedList Java 操作	アルゴリズムの有効性
get(int インデックス)	O(n)、平均— n/4ステップ、n はLinkedListのサイズ
add(E要素)	○(1)
add(int インデックス, E 要素)	O(n)、平均 - n/4ステップ。if index = 0 then O(1)なので、リストの先頭に何かを追加する必要がある場合は、 LinkedList<E> が良い選択になる可能性があります。
削除(int インデックス)	O(n)、平均 — n/4ステップ
Iterator.remove()	O(1)これがLinkedList<E>を使用する主な理由です

ArrayList の時間計算量

リンクリストの操作	アルゴリズムの有効性
get(int インデックス)	O(1) 、 ArrayList<E>を使用する主な理由の 1 つ
add(E要素)	配列のサイズを変更してコピーする必要があるため、 O(n)は最悪のケースですが、実際にはそれほど悪くありません。
add(int インデックス, E 要素)	O(n)、平均n/2ステップ
削除(int インデックス)	O(n)、平均n/2ステップ
Iterator.remove()	O(n)、平均n/2ステップ
ListIterator.add(E要素)	O(n)、平均n/2ステップ

LinkedList を使用する場合: 例

間違いなく、ArrayList が最も人気のあるList実装です。ただし、追加/削除操作が頻繁に必要になる場合があります。その場合、LinkedList とIterator を併用すると有益になる可能性があります。ここに一例を示します。長いリストがあるので、このリストからすべての要素を削除する必要があります。このタスクをArrayListとLinkedList + Iteratorで実行してみましょう。すべての操作の時間を比較し、コンソールに出力します。コードは次のとおりです。


import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList の結果:


start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

LinkedList の結果:


start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

この例からわかるように、LinkedList の方がはるかに効果的です。正直に言いましょう。実際のソフトウェア開発では、LinkedList が使用されることは一種のまれな出来事です。それにもかかわらず、専門家はこのデータ構造の存在とその利点について知っておく必要があります。実際のコードではLinkedList は珍しいゲストですが、Java Junior のインタビューでは非常に人気があります。それでも、Joshua Bloch がLinkedListについて書いたことは次のとおりです。 LinkedList Java データ構造 - 4

アドオン: 単一リンクリスト Java

Java の古典的なコレクションには単一リンクリストはありません。単一リンクリストは、すべてのノードにオブジェクトと次のノードへの参照が含まれる構造ですが、前のノードへの参照は含まれません。Java LinkedListは 2 つのリンクがありますが、Singly ,code>Linked List などの独自のデータ構造を作成することを誰も邪魔しません。これらのタスクを解決するためのいくつかの手順を次に示します。

data と next という 2 つの属性を持つNodeクラスを作成します。Next は次のノードへの参照です。
head と tail の 2 つの属性を持つFirstLastクラスを作成します。
add()メソッドを作成して、新しいノードをリストに追加します。まずリストが空かどうかを確認します ( head == null )。その場合、先頭と末尾は新しいノードを参照します。リストが空でない場合、新しいノードは最後に追加されるため、末尾の次の属性は追加されたノードを参照し、新しいノードがリストの末尾になります。

ちなみに、練習として独自のLinkedListを作成してみることもできます。学習頑張ってください。