主にWEB+DB PRESS vol.91を参考に、ポイントだけを抜粋しました。
データ構造の基礎が全然無いと感じる方は、↑を読むのが一番良いと思います。
僕も、初めてデータ構造の基礎をまともに学んだのですが、非常に分かりやすかったです。
配列
-
構造
- 連続したメモリ領域を確保
- 使用しているメモリが連続しており、配列の中身の型が同じため、ランダムアクセスが一発でできる
-
特徴(どんな操作に強くて、どんな操作に弱いか)
- ○ : ランダムアクセス
- × : 要素の追加
-
C#で該当するコレクション
- List
連結リスト
-
構造
- メモリに、要素の値と次の要素への参照を持つ
-
特徴
- ○ : 要素の追加
- × : ランダムアクセス
-
C#で該当するコレクション
- LinkedList
ハッシュテーブル
-
構造
- bin(あるいはバケット)と呼ばれるものを配列で沢山用意し、その各要素に連結リストへの参照を持つ
- キーのハッシュ値とbinの要素数の剰余を取って、binの該当する要素に値を格納する
- 要素数が増えたら、rehashを行う。rehashとは、更に要素数の多いbinを用意し、古い要素を移動すること。
- 連結リストの要素数が増え、探索のコストが大きくなるため
-
特徴
- ○ : ランダムアクセス・要素の追加・削除
- × : メモリ効率
-
C#で該当するコレクション
- Dictionary
- HashSet
-
Dictionary・Setのどちらを選択するか
Setは、要素の値を重複させたくない場合に利用
ツリー
-
構造
- 親ノードの左のリーフノードに親ノードより大きな値を持った要素、右に小さな値を持った要素など、一定の規則に従って要素を持つ
-
特徴(どんな操作に強くて、どんな操作に弱いか)
- ○ : ハッシュテーブルよりもメモリ効率が良い
- × : 運が悪いと探索のコストが大きくなる
-
C#で該当するコレクション
- SortedDictionary
- SortedSet
参考
- WEB+DB PRESS Vol.91
- 未確認飛行、コレクション概要(コレクションとデータ構造の対応表)
- C#コレクションの使い分けのヒント