【ITニュース解説】JavaScript Data Structures: Linked List

ソフトウェア開発においてデータを効率的に管理することは非常に重要であり、そのためには「データ構造」と呼ばれるデータの格納方法と操作方法の知識が不可欠である。JavaScriptでデータを扱う際、通常は配列が真っ先に思い浮かぶが、配列は非常に便利である一方で、特定の場合には非効率になることがある。特に、配列の途中に新しい要素を挿入したり、既存の要素を削除したりする操作は、その後の要素をすべてずらす必要があるため、データ量が多い場合には処理に時間がかかってしまう。このような配列の弱点を補い、特定の操作に優れた性能を発揮するのが「連結リスト（Linked List）」というデータ構造である。

連結リストは、線形データ構造の一種であり、データが一直線に並んでいるように見える点で配列と似ている。しかし、その内部的なデータの格納方法は配列とは大きく異なる。配列がメモリ上の連続した場所にデータを順番に格納するのに対し、連結リストはデータがメモリ上のどこに配置されても良く、それぞれのデータが「ノード」と呼ばれる塊として独立している。そして、各ノードが次に続くノードの場所を示す「参照（ポインタ）」を持つことで、データのつながりを表現している。この「ノード」は、実際に保持する「値（データ）」と、次のノードへの「参照」という二つの情報から構成されている。リストの先頭は「ヘッド（head）」と呼ばれ、そこから順に各ノードの参照をたどっていくことで、リスト全体のデータにアクセスできる仕組みになっている。リストの末尾のノードは、次のノードが存在しないことを示すために、その参照がnullとなる。

JavaScriptで連結リストを実装する場合、まずノードを表すNodeクラスを定義することから始める。このクラスは、コンストラクタでノードが保持する「値」を受け取り、それをthis.valueに設定する。そして、次に続くノードへの参照を保持するthis.nextというプロパティも初期化時に作成する。最初はどのノードも次に何も指していないため、this.nextにはnullを設定しておく。

次に、このノードを使って連結リスト全体を管理するLinkedListクラスを定義する。このクラスのコンストラクタは、リストの先頭を表すthis.headプロパティをnullで初期化する。リストがまだ空の状態であることを意味する。

LinkedListクラスには、連結リストの操作を行うための様々なメソッドが実装される。 たとえば、append(value)メソッドはリストの末尾に新しいノードを追加する機能を持つ。まず、新しいノードを作成し、もしリストが空であれば、その新しいノードを直接headとする。リストにすでにノードが存在する場合は、現在のノードをheadから開始し、current.nextがnullになるまで、つまりリストの末尾のノードに到達するまで順にたどっていく。末尾に到達したら、そのノードのnextプロパティに新しいノードを設定することで、リストの末尾に連結する。

prepend(value)メソッドは、リストの先頭に新しいノードを追加する。これはよりシンプルな操作で、新しいノードを作成したら、そのnextプロパティを現在のheadノードに設定し、その後、リストのheadを新しいノードに更新するだけで完了する。

特定の値をリスト内で見つけるfind(value)メソッドも重要である。このメソッドは、headからリストを順にたどり、各ノードのvalueと検索対象のvalueを比較する。一致するものが見つかればそのノードを返し、リストの最後までたどっても見つからなかった場合はnullを返す。

連結リストの特長が最もよく現れる操作の一つが、delete(value)メソッドによるノードの削除である。まず、リストが空の場合や、削除対象がheadノードである場合は特別な処理を行う。headが削除対象の場合、headを次のノードに切り替えるだけで済む。それ以外の場合、削除したいノードの「前のノード」を見つける必要がある。currentノードをheadから始め、current.nextが存在し、かつcurrent.next.valueが削除対象の値と異なる限り、currentを次のノードに進める。このループが終わると、currentは削除したいノードの直前のノードを指しているか、削除対象が見つからなかったことを示す状態になっている。もし削除対象のノードが見つかった場合（current.nextが存在する場合）、current.nextをcurrent.next.nextに設定することで、間にあった削除対象ノードへの参照を飛ばし、そのノードをリストから切り離す。これにより、削除対象のノードはリストから実質的に除外される。

print()メソッドは、リストのすべての値を順番に出力する。headからノードをたどり、各ノードの値を配列に収集し、最終的にそれらを整形してコンソールに出力する。

これらのメソッドを使って、実際に連結リストを操作してみると、その動作が明確に理解できる。例えば、新しいLinkedListインスタンスを作成し、append(10)、append(20)、append(30)と続けて末尾に要素を追加し、さらにprepend(5)で先頭に要素を追加すると、print()メソッドで「5 → 10 → 20 → 30」という順序で出力されることが確認できる。その後、list.find(20)を実行すれば、値が20のノードが正常に見つかり、list.delete(10)を実行すると、値10のノードがリストから削除され、print()では「5 → 20 → 30」と出力される。

連結リストが真価を発揮するのは、頻繁な挿入や削除が求められる場面である。配列のように要素をずらす必要がないため、これらの操作は非常に効率的である。また、リストのサイズを動的に変更する必要がある場合にも適している。配列のように、事前に固定サイズでメモリを確保したり、要素数が増えた際に配列全体を新しい大きなメモリ領域にコピーしてサイズ変更するといったコストの高い操作が不要だからである。ノードが必要な時に必要なだけメモリを確保し、連結していくだけでよい。

しかし、連結リストにはトレードオフも存在する。最大の欠点は、配列のように直接インデックスを指定して要素にアクセスできないことである。例えば「リストの3番目の要素にアクセスしたい」と思っても、headから3回たどる必要があるため、要素数が多くなるとアクセス速度が遅くなる。また、各ノードが値に加えて次のノードへの参照（ポインタ）を保持するため、配列に比べて同じ数のデータを格納する際により多くのメモリを消費するという点も考慮する必要がある。

結論として、JavaScriptの配列が多くの場面で便利であることは確かだが、連結リストは、特定の状況下で非常に強力な代替手段となる基本的なデータ構造である。連結リストを理解することは、メモリの管理、アルゴリズムの効率、そしてデータ構造の選択がプログラムの性能にどう影響するかについて、より深い洞察を与えてくれる。次に、柔軟なデータの挿入や削除が頻繁に必要となる要件に直面したときは、配列だけでなく連結リストも選択肢として検討するとよいだろう。