JavaScriptでリンクリストに要素を挿入する方法をわかりやすく解説

はじめに

リンクリスト（連結リスト）では、指定した位置にデータを挿入するための関数 insert(data, position) を用意する必要があります。本記事では、その実装手順とサンプルコードを初心者にもわかるように解説します。

挿入処理の基本手順

insert(data, position) の内部では、以下のステップを実行します。

• 新しいノード（Node）を作成します。
• リストが空かどうかを確認します。空の場合は、作成したノードをheadに設定して処理を終了します。
• 空でない場合は、currNode を使って挿入したい位置までリストをたどります。リンクリストの走査は「currNode = currNode.next」を繰り返すことで実現できます。
• 新しく作成したノードの next に、現在のノードの次のノードを代入します。これにより、挿入位置より後ろにある残りのリスト構造が失われずに保持されます。
• 最後に、現在のノードから後続ノードへの参照を切り替え、新しく作成したノードを指すようにします。これで、ノードが指定した位置に正しく挿入されます。

以下は、この一連の流れを表したイメージ図です。

実装例

それでは、実際のコードを見ていきましょう。

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;
}

ここで注目すべき点は、引数 position のデフォルト値としてリストの長さ（＝末尾の位置）が設定されていることです。これにより、位置を指定せずに呼び出した場合でも、要素が自動的にリストの末尾へ追加されるようになっています。

動作確認

実際にコードを実行して、動作を確認してみましょう。

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

実行結果

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

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

このように、すべての要素が意図した通りの順序で並んでいます。位置として「2」を指定することで、値 15 が2番目の要素（20）の後に正しく挿入されていることが確認できます。