リストとは？

リストの意味

各要素が次の要素へのポインタを持つデータ構造。要素の挿入・削除がポインタの付け替えだけで済む一方、n番目の要素へアクセスするには先頭からたどる必要がある。

リストの具体例

単方向リストで末尾の要素を削除するには、直前の要素のポインタを書き換える必要があるが、単方向では手前に戻れないため先頭から全体をたどることになる。双方向リストならこれを避けられる。

リストは試験でどう引っ掛けられる？

配列は「アクセスが速く挿入削除が遅い」、リストは「挿入削除が速くアクセスが遅い」。用途に応じた選択理由が問われる。

リストと関連する用語

• 配列
• 2分探索木

リストが出た過去問

• 媒体障害の回復において，最新のデータベースのバックアップをリストアした後に，トランザクションログを用いて行う操作はどれか。

  正解：バックアップ取得後にコミットした全てのトランザクションをロールフォワードする。

  要点：媒体障害はリストア＋ロールフォワードで復旧する

  媒体障害ではディスク上のデータが失われるため、まずバックアップをリストアして過去の状態に戻す。その時点以降にコミット済みのトランザクションの更新は失われているので、ログの更新後情報を使って再適用（ロールフォワード）して最新状態まで進める。未コミットのものは再現する必要がないので対象外である。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問10（IPA）

• 先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタ又は各データのポインタをたどる回数…

  正解：末尾のデータを削除する処理

  要点：単方向リストの末尾削除は手前に戻れず全体をたどる

  単方向リストでは各ノードが次のノードだけを指す。末尾のデータを削除するには、新しい末尾となる「最後から2番目」のノードのポインタを書き換える必要があり、そのノードへは先頭からたどるしかない。末尾ポインタがあっても手前には戻れないため、リスト全体をほぼ一巡することになり、たどる回数が最も多くなる。

  出典：令和1年度 秋期 高度共通_午前I試験 am1 問4（IPA）

• デジタル証明書が失効しているかどうかをオンラインで確認するためのプロトコルはどれか。

  正解：OCSP

  要点：証明書の失効確認をオンラインで行うのはOCSP

  OCSP（Online Certificate Status Protocol）は、デジタル証明書が失効していないかを検証者がレスポンダへ問い合わせ、オンラインでリアルタイムに確認するためのプロトコルである。CRL（証明書失効リスト）を丸ごと取得する方式に比べ、通信量が小さく最新の状態を確認しやすい。

  出典：令和4年度 秋期 高度共通_午前I試験 am1 問12（IPA）

• 販売管理システムにおいて、起票された受注伝票の入力が、漏れなく、かつ、重複することなく実施されていることを確かめる監査手続として、適切なものはどれか。

  正解：販売管理システムから出力したプルーフリストと受注伝票との照合が行われているか、プルーフリストと受注伝票上の照合印を確かめる。

  要点：入力の網羅性はプルーフリストとの照合記録で検証する

  入力の網羅性（漏れがないこと）と一意性（重複がないこと）を確かめるには、システムが出力した入力内容の一覧であるプルーフリストと、元の受注伝票とを突き合わせる統制が機能しているかを確認する。照合印の有無を確かめることで、その照合が実際に行われた証跡を検証できる。

  出典：令和5年度 秋期 高度共通_午前I試験 am1 問22（IPA）

• 関係データベースのビューに関する記述のうち、適切なものはどれか。

  正解：ビューの列名は、基の表の列名と異なる名称で定義することができる。

  要点：ビューは仮想表。列名を基の表と変えて定義できる

  ビューを定義するSELECT文では列に別名を付けたり、CREATE VIEWで列名リストを指定したりできるため、基の表と異なる列名にできる。ビューは仮想表であり、射影・選択・結合・和集合など問合せで表現できる操作を自由に定義できる。

  出典：令和7年度 秋期 高度共通_午前I試験 am1 問9（IPA）