JavaScriptで単方向リンクリストから特定の値のノードを削除する方法

単方向リンクリストとは

連結リスト(リンクリスト)は、各ノードが「値(value)」と「次のノードへの参照(next)」を持つデータ構造です。配列と異なり、要素の追加や削除を参照の付け替えだけで行えるのが特徴です。ここでは、次のような単方向リンクリストを例に考えます。

const list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: {
          value: 5,
          next: {
            value: 6,
            next: {
              value: 7,
              next: null
            }
          }
        }
      }
    }
  }
};

やりたいこと

リンクリストを第1引数、数値を第2引数として受け取る関数を作成します。この関数は、指定された値を持つノードがリスト内に存在するかどうかを先頭から探索し、存在すればそのノードをリストから取り除いてtrueを返します。最後まで見つからなければfalseを返します。

実装コード

再帰呼び出しを使って実装すると、次のようになります。

const removeNode = (list, val, prev = null) => {
  // 末尾まで到達しても該当する値が見つからなかった場合
  if (!list) {
    return false;
  }

  if (list.value === val) {
    if (prev) {
      // 前のノードのnextを、削除対象の次のノードへ付け替える
      prev.next = list.next;
    } else if (list.next) {
      // 先頭ノードが対象の場合は、次ノードの内容を先頭へコピーする
      list.value = list.next.value;
      list.next = list.next.next;
    } else {
      // 要素が1件しかないリストの場合
      list.value = undefined;
    }
    return true;
  }

  // 一致しなければ次のノードへ進む(現在のノードを前ノードとして渡す)
  return removeNode(list.next, val, list);
};

console.log(removeNode(list, 3));   // true
console.log(JSON.stringify(list, undefined, 4));
console.log(removeNode(list, 100)); // false(存在しない値)

コードのポイント

• 削除の仕組み: ノードを物理的に消すのではなく、「前のノードのnext参照を、削除対象ノードの次のノードへ向き直す」ことでリンクを切り離します。
• 先頭ノードの削除: 先頭には前のノードが存在しないため、次のノードの値と参照を先頭オブジェクトにコピーして対応します。
• 計算量: 先頭から1ノードずつ辿っていくため、時間計算量はO(n)です。

出力結果

コンソールには次のように出力されます。

true
{
    "value": 1,
    "next": {
        "value": 2,
        "next": {
            "value": 4,
            "next": {
                "value": 5,
                "next": {
                    "value": 6,
                    "next": {
                        "value": 7,
                        "next": null
                    }
                }
            }
        }
    }
}

値が3のノードが正しく取り除かれ、リストは「1 → 2 → 4 → 5 → 6 → 7」という順序になりました。存在しない値を指定した場合は、リストは変更されずにfalseが返されます。