JavaScriptで双方向リンクリスト（DoublyLinkedList）クラスを実装する完全ガイド

双方向リンクリスト（Doubly Linked List）は、各ノードが「次のノード（next）」と「前のノード（prev）」の両方への参照を持つデータ構造です。片方向リンクリストと異なり、リストを前後どちらの方向にもたどれるため、挿入や削除の処理が柔軟に行えます。

この記事では、JavaScriptで双方向リンクリストを扱う DoublyLinkedList クラスの完全な実装例を紹介します。このクラスには、ノードの挿入（insert）、削除（remove）、表示（display）の3つの主要メソッドが含まれています。

DoublyLinkedList クラスの完全な実装

以下が DoublyLinkedList クラスの完全なコードです。

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    insert(data, position = this.length) {
        let node = new this.Node(data);
        // リストが空の場合
        if (this.head === null) {
            this.head = node;
            this.tail = node;
            this.length++;
            return this.head;
        }
        // 先頭への挿入
        if (position == 0) {
            node.prev = null;
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
            return this.head;
        }
        let iter = 1;
        let currNode = this.head;
        while (currNode.next != null && iter < position) {
            currNode = currNode.next; iter++;
        }
        // 新しいノードのnextを、リスト内の次のノードに向ける
        node.next = currNode.next;
        // 次のノードのprevを新しいノードに向ける
        if (currNode.next != null) {
            currNode.next.prev = node;
        }
        // 新しいノードのprevを前のノードに向ける
        node.prev = currNode;

        // 前のノードのnextを新しいノードに向ける
        currNode.next = node;

        // 挿入した要素が末尾だった場合は、tailを更新する
        if (this.tail.next != null) {
            this.tail = this.tail.next;
        }
        this.length++;
        return node;
    }
    remove(data, position = 0) {
        if (this.length === 0) {
            console.log("List is already empty");
            return;
        }
        this.length--;
        let currNode = this.head;
        if (position <= 0) {
            this.head = this.head.next;
            this.head.prev = null;
        } else if (position >= this.length - 1) {
            this.tail = this.tail.prev;
            this.tail.next = null;
        } else {
            let iter = 0;
            while (iter < position) {
                currNode = currNode.next;
                iter++;
            }
            currNode.next = currNode.next.next;
            currNode.next.prev = currNode;
        }
        return currNode;
    }
    display() {
        let currNode = this.head;
        while (currNode != null) {
            console.log(currNode.data + " <-> ");
            currNode = currNode.next;
        }
    }
}

DoublyLinkedList.prototype.Node = class {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
};

コードの解説

1. コンストラクタ（constructor）

コンストラクタでは、リストの先頭を指す head、末尾を指す tail、そして要素数を管理する length の3つのプロパティを初期化します。初期状態ではすべて空（null / 0）です。

2. ノードの挿入（insertメソッド）

insert メソッドは、指定した位置に新しいノードを挿入します。位置を省略した場合はリストの末尾に追加されます。主な処理の流れは以下の通りです。

• リストが空の場合： 新しいノードを head と tail の両方に設定します。
• 先頭への挿入（position = 0）： 新しいノードの next を現在の head に向け、head を更新します。
• 中間・末尾への挿入： 指定位置までノードをたどり、前後のノードの参照（next / prev）を適切につなぎ替えます。末尾への挿入時は tail も更新されます。

3. ノードの削除（removeメソッド）

remove メソッドは、指定した位置のノードを削除します。

• リストが空の場合はコンソールにメッセージを出力して終了します。
• 先頭の削除： head を次のノードに移し、その prev を null にします。
• 末尾の削除： tail を前のノードに移し、その next を null にします。
• 中間の削除： 指定位置までたどり、削除対象ノードを参照チェーンから外します。

4. リストの表示（displayメソッド）

display メソッドは、head から tail まで順にノードをたどり、各ノードのデータをコンソールに出力します。

5. Nodeクラス

各ノードは data（格納する値）、next（次のノードへの参照）、prev（前のノードへの参照）の3つのプロパティを持ちます。DoublyLinkedList.prototype.Node として定義することで、リストクラスと密接に結び付けられた内部クラスとして扱えます。

まとめ

双方向リンクリストは、先頭・末尾の両方からアクセスできるため、キュー（Queue）やデック（Deque）などのデータ構造の実装基盤として非常に有用です。この実装をベースに、検索メソッドや逆順表示などの機能を追加してみると、理解がさらに深まるでしょう。