連結リストと配列

ウィキペディア小見出し辞書

連結リストと配列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)

「連結リスト」の記事における「連結リストと配列」の解説

配列連結リスト検索 O(1) O(n) 最後尾での挿入/削除 O(1) O(1) or O(n) 途中での挿入/削除（位置指定あり） O(n) O(1) 永続性 なし 片方向で有り 局所性 大 小 連結リストは配列と比較したとき、いくつかの利点を持つ。リストでは要素の挿入は無制限に可能であるが、配列はサイズが決まっているために限界があり、配列を大きくしようとしても、メモリのフラグメンテーションによって不可能なこともある。同様に、配列から要素の多くを削除すると領域の無駄となったり、サイズを小さくする必要が生じる。 複数のリストが尾部を共有することで、さらにメモリを節約できる場合もある。つまり、先頭が複数あって、末尾が1つになっている構造が可能である。これを使って、何らかのデータの古いバージョンと新しいバージョンを同時に保持することが可能であり、簡単な永続データ構造の例となっている。 一方、配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。 連結リストの別の欠点は、参照のための余分な領域を必要とする点である。このため、キャラクタやブーリアン型のような小さなデータ要素を連結リストで操作するのは（1文字ごとにノードを割り当てて文字列操作を実現するなど）、速度の面でもメモリ消費の面でも無駄が多く、現実的でない。 これらの問題の一部を改善する連結リストの派生データ構造がいくつか存在する。Unrolled linked list は各ノードに複数の要素を格納するもので、キャッシュ性能を向上させ、参照時のメモリのオーバヘッドを低減させる。CDRコーディングも参照を参照すべき実データと置換することで同様の効果が得られる。 配列との比較で利点と欠点を明確にする好例として、ジョセファスの問題を解くプログラムの実装がある。ジョセファスの問題とは、人間が輪になって並んでいる状況で、そこから1人を選ぶというものである。ある人を開始点として、特定の方向に n 人を数えていく。n 番目の人に到達したら、その人を輪から外して、残りの人間で一回り小さい輪を作る。そして再び n 番目まで数えていく。これを1人だけが残るまで繰り返し、最後に残った人が選ばれた人ということになる。これを循環リストを使って表すのは直接的で分かり易いし、ノードの削除も簡単である。しかし、循環リストでは、現在のノードから n 番目のノードを見つけるには、リストを順に辿っていくしかない。配列であればインデックスの計算で即座に見つけられる。一方、配列では要素（ノード）の削除は容易ではなく、n 番目のノードを即座に見つけるという利点を生かすには、ノードを削除したときに残った要素を詰めてやる必要がある。