ポインタとは？

ポインタの意味

データそのものではなく、データが格納されている場所（アドレス）を保持する値。連結リストや木構造では、要素どうしのつながりをポインタで表現する。つなぎ替えだけで構造を変えられるため、挿入・削除がデータ移動なしで行える。

ポインタの具体例

連結リストの各要素は「データ」と「次の要素のアドレス」を持つ。末尾の要素の次にはナル（空を表す値）を入れて終端を示す。要素Xを削除するには、Xを指していた要素のポインタをXの次の要素へ向け直せばよい。

ポインタは試験でどう引っ掛けられる？

ポインタが指す先を書き換える順序を誤ると、後続の要素へ到達できなくなり領域が迷子になる。またポインタのぶん記憶領域を余分に使う点、参照が間接的になるためアクセスが配列より遅くなる点も問われる。

ポインタと関連する用語

• 連結リスト
• 双方向リスト
• 配列

ポインタが出た過去問

• CPUのスタックポインタが示すものはどれか。

  正解：サブルーチン呼出し時に，戻り先アドレス及びレジスタの内容を格納するメモリのアドレス

  要点：スタックポインタは退避データを積む位置を指す

  スタックポインタは、スタック領域の先頭位置を保持するレジスタである。サブルーチン呼出しや割込みの際に戻り先アドレスやレジスタ内容を退避する場所を示す。

  出典：平成28年度 春期 応用情報技術者試験 午前 問8（IPA）

• 関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木…

  正解：イ：中間ノードAからB、C1、C2、Dの4つ全てに矢印。リーフノードは B⇔C1⇔C2⇔D の順で相互連結。

  要点：B+木は全リーフを親が参照し順序どおり連結する

  B+木ではすべてのキーがリーフノードに置かれ、リーフ同士が順次アクセス用のポインタで連結される。リーフが分割されたときは、新しいリーフも親ノードから参照されるようポインタを追加し、リーフ間の連結もキー順を保つよう張り替える必要がある。したがって親AからB・C1・C2・Dの4つすべてへポインタがあり、リーフがB⇔C1⇔C2⇔Dの順で連結された構造が正しい。

  出典：平成30年度 春期 応用情報技術者試験 午前 問26（IPA）

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

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

  要点：単方向リストの末尾削除は直前要素を探すため全体走査が要る

  単方向リストではポインタが先頭から末尾の一方向にしか張られていません。末尾の要素を削除するには、直前の要素のポインタを書き換える必要がありますが、末尾ポインタからは直前へ戻れないため、先頭から順にたどって末尾の一つ前を探す必要があります。他の3つは先頭ポインタ・末尾ポインタを1〜2回たどるだけで済みます。

  出典：令和1年度 秋期 応用情報技術者試験 午前 問6（IPA）

• ポインタを用いた線形リストの特徴のうち、適切なものはどれか。

  正解：ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。

  要点：線形リストの挿入・削除はポインタ操作だけで一定時間

  ポインタで連結された線形リストは、要素の追加・削除がポインタの張り替えだけで済む。挿入位置がポインタで指定されていれば、要素数や位置に関係なく一定の手間（計算量O(1)）で挿入できる。一方、任意の要素へアクセスするには先頭から順にたどる必要がある。

  出典：令和2年度 10月 応用情報技術者試験 午前 問5（IPA）

• CPUのスタックポインタが示すものとして、最も適切なものはどれか。

  正解：サブルーチン呼出し時に、戻り先アドレス、レジスタの内容などを格納するメモリのアドレス

  要点：スタックポインタはスタックの先頭アドレスを保持する

  スタックポインタは、スタック領域の先頭（次に読み書きする位置）のアドレスを保持するレジスタである。サブルーチン呼出しや割込みの際に、戻り先アドレスやレジスタの内容を退避するのがこのスタック領域であり、その位置を示すのがスタックポインタである。

  出典：令和2年度 10月 応用情報技術者試験 午前 問8（IPA）