データ構造まとめ

全体像を簡単に知りたい方向けです。データ構造はプログラミングの難易度や計算回数に直結します。実務でそこまで意識する機会もないと思いますが、一通り知っておくと裏側で起きている計算まで理解することができるでしょう。

データ構造の種類

• 配列と文字列
• 連結リスト
• スタックとキュー
• 木とグラフ

配列と文字列

◯配列

変数にインデックスを付けて扱えるようにするもの。

◯ハッシュテーブル

任意の種類のオブジェクト(キー)から任意の種類のオブジェクト(値)への関連付けを行うことが出来る。

◯※配列リスト(可変長配列)

実行時に自由にサイズを変えられる配列
Ruby/Perl/Pythonは自動的に調整してくれる。

連結リスト(リンクリスト)

自分の次、及び前の要素を示す情報を持つことで要素を連結させたリスト。

スタックとキュー

◯スタック(後入れ先出し)

スタックは、あるデータの集合にデータを一つ追加し、その後一つ取り出すと、最初に追加したものが取得できる性質のもの。
To Doリストなど。一番最後に登録したタスクから処理していく。
ex) [1,2,3,4]に5を入れる。(push)　5が出てくる。(pop)

◯キュー(先入れ先だし)

スタックと逆の動作。データの集合にデータを一つ追加し、その後一つ取り出すと、最初に追加されたデータが出てくる。
待合室データなど。一番最初に登録した人を処理していく。
ex) [1,2,3,4]に5を入れる。(enqueue)　1が出てくる。(dequeue)

木とグラフ

◯二分木と二分探索木

二分木とは、あるノードが持つ子の数が高々2であるもの。
二分探索木は、左の子ノードと親ノードより小さいか等しいかつ、右ノードよりも小さくなければならない。

◯平衡木と非平衡木

木構造のうち、根ノードから葉ノードまでの高さ(深さ)が等しくなるように構築されたもの。

◯完全二分木

全ての葉が同じ深さをもつ二分木。