れんけつりすと
各要素が、値と次の要素の位置を指すポインタを持ち、それをたどってつながるデータ構造。位置が分かっていれば挿入や削除はポインタの付け替えで O(1) だが、i 番目の要素を読むには先頭からたどる O(n) が必要。要素がメモリ上に散らばりやすく、配列よりキャッシュが効きにくい。
「連結リスト」は、5分野の10問の練習問題に出てきます(データ構造とアルゴリズム, メモリ階層と性能, プログラミングの基礎(擬似言語のトレース)など)。
この用語の分野: データ構造とアルゴリズム
正解：A. 挿入する位置の直前の要素が分かっていれば、ほかの要素を動かさずにポインタの付け替えだけで挿入できるが、i 番目の要素を読むには先頭から順にたどる必要がある
連結リストでは、挿入や削除の位置が分かっていれば、前後のポインタを書き換えるだけで O(1) で済みます。一方、i 番目の要素を読むには先頭から i 回ポインタをたどる必要があり、O(n) かかります。配列は先頭の番地と要素の大きさから i 番目の番地を計算できるので O(1) で読めますが、途中への挿入には後ろの要素をずらす O(n) の手間がかかります。また、配列は要素が連続して並ぶためキャッシュやプリフェッチが効きやすく、メモリ上に散らばりやすい連結リストは、同じ O(n) の走査でも大幅に遅くなることがあります。
正解：A. チェイン法では負荷率が1を超えても格納できるが、オープンアドレス法では表の大きさを超えて格納できず、負荷率が1に近づくと探索の回数が急に増える
チェイン法は同じ位置の要素をリストにつなぐので、要素数が表の大きさを超えても格納できますが、平均のリストの長さは負荷率に比例して伸び、探索の手間も増えます。オープンアドレス法は表の中だけに格納するので要素数は表の大きさまでで、負荷率が1に近づくと空きを探す回数が急に増えます。どちらの方法でも、負荷率が決めた値(例えば0.5〜0.75程度)を超えたら表を大きくして全要素を入れ直す(リハッシュ)のが普通です。オープンアドレス法でも衝突は起こり、空いた位置を探すことで対処しています。
連結リストでは、次の要素のアドレスがp->nextを読んで初めて分かります。
上の連結リストをたどる処理が、同じ数の要素をもつ配列を順に読むより大幅に遅くなりやすい理由はどれか。連結リストでは、挿入や削除の位置が分かっていれば、前後のポインタを書き換えるだけで O(1) で済みます。
配列と比べたときの連結リスト(各要素が次の要素の位置を指すポインタを持つリスト)の特徴として正しいものはどれか。連結リストのつなぎ替えでは、後ろの要素への道筋を失わない順に代入します。
次のプログラムは、配列 next でつないだ連結リスト A → C → E → D → B の「C」(要素番号3)の直…連結リストは次の要素のアドレスが今の要素を読むまで分からないため、規則性がなく予測できません。
ハードウェアのプリフェッチが特に効果を発揮しやすいアクセスはどれか。連結リストの先頭のポインタがAのとき、あるスレッドがAを読んでCASの準備をする間に、ほかのスレッドがAを取り除き、Bの操作をして、再び同じ番地Aのノードを入れることがあります。
CASを使ったロックフリーのデータ構造で問題になるABA問題の説明として正しいものはどれか。Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。