データ構造 (配列・リスト)

入れ物というより、入れ物の中の並べ方のルール、と言ったほうが近いわね。
同じデータでも、どう並べるかで使い勝手がガラッと変わるのよ。

まず基本中の基本が配列?
よ。
マンションの部屋みたいに、同じ大きさの箱がぴったり連続して並んでいるの。

ふふ、最初は戸惑うわよね。
でもこれには理由があるの。
配列は先頭の住所(アドレス)から『何個ぶんずれた所か』で位置を計算するから、先頭そのものは『0個ずれ』なのよ。

それが、そうもいかないのよ。
配列には弱点があってね。
途中にデータを差し込んだり、消したりするのが大変なの。

満員の映画館を想像してみて。
前のほうの席に1人割り込ませようとしたら、後ろの人が全員ひとつずつ席をずれないといけないでしょう?

ところが、こちらにも弱点があるの。
連結リストは添字でいきなり飛べないのよ。
100番目が欲しければ、先頭から99回メモを辿るしかないの。

大丈夫よ。
O(1)は『データが何個あっても手間は変わらない』、O(n)は『データが増えた分だけ手間も増える』。
それだけ覚えておけば十分。

いい質問。
実はそのどちらでもなくて、両者のいいとこ取りをした動的配列?
という仲間なの。

ちなみに、最初からサイズが固定で変えられない配列は静的配列?
と呼ぶわ。
動的配列と対で覚えておくといいわよ。

まとめるわね。
配列は『番地で一発アクセス、でも割り込みは苦手』、連結リストは『割り込み得意、でも頭から辿るのは苦手』。
この対比と、添字アクセスが O(1) という点を押さえれば、試験はばっちりよ。