応用情報技術者 試験情報＆徹底解説

ポインタを用いた線形リストの特徴として、「ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定」と書いてあるのですが、ポインタの場合、先頭から追加位置や削除位置を探す必要があるので、最大でO(N)になる気がしており、一定という回答が良く理解できません。
(リストの最初や最後に追加する場合にO(1)になることは理解できます)
考え方が誤っていましたらご教示いただけますと幸いです。

「データへのアクセスにかかる計算量」と「新たな要素を追加する計算量」を分けて認識するとわかりやすいかもしれません。

umejiroさんはデータへのアクセスにかかる計算量について考えておられますね。
中間データへのアクセスという意味では計算量はO(N)になりますので認識の通りで合っております。

説明文には"ポインタによって指定されている要素"という前提があるのでデータへのアクセス時間は既に済んでいると考えてOKです。

説明文には"新たな要素を追加する計算量"とありますのでポインタを用いた線形リストにおいては中間データの追加にかかる計算量は一定となります。

まとめますよ、umejiroさんは「データへのアクセスにかかる計算量」と「新たな要素を追加する計算量」の合計は一定ではないという理解をしているのだと思います。
今回の説明文は「新たな要素を追加する計算量」のみに焦点を当てていますので、計算量は一定ということになります。

参考になれば幸いです。

>Anonymousさん
ご回答いただきましてありがとうございます。
ポインタが既に指定されているという前提であれば、要素の個数や位置によらず一定であることを理解出来ました。誠にありがとうございました。