処理速度・メモリの使用量・プログラミングの容易さのトレードオフの理解という点で、 まとめる。

• 単純配列
  • 検索処理O(N),挿入処理O(N)
  • 固定サイズで最大量不定ならメモリ使用効率×、巨大一定
  • 最大データ数が既知ならば、メモリの使用効率は高くできる。
  • プログラミングはそのまんま。
• 昇順配列
  • 2分探索法で検索処理O(log(N)),挿入処理O(N)
• 配列によるヒープ
  • 検索処理O(log(N)),挿入処理(入れ替えがあるとちょっと手間)

• 線形リスト
  • 検索処理O(N),挿入処理O(1)
  • メモリ量はデータに比例(ポインタ分のムダ)
  • スタックや待ち行列などで、最大データ数が分からない場合に便利。
• 循環リスト
  • 待ち行列など
• 双方向リスト
  • エディタなどの前後移動のあるデータ
• 2分木
  • 検索処理O(log(N)),挿入処理O(1)
  • 木の左右のバランスが重要。AVL木=O(log(N)),不均衡=O(N) worst
  • 2つのポインタを持つため、メモリのムダあり。
  • 全データ対象だと再帰などでプログラミングが難しい。
• B木
  • 検索処理O(log_d(N)),d=位数
  • データベースなどの基本技術
• ハッシュ法
  • 検索処理：表サイズ>Nなら、O(1) , 表サイズ<Nなら、O(N)
  • 同一ハッシュ値が求まった場合＝ハッシュ衝突
  • オープンアドレス法(ハッシュ値を求めなおす,イス取りゲーム？)
  • チェイン法(同一ハッシュ値をリスト構造で保存)