連結リストと配列の比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/01 16:16 UTC 版)
「ルックアップテーブル」の記事における「連結リストと配列の比較」の解説
詳細は「連結リスト」を参照 連結リストには配列と比較して以下のような利点がある。 連結リストに特有の性質として、要素の挿入と削除を定数時間で行える（なお、削除された要素を「この要素は空である」とマーキングする方式であれば配列でも削除は定数時間で行える。ただし、配列を走査する際に空の要素をスキップする必要がある）。 要素の挿入を、メモリ容量の許す限り連続して行える。配列の場合は、内容がいっぱいになったらリサイズする必要があるが、これは高価な処理である上に、メモリが断片化していた場合はリサイズ自体が行えないこともある。同様に、配列から要素を大量に削除した場合、使用メモリの無駄をなくすには配列のリサイズを行う必要がある。 一方、配列には以下のような利点がある。 連結リストはシーケンシャルアクセスしか行えないが、配列はランダムアクセスが行える。また、単方向の連結リストの場合、一方向にしか走査が行えない。このため、ヒープソートのようにインデックスを使って要素を高速に参照する必要がある処理には連結リストは向いていない。 多くのマシンでは、連結リストよりも配列のほうが順次アクセスが高速に行える。これは、配列の方が参照の局所性が高くプロセッサのキャッシュの恩恵を受けやすいためである。 連結リストは配列と比較してメモリを多く消費する。これは、次の要素への参照を保持しているためであるが、格納するデータ自体が小さい場合（キャラクタやブール値などの場合）はこのオーバーヘッドが原因で実用性がなくなってしまうこともある。また、新しい要素を格納する際の動的メモリ確保にネイティブアロケータを使用する場合、メモリ確保による速度の低下や使用メモリ量の無駄が発生する場合もあるが、これはメモリプールを使用すれば概ね解決できる。 2つの手法を組み合わせて両方の利点を得ようとする手法もある。Unrolled linked listでは一つの連結リストのノード中に複数の要素を格納することでキャッシュパフォーマンスを向上させるとともに、参照を保持するためのメモリのオーバーヘッドを削減している。同様の目的で使用されるCDRコーディングでは、参照元レコードの終端を伸ばし、参照を実際に参照されるデータで置き換えている。
※この「連結リストと配列の比較」の解説は、「ルックアップテーブル」の解説の一部です。
「連結リストと配列の比較」を含む「ルックアップテーブル」の記事については、「ルックアップテーブル」の概要を参照ください。
- 連結リストと配列の比較のページへのリンク
