データ構造

同じデータでも、しまい方を変えると得意な操作と苦手な操作が変わります。どれかが万能なのではなく、何をよくやるかで選ぶものだ、というところまで見ていきます。

• 配列と連結リスト: 先頭への挿入は連結リストが1手、配列は全部ずらすので要素数ぶんかかります。逆に「n番目を取り出す」は配列が1手、連結リストは先頭からたどるぶんだけかかります。
• ハッシュテーブル: キーから計算で場所を決めます。同じ場所になること（衝突）が起きると、その中を順に見ることになり遅くなります。入れ物の数を変えて衝突の頻度を確かめられます。
• 二分探索木: 「小さいものは左、大きいものは右」の規則だけで作ります。小さい順に入れると一直線になり、探索が遅くなります。

スタックとキューは、スタック・キューのページで扱っています。