Loading article…
コンピュータプログラミング、特にLispでは、連想リスト（ alistとも呼ばれる）は、各リスト要素（またはノード）がキーと値で構成される連結リストです。連想リストは、値をキーに関連付けると言われています。特定のキーに関連付けられた値を見つけるには、逐次検索が使用されます。つまり、キーが見つかるまで、リストの各要素を先頭から順番に検索します。連想リストは連想配列を簡単に実装する方法を提供しますが、キーの数が非常に少ない場合にのみ効率的です。
連想配列は、キーと値のペアのコレクションを保持し、特定のキーに関連付けられた値を検索するために使用できる抽象データ型です。連想リストは、このデータ型を簡単に実装する方法を提供します。
特定の関連付けリストでキーが値に関連付けられているかどうかをテストするには、リストの最初のノードから検索を開始し、キーを含むノードが見つかるか、検索がリストの末尾に達するまで（この場合、キーは存在しません）検索を続けます。関連付けリストに新しいキーと値のペアを追加するには、そのキーと値のペアの新しいノードを作成し、ノードのリンクを関連付けリストの前の先頭要素に設定し、関連付けリストの先頭要素を新しいノードに置き換えます。[ 1 ]関連付けリストの実装によっては、同じキーを持つ複数のノードを持つことを許可しないものもありますが、このような重複はこの検索アルゴリズムでは問題になりません。リストの後半に現れる重複キーは無視されます。[ 2 ]
また、関連付けリストからキーを削除することも可能です。リストをスキャンしてキーの各出現箇所を見つけ、キーを含むノードをリストから切り離します。[ 1 ]同じキーが複数回挿入されている可能性があるため、キーが見つかった場合でも、スキャンはリストの最後まで続ける必要があります。
連想リストの欠点は、検索時間がO ( n )であることです。ここでnはリストの長さです。[ 3 ]大きなリストの場合、これは連想配列を二分探索木またはハッシュテーブルとして表現した場合に得られる時間よりもはるかに遅くなる可能性があります。さらに、重複するキーを持つ要素を削除するためにリストを定期的に剪定しない限り、同じキーに関連付けられた複数の値はリストのサイズ、ひいては検索時間を増加させますが、補償的な利点はありません。
連想リストの利点の1つは、新しい要素を定数時間で追加できることです。さらに、キーの数が非常に少ない場合、連想リストの検索は、実装がより単純なため、二分探索木やハッシュテーブルの検索よりも効率的になる可能性があります。[ 4 ]
Lisp の初期開発では、プロシージャ内の自由変数への参照を解決するために連想リストが使用されていました。 [ 5 ] [ 6 ]このアプリケーションでは、同じキーの他のコピーをリスト内でスキャンすることなく、キーと値のペアの追加を反転する追加の操作を連想リストに追加することが便利です。このようにして、連想リストはスタックとして機能し、ローカル変数が同じ名前の他の変数の値を破壊することなく、一時的にそれらの変数をシャドウすることができます。[ 7 ]
Lisp [ 5 ] Scheme [ 8 ] OCaml [ 9 ]や Haskell [ 10 ]など、多くのプログラミング言語には、標準ライブラリに連想リストを扱うための関数があります。