分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

• 挿入するデータの次ノードへの参照に現在の先頭ポインタの値をセットし、リストの先頭ポインタに挿入するデータのポインタをセットします。ポインタを参照する回数は1回です。
• 現在の先頭のデータが持つ次ノードへの参照を、先頭ポインタにセットすることで先頭のデータがリストから削除されたことになります。先頭ポインタ→先頭データで1回。
• 末尾ポインタから末尾データへ飛び、末尾データの次ノードへの参照を追加するデータにします。末尾ポインタに追加するデータの参照をセットします。末尾ポインタ→末尾データで1回。
• 正しい。末尾のデータを削除するには、末尾の1つ前のノードがもつ次ノードへの参照を空にし、末尾ポインタに末尾の一つ前のデータのポインタをセットしなくてはなりません。単方向リストなので末尾のデータから一つ前のデータへの逆方向の参照はできず、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。

つまり「エ」の「末尾のデータを削除する処理」の場合、ポインタをたどる回数がリストが保持するデータ数にほぼ等しい回数となるため「ア」「イ」「ウ」の処理に比べて極端に多くなります。

例として長さが5であるリストを用いてそれぞれのポインタの参照回数を考えてみましょう。(リストデータは[このデータのポインタ:次ノードのポインタ]で構成され、初期状態は[1:2][2:3][3:4][4:5][5:-]，先頭ポインタ1，末尾ポインタ5とします)

• 「ア」〔リストの先頭にデータ[6:-]を挿入する〕
  
  1. 挿入するデータ[6:-]の次ノードへのポインタに現在の先頭ポインタの値をセットする。
     　[6:1]
  2. 先頭ポインタに挿入するデータのポインタをセットする。
     　先頭ポインタ＝6
  3. 以上で完了なのでポインタの参照回数は1回です。
     　[6:1][1:2][2:3][3:4][4:5][5:-]，
     　先頭ポインタ6，末尾ポインタ5
• 「イ」〔リストの先頭のデータを削除する〕
  1. 先頭ポインタを参照し、先頭データ[1:2]を得る。
  2. 先頭データ[1:2]がもつ次ノードへのポインタを先頭ポインタにセットする。
     　先頭ポインタ＝2
  3. 以上で完了なのでポインタの参照回数は2回です。
     　[2:3][3:4][4:5][5:-]，
     　先頭ポインタ2，末尾ポインタ5
• 「ウ」〔リストの末尾にデータ[6:-]を挿入する〕
  1. 末尾ポインタを参照し、末尾データ[5:-]を得る。
  2. 末尾データの次ノードへのポインタに挿入するデータへのポインタをセットする。
     　[5:6]
  3. 末尾ポインタに、挿入するデータへのポインタをセットする。
     　末尾ポインタ＝6
  4. 以上で完了なのでポインタの参照回数は1回です。
     　[1:2][2:3][3:4][4:5][5:6][6:-]，
     　先頭ポインタ1，末尾ポインタ6
• 「エ」〔リストの末尾のデータを削除する〕
  このリストは各データが次ノードへのポインタのみを保持する単方向リストのため、リストの末尾以外のデータを参照する場合には先頭から順にポインタをたどっていく必要があります。
  
  1. 先頭ポインタを参照し、先頭データ[1:2]を得る。
  2. 先頭データ[1:2]を参照し、次ノード[2:3]を得る。
  3. データ[2:3]を参照し、次ノード[3:4]を得る。
  4. データ[3:4]を参照し、次ノード[4:5]を得る。
  5. データ[4:5]がもつ次ノードへのポインタを削除する。
     　[4:-]
  6. 末尾ポインタに、末尾の1つ前のデータのポインタをセットする。
     　末尾ポインタ＝4
  7. 以上で完了なのでポインタの参照回数は4回です。
     　[1:2][2:3][3:4][4:-]，先頭ポインタ1，末尾ポインタ4

このように「エ」の操作はリストを末尾方向に1つずつたどっていく必要があるため、ほぼリストの長さと同じだけポインタの参照が発生することがわかります。