『アルゴリズム図鑑』の元となったのは、Appleが2016年末に発表した「ベストApp10選」に選ばれたアプリ「アルゴリズム図鑑」です。
勉強しようと思っても、文字や少数の図解だけでは仕組み・概念を理解しづらいのがアルゴリズム。アプリではイラストで表現することでその課題を解決し、大変な好評を得ました。本書は紙幅を活かして一覧での見やすさを高め、26種類のアルゴリズムを徹底的にイラストで表現しました。
今回は本書から、データ構造の「リスト」、グラフを探索するアルゴリズムの「幅優先探索」、データを暗号化するアルゴリズムの「公開鍵暗号方式」、データを似たもの同士に分類するクラスタリングアルゴリズムの「k-means法」を紹介します。
リスト――データ構造
アルゴリズムの仕組みを理解するのであれば、そこで扱うデータの構造について知っておく必要があります。データはメモリに蓄えられており、その際にデータの順番や位置関係などを規定したものがデータ構造です。
データ構造の一つが「リスト」。データを一直線に並べた構造をしていて、データの追加や削除がしやすいメリットがある反面、アクセスには時間がかかるというデメリットもあります。
これはリストの概念図で、三つのデータが格納されています。各データを繋いでいるのがポインタで、メモリ上の位置を指し示します。
リストではポインタが位置関係を規定するため、メモリ上の連続した領域に格納される必要がありません。データは一般的に離れた領域に格納されています。
格納場所が異なるため、各データにはポインタを順に辿らないとアクセスできません（順次アクセス、またはシーケンシャルアクセス）。RedにアクセスしたいときはBlueからアクセスし、Yellowを経る必要があります。
データを追加するときは、追加する前後のデータのポインタを指し替えるだけなので簡単です。BlueとYellowの間にGreenを追加したいときは……
BlueのポインタをGreenに、GreenのポインタをYellowに向けます。これでデータが追加されたことになります。もちろんGreenのデータはメモリ上のどこにあっても構いません。
データの削除もポインタの指し替えで行います。Yellowを削除したいなら……
GreenのポインタをRedに指し替えましょう。Yellowはどこからもアクセスできないので、消す必要もなく、その領域は別のデータに上書きされて再利用されます。
ここで紹介したリストは最も基本的なもので、拡張されたものもあります。リストの最後尾のデータであるRedはポインタを持っていませんでしたが、Redから先頭のBlueへポインタを指せば「環状リスト（循環リスト）」ができ上がります。常に一定個の最新データを保持したいときに有用です。
また、各データに双方向のポインタを持たせて、「双方向リスト」を作ることもできます。リストを前からでも後ろからでも辿れるので便利ですが、ポインタの数が増えることでデータ格納のための領域が多くなる欠点もあります。
