シングルリンク (シングルリンク) とは | 意味や読み方など丁寧でわかりやすい用語解説

シングルリンク (シングルリンク) の読み方

日本語表記

シングルリンク (シングルリンク)

英語表記

single link (シングルリンク)

シングルリンク (シングルリンク) の意味や用語解説

シングルリンクとは、データ構造の一種である連結リストにおいて、各データ要素（ノードと呼ぶ）が、自身のデータと、次に連結するデータ要素への参照（ポインタ）のみを持つ構造を指す。データが直線的に一方向にのみ連結されているため、シングルリンク、あるいは単方向連結リストとも呼ばれる。 連結リストは、データをメモリ上に連続して配置する配列とは異なり、個々のデータ要素がメモリ上のどこに配置されても良いという特徴を持つ。シングルリンクはこの連結リストの最も単純な形態である。各ノードは基本的に二つの部分から構成される。一つは「データ部」で、実際に格納したい情報（例えば数値、文字列、オブジェクトなど）を保持する。もう一つは「ポインタ部」で、これは次に続くノードがメモリ上のどこにあるかを指し示す情報、つまり「次のノードへの参照」を保持する。リストの最後のノードのポインタ部は、次に続くノードがないことを示す特殊な値（一般的にはNULL）を持つ。リスト全体は、最初のノードへのポインタである「ヘッド」によって管理される。 シングルリンクでの操作は、主にこのポインタを操作することで実現される。データの探索を行う場合、ヘッドから順に各ノードのデータ部を調べ、ポインタを辿って次のノードへと移動していく。目的のデータが見つかるか、リストの末尾（NULLポインタ）に到達するまでこの作業を繰り返す。後方への移動はできないため、常に先頭から順に探索する必要がある。 データの追加は、新しいノードを作成し、既存のノードのポインタを付け替えることで行う。リストの先頭にノードを追加する場合、新しいノードのポインタ部に現在のヘッドが指すノードをセットし、その後ヘッドを新しいノードに更新する。リストの末尾に追加する場合、先頭から最後のノードまでポインタを辿り、見つかった最後のノードのポインタ部に新しいノードをセットする。リストの途中に挿入する場合、挿入したい位置の直前のノードを探し、新しいノードのポインタ部に直前のノードのポインタが指していたノードをセットした後、直前のノードのポインタ部に新しいノードをセットする。 データの削除も同様にポインタの操作で行われる。リストの先頭のノードを削除する場合、ヘッドを現在のヘッドが指すノードのポインタが指すノードに更新する。元の先頭ノードはメモリから解放される。リストの末尾のノードを削除する際は、先頭からポインタを辿り、末尾のノードとその直前のノードを探す必要がある。末尾のノードの直前のノードが見つかったら、そのノードのポインタ部をNULLに更新する。リストの途中のノードを削除する場合、削除したいノードの直前のノードを探し、その直前のノードのポインタ部に、削除したいノードのポインタが指すノードをセットする。これにより、削除したいノードはリストから切り離され、メモリから解放される。 シングルリンクの最大の特徴は、ノード間の連結が一方通行である点にある。これにより、あるノードからその前のノードへ移動することは不可能であるという制約が生じる。例えば、末尾のノードを削除する際には、その直前のノードを特定するために、リストの先頭から再度探索を行う必要があるため、非効率になることがある。 一方、シングルリンクは配列と比較して、データの挿入や削除が高速に行える場合がある。配列の場合、途中にデータを挿入したり削除したりすると、その後ろの要素を全てずらす必要があるが、シングルリンクではポインタの付け替えだけで済むため、要素数が多いほどその利点が顕著になる。また、リストのサイズを動的に変更できるため、あらかじめ最大サイズを決める必要がない。しかし、ランダムアクセスはできないという欠点がある。特定のインデックスのデータにアクセスするには、先頭から順に数えながら辿っていくしかなく、配列のように直接アドレスを計算してアクセスするような効率的な方法は存在しない。さらに、各ノードがポインタを持つため、データそのものに加えてポインタ分のメモリオーバーヘッドが発生する。 シングルリンクは、実装がシンプルであることから、比較的単純なリスト構造が必要な場面で利用される。例えば、データを追加する操作と削除する操作が主に一方向から行われる、スタック（後入れ先出し）やキュー（先入れ先出し）といったデータ構造の実装基盤として用いられることがある。また、プログラムの内部で一時的なデータの一覧を管理する際など、要素の追加や削除が頻繁に行われるが、後方への参照が不要な場合にも適している。 シングルリンクの制約、特に後方への移動ができないという点を克服するために、「ダブルリンク（双方向連結リスト）」という派生構造が存在する。ダブルリンクでは、各ノードが次に続くノードへのポインタだけでなく、前に続くノードへのポインタも持つことで、両方向への探索や操作を効率的に行えるようになる。しかし、その分ポインタ分のメモリ消費が増え、実装もわずかに複雑になる。シングルリンクは、このダブルリンクや他の複雑なリスト構造を理解する上での基本的な出発点となる重要なデータ構造である。