連結リスト(レンケツリスト)とは | 意味や読み方など丁寧でわかりやすい用語解説

連結リストとは、複数のデータ要素を格納するデータ構造の一つである。配列とは異なり、メモリ上で連続した領域を必要とせず、それぞれのデータ要素が次の要素への参照、いわゆるポインタやリンクを持つことで線形につながっている点が大きな特徴だ。この構造により、リストの途中にデータを追加したり、既存のデータを削除したりする操作が効率的に行えるメリットがある。各データ要素は「ノード」と呼ばれ、データ本体と次のノードへのポインタのセットで構成される。リストの開始地点は「ヘッド」または「先頭ノード」と呼ばれ、ここからリスト全体をたどることができる。

連結リストを構成する最小単位であるノードは、通常、格納するデータそのものと、次のノードを指し示すポインタ（メモリ上のアドレス情報）の二つの部分から成る。このポインタをたどることで、リスト内の次のデータへと順に進むことが可能になる。ノードは必要に応じて動的に生成され、メモリ上の任意の場所に配置されるため、連続した大きなメモリ領域を事前に確保する必要がない。

連結リストにはいくつかの種類が存在する。最も基本的なものは「単方向連結リスト」である。これは、各ノードが次のノードへのポインタのみを持つ構造だ。リストの先頭から順にたどることはできるが、一度次のノードへ進むと前のノードへ戻ることはできない。データの探索は、先頭ノードから始めて、目的のデータが見つかるか、リストの末尾（ポインタがNULLやNILを示すノード）に到達するまで、順次ポインタをたどっていく形となる。新しいノードを挿入する場合、挿入したい位置の手前のノードのポインタを新しいノードへ向け、新しいノードのポインタをその次に続くノードへ向けることで行われる。ノードを削除する場合は、削除したいノードの手前のノードのポインタを、削除したいノードの次のノードへ向け直すことで、削除対象のノードをリストから切り離す。

次に、「双方向連結リスト」がある。これは、各ノードが次のノードへのポインタだけでなく、前のノードへのポインタも持つ構造だ。この「前のノードへのポインタ」を持つことで、リストを先頭からだけでなく、末尾からも、あるいは任意のノードから前後どちらの方向へもたどることが可能になる。これにより、特定ノードの直前のノードを探す操作が効率化され、挿入や削除の処理が単方向連結リストよりも柔軟になる。例えば、あるノードを削除する際、そのノードへの参照さえあれば、前のノードと次のノードの両方を容易に特定し、ポインタを適切に付け替えることができるため、削除処理が簡素化される。

さらに、「循環連結リスト」も存在する。これは、リストの末尾のノードのポインタが、NULLではなくリストの先頭ノードを指し示す構造になっているものだ。これにより、リストのどのノードから始めても、リスト全体を繰り返し巡回することができる。特定の処理を繰り返したり、タスクを巡回させたりするようなシステムで利用されることがある。単方向や双方向の循環リストが存在する。

連結リストの主要な操作には、探索、挿入、削除がある。探索は、リストの先頭から順にノードをたどり、各ノードのデータが目的の値と一致するかどうかを比較する。目的のデータが見つかれば探索を終了し、見つからずにリストの末尾に到達すれば、データはリストに存在しないと判断する。この操作の効率はリストの長さに比例し、要素数が多い場合には時間がかかることがある。

挿入操作は、新しいノードをリストの特定の位置に追加することだ。例えば、あるノードAの直後に新しいノードXを挿入する場合、ノードAのポインタをノードXに向け、ノードXのポインタをノードAが元々指していたノード（例えばノードB）に向ける。この操作は、挿入位置のノード（ここではノードA）が特定されていれば、非常に高速に実行できる。配列のように、既存の要素をずらす必要がないためだ。

削除操作は、リストから特定のノードを取り除くことだ。例えば、ノードXを削除する場合、ノードXの前のノードPのポインタを、ノードXが指していた次のノードNに向ける。これにより、ノードXはリストから切り離され、実質的に削除される。この操作も、削除するノードの前後のノードが特定されていれば高速に行える。

連結リストの最大の利点は、動的なメモリ管理に適している点である。必要なときに必要なだけのメモリを確保してノードを追加でき、不要になったノードは解放できるため、プログラムの実行中にリストのサイズを柔軟に変更できる。また、リストの途中に要素を挿入したり、要素を削除したりする操作が、配列と比べて効率的である。配列の場合、挿入や削除を行うと、その位置より後ろの全要素を移動させる必要があるが、連結リストではポインタの付け替えだけで済むため、要素の移動に要する時間と手間を削減できる。これは特に、リストの要素数が多い場合や、挿入・削除が頻繁に行われる場合に顕著なメリットとなる。

一方、デメリットも存在する。最も顕著なのは、特定のインデックスを持つ要素に直接アクセスできないことだ。配列であればarray[5]のように直接アクセスできるが、連結リストでは先頭から順にポインタをたどっていくしかないため、目的の要素に到達するまでに時間がかかる。このアクセス効率は、リストの長さに比例して悪化する。また、各ノードがデータ本体に加えてポインタのための余分なメモリを必要とするため、同じデータ量であれば配列よりも多くのメモリを消費する可能性がある。さらに、メモリ上でノードが連続して配置されないことが多いため、CPUのキャッシュメモリの利用効率が低下し、アクセス速度が遅くなる場合がある。これはキャッシュミスが増加し、メインメモリへのアクセスが発生することでパフォーマンスが低下する要因となる。

連結リストは、オペレーティングシステムにおけるプロセス管理、ファイルシステムのブロック管理、Webブラウザの閲覧履歴、様々なアルゴリズムやデータ構造（スタック、キュー、ハッシュテーブルなどの基盤）の実装など、多岐にわたる場面で利用されている。これらの分野では、データの動的な追加・削除が頻繁に発生し、メモリを効率的に利用する必要があるため、連結リストがその特性を活かして活用されている。