内部収納と外部収納
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)
連結リストを構築する際、データをノードそのものに格納するか、別のデータ構造への参照のみを格納するかという選択を迫られる。前者を「内部収納; internal storage[要出典]」、後者を「外部収納; external storage[要出典]」と呼ぶ。内部収納の方がデータアクセスが効率化され、全体としてメモリ使用量が低減され、参照の局所性が向上し、リストに関するメモリ管理も簡素化される（データはノードと共に確保・解放される）。 一方、外部収納はより汎用的だという利点がある。データの内容に依存しないデータ構造とリスト操作コードを形成可能である。また、複数のノードで同じデータを共有することも容易に実現できる。内部収納の場合も、通常のリンクとは別に、同じ内容のデータを保持するノードを連結するフィールドを持てば、同様のことが可能になるが、リスト操作にあたってそれも考慮する必要が出てくる。 一般に、データ構造を複数の連結リストに属させる必要がある場合、外部収納が最善の手法である。データ構造が1つの連結リストにしか属さない場合、内部収納の方が若干良いが、外部収納の汎用リスト操作パッケージが利用可能なら、それを利用するほうがよい場合もある。 いくつかの言語で採用されている別の手法として、いくつかの種類のデータ構造があって、それらの先頭部分の同じ位置にリストのための "next" および "prev" のフィールドが存在する場合がある。この場合、リスト操作は汎用的なルーチンを使い、個々のノード内のデータは個別のルーチンで処理する。様々な種類のメッセージを受信する際の構文解析などでよく使われる。メッセージのキューへの追加と削除は汎用的なルーチンで行われる。メッセージの種類がメッセージの先頭にあり、それを見て適切なメッセージ処理ルーチンを呼び出す。
※この「内部収納と外部収納」の解説は、「連結リスト」の解説の一部です。
「内部収納と外部収納」を含む「連結リスト」の記事については、「連結リスト」の概要を参照ください。
- 内部収納と外部収納のページへのリンク
