🦁

Javaのフレームワークを使用せずに、キューを連結リストで実装

2024/09/16に公開

便利なフレームワークがたくさんありますが、今回は基礎理解のためにキューを連結リストで自前実装しました。
フレームワークの連結リストを使用してしまった方が、簡単で早いのですが内部で何が起こっているのかがわからずブラックボックス化していたので、、、

私と同じように学習目的であれば自前実装をお勧めしますが、手間がかかる上に長年をかけて最適化されているフレームワークを超えることは難しいので、学習目的以外では普通にフレームワークを使用した方がいいかなと思います。

以下の実装でスムーズにいかなかった点はまた後日記載しようと思います。

今回実装した連結リストによるキュー

// ノードクラス
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// キュークラス(連結リストで実装)
class Queue {
    Node front;  // 先頭(取り出し側)
    Node rear;   // 末尾(追加側)

    // コンストラクタでキューの初期化
    public Queue() {
        this.front = null;
        this.rear = null;
    }

    // キューに要素を追加する(enqueue操作)
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            // キューが空の場合、先頭と末尾が同じノードになる
            front = rear = newNode;
        } else {
            // 末尾に新しいノードを追加
            rear.next = newNode;
            rear = newNode;
        }
    }

    // キューから要素を取り出す(dequeue操作)
    public int dequeue() {
        if (front == null) {
            throw new RuntimeException("キューが空です。");
        }
        int data = front.data;
        front = front.next;

        // もしキューが空になったら、rearもnullにする
        if (front == null) {
            rear = null;
        }

        return data;
    }

    // キューが空かどうかをチェックする
    public boolean isEmpty() {
        return front == null;
    }

    // キューの先頭の要素を取得する(削除しない)
    public int peek() {
        if (front == null) {
            throw new RuntimeException("キューが空です。");
        }
        return front.data;
    }
}

このコードでは連結リストの基本的な処理のノードの追加、ノードの削除を実装しております。

連結リストと配列リストの長所短所

連結リストで実装した理由は、学習したかったからという理由のみで見切り発車しましたが、一応ArrayListで実装する場合とどのような違いがあるのかを調べてみました。

比較ポイント 連結リスト(LinkedList) 配列リスト(ArrayList)
要素の追加削除 先頭、末尾への追加削除が高速 (O(1)) 末尾への追加は高速(O(1))だが、先頭への削除は低速(O(n))
ランダムアクセス インデックスでのアクセスは遅い(O(n)) インデックスでのアクセスは高速(O(1))
サイズ管理 動的にサイズ調整ができ、再割り当ては不要 サイズが不足すると再割り当てが必要
メモリアクセス 要素ごとにメモリのオーバーヘッドが大きい メモリ効率がいい
メモリ使用量 各ノードに参照などを使うためメモリ使用量が大きい 連続したメモリを使用するためオーバーヘッドが少ない
適した使用用途 追加削除が発生するキューやスタックなどの実装など 要素のランダムアクセスが必要な場合など

Discussion