メニューを表示するにはスワイプしてください

オブジェクト同士がリンクされていたら？

次に進むデータ構造は、非常に興味深い LinkedList です。

LinkedList の構文と動作の仕組みを見てみましょう:

ご覧の通り、構文は ArrayList の宣言とまったく同じです。一般的に、どんなリストもこの方法で宣言できます。

しかし、LinkedList の仕組みを理解しようとすると、面白い部分が始まります。

LinkedListの構造

内部的には、LinkedListはNodesを使用して動作します。NodeはLinkedList内に格納されるオブジェクトです。LinkedList内での実装例は次の通りです:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

このクラスの構成要素について説明します。まず最初に出てくる主な疑問は、「<E>とは何か？」という点です。これはジェネリクスです。

簡単に言うと、ここでは初期化時に指定されるデータ型のプレースホルダーを用意しています。このプレースホルダーをコード内で使用し、後でユーザーが指定したデータ型に置き換えられます。

これはオーバーロードと比較できます。

実際の動作を見てみましょう:

したがって、このメソッドを各データ型ごとにオーバーロードする代わりに、ジェネリックを使用し、その中にメソッドが扱うデータ型を挿入します。文字 E は、必要なデータ型に単純に置き換えられます。今回の場合は Integer です。

次に、E item フィールドに注目します。これは、この Node に格納されるオブジェクトの値です。たとえば、{0, 1, 2, 3} のようなリストを作成すると、最初のノードには 0、2 番目のノードには 1 というように格納されます。

次に、他の Node オブジェクトへの参照、すなわち Node<E> next および Node<E> prev があることがわかります。これがリンクリストの主な特徴です。1 つの Node には次の Node と前の Node への参照が含まれています。この仕組みによりリストを順にたどることができます。LinkedList のイテレーションについて詳しく見ていきましょう。

このような構造を見ると、このリストのイテレーションは異なる仕組みで動作していることがわかります。

ArrayList<>() では、内部的にプログラムが配列を使用し、要素数が容量の 3/4 に達すると配列サイズが倍増します。

一方、LinkedList<>() には、LinkedList 内に配列が存在しないため、新しい配列を作り直す必要はありません。

代わりに、新しい要素を追加する際は、新しい Node オブジェクトが作成され、参照によって前の末尾要素とリンクされます。

少し複雑に見えるかもしれませんが、プログラマーとしてこれらすべてを自分で設定する必要はありません。

LinkedListのメソッドはArrayListのものと同じです。これは、両方ともListインターフェースから継承されており、すべての子孫が実装しなければならないメソッドを定義しているためです。

アルゴリズムの計算量

コレクションフレームワークにはさまざまなデータ構造があり、それぞれにアルゴリズムの計算量があります。

アルゴリズムの計算量はビッグO記法（例：O(n)、O(n^2)）で表されます。ここで**「O」は「ビッグO」**を意味し、入力サイズに対する実行時間の増加の上限を示します。

主なアルゴリズムの計算量の種類は次のとおりです:

O(1) （定数時間）: 計算量が入力データのサイズに依存しない場合。例：配列のインデックスによる要素アクセス；
O(log n) （対数時間）: 計算量が入力データのサイズに対して対数的に増加する場合。例：ソート済み配列での二分探索；
O(n) （線形時間）: 計算量が入力データのサイズに比例して増加する場合。例：ArrayList内の全要素の走査；
O(n^2) （二乗時間）: 計算量が入力データのサイズの二乗に比例する場合。例：バブルソート。

これらは基本的なカテゴリであり、他にも O(n log n)、O(2^n)、O(n!) など、より複雑なアルゴリズムを特徴付ける多くのアルゴリズムの計算量があります。効率的なアルゴリズムの選択とその計算量の考慮は、ソフトウェア開発における重要な要素です。

それでは、Javaのデータ構造に戻りましょう。各データ構造は、実行する操作によってアルゴリズムの計算量が異なります。表を見てみましょう:

ArrayListでのインデックスによる要素検索は、単純に配列のインデックスにアクセスするだけなので、定数時間となります。

一方、LinkedListでのインデックス検索は、すべてのノードを順にたどって目的のオブジェクトを見つける必要があるため、はるかに時間がかかります。

逆に、要素の挿入を見ると、LinkedListは定数時間ですが、ArrayListは線形時間です。これは、LinkedListではノード間のリンクを新しいものに変更して要素を挿入するだけで済むのに対し、ArrayListでは新しい要素を含む配列を再作成し、元の配列をコピーして要素を挿入する必要があり、より多くの時間がかかるためです。

例を見てみましょう:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

2つのリストを作成しました。1つはArrayList、もう1つはLinkedListです。そして、それぞれに1,000,000個のランダムな整数を格納しました。両方のリストには同じ内容が含まれており、1から100までの数値が100万個入っています。

次に、値50を持つ要素を1000番目のインデックスに追加するのにかかる時間を計測しました。時間の計測にはSystem.nanoTime()メソッドを使用し、現在の時刻をナノ秒単位で取得します。その後、各リストについて開始時刻から終了時刻を引くことで、リストの中央に要素を追加するのにかかった時間を算出しました。

表から分かるように、LinkedListの方がはるかに高速です。LinkedListは定数時間のアルゴリズム的複雑度を持ち、ArrayListは線形の複雑度となります。

このように、異なる種類のリストが必要となる理由があります。プロジェクトで大量のデータを扱い、最適化が重要な場合は、どのリスト型が特定のケースでより高速に動作するかを再検討する価値があります。しかし、秘密を教えますが、私はほとんどの場合ArrayListを使っています。

SinglyLinkedList

SinglyLinkedListという未公開のデータ構造があります。名前が示す通り、このデータ構造は一方向のみでイテレーションを行います。LinkedListクラスのNodeにはitem、next、prevのフィールドがありますが、SinglyLinkedListクラスのNodeにはitemとnextの2つのフィールドしかありません。

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}