JavaScriptでリンクリストから要素を削除する方法

リンクリストから要素を削除する基本の考え方

リンクリスト（連結リスト）から要素を削除する処理は非常にシンプルです。削除したいノードへの参照を失う（参照を切り離す）だけで実現できます。ただし、削除する位置によって処理が異なるため、次の3つのケースを考慮する必要があります。

ケース1：先頭（ヘッド）から削除する場合

先頭の要素を削除する場合は、head = head.next と代入するだけでOKです。これにより最初のノードへの参照が失われ、headは2番目のノードを指すようになります。

ケース2：末尾（テール）から削除する場合

末尾の要素を削除する場合は、最後から2番目のノードの node.next に null を代入するだけで、リストの最後の要素を取り除くことができます。

ケース3：中間の要素を削除する場合

中間の要素を削除する場合は少し複雑です。削除対象ノードの「前のノード」が、削除対象ノードの「後のノード」を直接指すようにする必要があります。具体的には、prevNode.next = node.next という1行のコードで実現できます。

それでは、この削除の仕組みを図で確認してみましょう。

removeメソッドの実装例

続いて、上記の3つのケースに対応した remove メソッドの実装を見ていきましょう。

remove(data, position = 0) {
   if (this.length === 0) {
      console.log("List is already empty");
      return;
   }
   this.length--;
   let currNode = this.head;
   // 条件1：先頭の削除
   if (position <= 0) {
      this.head = this.head.next;
   }
   // 条件2：末尾の削除
   else if (position >= this.length - 1) {
      while (currNode.next.next != null) {
         currNode = currNode.next;
      }
      currNode.next = null;
   }
   // 条件3：中間の削除
   else {
      let iter = 0;
      while (iter < position) {
         currNode = currNode.next; iter++;
      }
      currNode.next = currNode.next.next;
   }
}

このメソッドは、まずリストが空かどうかをチェックし、空であればメッセージを表示して処理を終了します。その後、position の値に応じて、先頭・末尾・中間のいずれかの削除処理を実行します。引数 position のデフォルト値は0のため、引数を省略して呼び出した場合は先頭の要素が削除される仕組みです。

動作確認用サンプルコード

実際に動作を確認してみましょう。

let list = new LinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.remove(1);
list.display();
list.insert(15, 2);
list.remove();
list.display();

出力結果

上記のコードを実行すると、次の出力が得られます。

20 ->
30 ->
30 ->
15 ->