わかりやすく 配列 リスト ちがい

くっついたロッカー、配列

前のレッスンで、入れ物ごとに形が違うことを見ました。そのうちいちばん単純な形が配列です。番号の付いたますを一列にぴったりくっつけて並べたロッカーだと考えればよいでしょう。
ますの番号は、0番、1番、2番のようにふつう0から付けます。ますがすべて同じ大きさでくっついているので、始まりの位置にます一つ分の大きさを番号の数だけ足せば、そのますがどこにあるかがすぐに計算できます。

番号を押して、そのますへすぐにジャンプしてみましょう。ますがくっついているので、番号ですぐに見つかります。

番号を押すと、すぐにそのますが光りました。ますが並んでくっついているので、何番のますでも一回でたどり着きます。ますが十個でも百万個でも、かかる時間は同じです。
このように番号ですぐに取り出すことを速いアクセスといい、配列のいちばんの長所です。でも、ますは必ずくっつけておかなければならないのでしょうか。散らしておいたらどうなるでしょうか。

散らばったロッカー、リスト

リストは、ますをくっつけておきません。ますはメモリーのあちこちに散らばっています。では、順番はどうやってつなぐのでしょうか。ますごとにメモを一枚ずつ付けて、そのメモに次のますのある場所を書いておくのです。
だから、最初のますでメモを見て次のますへ、またそのメモを見てその次のますへとたどっていきます。ますがメモで次々につながっているので、この形を連結リストと呼びます。

メモを押して、次のますへたどってみましょう。ますは散らばっていても、メモが順番をつないでくれます。

メモをたどると、散らばったますが一列につながりました。番号ですぐに飛べる配列と違って、リストはメモを読みながら一ますずつ順に進まなければなりません。
少し手間に見えますが、この散らばった作りには思いがけない長所があります。それが何かは、すぐにわかります。

速いアクセスと遅いアクセス

では、二つを比べてみましょう。5番目のますを取り出したいとします。配列は番号を言えば終わりです。ますがくっついているので、一回で飛べます。
リストはそうはいきません。最初のますからメモをたどり、一ます、二ます、三ますと順に数えながら進まなければなりません。だから、探すますが遠いほど時間がかかります。

5番目を取り出してみましょう。配列は一回で、リストは最初から一ますずつ進みます。押した回数を比べましょう。

違いははっきりしています。配列は一回押しただけで着きましたが、リストは何回も押してやっとたどり着きました。取り出す仕事では、番号ですぐに飛べる配列のほうがずっと速いのです。
では、配列のほうがいつでもよいのでしょうか。そうではありません。次の場面では、リストが活躍する瞬間がやって来ます。まん中に何かをはさむときです。

まん中にはさむ

今度は、列のまん中に新しいますをはさんでみましょう。リストならとてもかんたんです。前のますのメモが新しいますを指すように直し、新しいますのメモが元の次のますを指すようにすればよいのです。
メモを二枚書き直すだけで、ほかのますには手をつけなくてかまいません。ますが百万個あっても、直すメモは二枚だけです。

まん中に新しいますをはさんでみましょう。リストはメモを二枚直すだけで、配列は後ろのますをすべてずらします。手間を比べましょう。

配列はどうだったでしょうか。まん中に場所をあけるには、後ろのますを一つずつすべてずらさなければなりませんでした。ますがくっついていて、すき間がないからです。リストはメモ二枚で終わりました。
だから、まん中によくはさむ仕事には、リストのほうがずっと便利です。速いアクセスは配列、かんたんな挿入はリスト。一つを得れば一つを手放す、引きかえの関係なのです。

まとめ

一言でまとめるとこうです。配列は番号の付いたますをくっつけて並べたロッカーなので、番号ですぐに取り出せます。リストは散らばったますに、次のますの場所を書いたメモを付けたものなので、まん中にはさむのがかんたんです。
5番目を取り出すなら配列が速く、まん中にはさむならリストが便利です。何をよくするかで選びましょう。

要点を順に押して振り返りましょう。（くっついたロッカー、配列 → 散らばったロッカー、リスト → 速いアクセスと遅いアクセス → まん中への挿入）

これで、同じ物でもどう入れるかによって得意な仕事が変わることがわかりました。配列とリストは、入れ物の形を選ぶ最初の分かれ道です。
次のレッスンでは、片方の端だけで出し入れする入れ物と、並んだ順にしか取り出せない入れ物、つまりスタックとキューを取り上げます。