Array
Array には Array List と Linked List がある
Array Listはメモリ上に連続的に存在しているためindexさえあればアクセスできる
Linked List は Nodeを元に作成されており、indexでアクセスするためにはheadから辿る必要があり、O(n)かかる。
recursive
再帰は人間にも分かりづらいが stack を使うと分かりやすい
computerがrecursive function を実行するときに、現在の関数のローカル変数や関数のどこにいるのかを知る必要がある。これは runtime stack stack frame と呼ばれている。
Pythonなどではstack frame がでかく、n=1000くらいで最大に達する。よって安易に再帰はするべきでない
Linked List
Singly Linked List (単連結リスト）。普通の配列に比べて扱いにく過ぎだろ(readがO(N)なので)と思ったが、
連結リストは挿入が簡単というメリットがある。挿入する操作がnextを付け替えるだけで実装できるからだ。配列の場合は、挿入後にあるカラムを全部移動させなければならない。
Hash Map
hash = map = hashmap = dict. 呼び方は何でもあり。
基本的にhashmapは特定のアルゴリズムを用いてキーを探索しているためソートはしてくれない。けどなぜかPythonのdictはしてくれてる。なんで？
追記順ならいうてnextかなんか実装すれば順番通りにしてもO(1)ですむのかな？未だ謎は多い
Heap
英語で「山積み」という意味。データ構造のheapと、動的メモリ領域のheapがあるのでややこしいが、実はヒープ領域はヒープ構造で実装されているとかいないとか。
ヒープ木構造
インデックスは深さ探索。
親ノード(k)は子ノード（2k, 2k+1）よりも小さくなければならない。(k=1,2,3..)
ヒープ作成(build_min_heap)の最悪計算量はO(n), min_heapify(ヒープ構造を作る上で、上のルールを守るためにノードを入れ替える作業)の最悪計算量はO(logn)である。
ヒープ領域
未使用ノード、使用中ノードに分かれる。最初は一つの大きい未使用ノードで、mallocやnewでメモリ確保されると、未使用ノードから必要分切り離して与える。free or deleteされるとまた未使用ノードに戻るが、動的に削除されるのでフラグメンテーションが発生する。これをガベージコレクションでまとめないと再利用しにくい。