JavaScriptで双方向リンクリスト（二重リンクリスト）を作成する方法

双方向リンクリスト（二重リンクリスト）とは、各ノードが「次のノード」と「前のノード」の両方への参照を持つデータ構造です。片方向リンクリストでは前方へしかたどれませんが、双方向リンクリストならどちらの方向にも移動できるため、挿入や削除などの操作がより柔軟に行えます。

ここでは、JavaScriptを使って双方向リンクリストを実装する基本的な手順を解説します。

LinkedListクラスとNodeクラスの定義

まず、head（先頭）とtail（末尾）をnullで初期化するコンストラクタを持つシンプルなクラスを定義することから始めましょう。あわせて、LinkedListクラスのプロトタイプ上に、リンクリスト内の各ノードを表すNodeクラスも定義します。

例

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
}
LinkedList.prototype.Node = class {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
};

このコードでは、LinkedListクラスがリスト全体を管理し、プロトタイプに登録されたNodeクラスがdata（データ本体）、next（次ノードへの参照）、prev（前ノードへの参照）という3つのプロパティを持っています。

display関数によるリストの表示

次に、作成したリストの中身を確認するためのdisplay関数を作成しましょう。この関数は以下のように動作します。

• 先頭（head）から処理を開始します。
• currNode = currNode.next を使ってリストを順にたどり、currNodeがnullになる（＝末尾に到達した）まで繰り返します。
• 各反復ごとに、そのノードが保持しているdataを出力します。

以下はその動作イメージです。

例

display() {
    let currNode = this.head;
    while (currNode != null) {
        console.log(currNode.data + " -> ");
        currNode = currNode.next;
    }
}

このように、whileループでnextポインタを順にたどるだけで、リスト内のすべての要素を先頭から末尾にかけて表示できます。双方向リンクリストの場合、prev参照を使えば、同じ要領で末尾から逆方向へ走査する処理も簡単に実装できるのが大きなメリットです。