JavaScriptでリンクリスト（LinkedList）クラスを実装する方法

リンクリスト（連結リスト）は、各要素（ノード）が「データ」と「次のノードへの参照」を持つ線形データ構造です。配列と異なり、要素の挿入や削除を参照の付け替えだけで行えるため、特定の場面では非常に効率的に動作します。

ここでは、JavaScriptで実装したLinkedListクラスの完全なコードを紹介し、その後、各メソッドの役割を解説します。

LinkedListクラスの実装例

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  insert(data, position = this.length) {
    let node = new this.Node(data);
    if (this.head === null) {
      this.head = node;
      this.length++;
      return this.head;
    }
    let iter = 1;
    let currNode = this.head;
    while (currNode.next != null && iter < position) {
      currNode = currNode.next;
      iter++;
    }
    node.next = currNode.next;
    currNode.next = node;
    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;
    }
    else if (position >= this.length - 1) {
      while (currNode.next.next != null) {
        currNode = currNode.next;
      }
      currNode.next = null;
    }
    else {
      let iter = 0; while (iter < position) {
        currNode = currNode.next; iter++;
      }
      currNode.next = currNode.next.next;
    }
    return currNode;
  }
  display() {
    let currNode = this.head;
    while (currNode != null) {
      console.log(currNode.data + " -> ");
      currNode = currNode.next;
    }
  }
}
LinkedList.prototype.Node = class {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
};

各メソッドの解説

constructor()（コンストラクタ）

リストの先頭を指す head を null で初期化し、要素数を管理する length を 0 に設定します。

insert() メソッド

指定した位置に新しいノードを挿入します。第2引数の position を省略すると、デフォルトでリストの末尾に追加されます。リストが空の場合は、新規ノードがそのまま先頭（head）になります。挿入処理では、前のノードの next 参照を付け替えることで要素を組み込んでいます。

remove() メソッド

指定した位置のノードを削除します。position が 0 以下の場合は先頭ノードを削除し、末尾付近を指定した場合は最後のノードを削除します。それ以外の場合は、目的の位置まで走査して該当ノードをスキップさせます。なお、リストが空の場合はコンソールに「List is already empty」と出力して処理を終了します。この実装では削除は位置指定で行われるため、第1引数の data は実際には使用されていない点に注意してください。

display() メソッド

リストの先頭から順に各ノードのデータをコンソールへ出力します。currNode が null になるまでループを回すことで、全要素を表示できます。

使用例

const list = new LinkedList();

// 要素の追加
list.insert(10);
list.insert(20);
list.insert(30);
list.display();
// 出力: 10 -> 20 -> 30 ->

// 要素の削除（先頭）
list.remove(0);
list.display();
// 出力: 20 -> 30 ->

まとめ

このLinkedListクラスは、挿入・削除・表示という基本的な操作をひと通り備えたシンプルな実装です。ノードクラスを LinkedList.prototype.Node として定義することで、LinkedListクラスとセットで管理できる点もポイントです。双方向リストや循環リストなど、応用的なデータ構造を学ぶ前の基礎として、ぜひ理解を深めてみてください。