アルゴリズム ~データ構造~

データ構造は端的に話せば、データの並び方である。電話帳をイメージするとわかりやすいだろう。

電話帳を追加すると50音順に並べることもあれば、追加した順番、メールアドレスのアルファベット順など
並び方がさまざまである。

データ構造によって処理速度に影響を及ぼす。ではどのような影響を及ぼすのか、
またどのようなデータ構造があるのかを見ていく。

どのような影響?

追加した順番だと、ランダムに並ぶことを意味する。追加した日付が古い順に並び、データに対する集合体の順序で並ぶわけではない。これが重要なポイントである。例えば、追加した電話帳を「検索する際に」検索にかなり負荷がかかる。理由は、並ぶ順序と欲しいデータに関連性がないからだ。 一方で、名前順に関しては検索しやすい。山田さんや佐々木さん、など欲しいデータの情報を元に検索するために検索負荷は少なく、処理橋やすい。しかし、更新においては、並ぶ順序に従って追加、削除するため負荷がかかる。

Ex
青木さん, 金子さん、佐々木さん....

ここに柿谷さんを入れたい。となれば、金子さんと佐々木さんの間に入れなければいけない。一行削除して、柿谷さんを追加するため、負荷がかかる。
このようにデータ処理において、データ構造は密接に関わる。

データ構造の種類

上記のように処理に応じて適切なデータ構造は異なるため、データ構造の種類を理解する必要がある。 いかに紹介する

1. リスト

   1. リストはデータ構造の一つで,「データを一直線に並べた構造」。追加や削除画しやすい反面、アクセスには時間がかかる

   BLUE→Yellow→RED
   と並び、それぞれにはポインタと言われるものが存在し「対」になっている。データのメモリ上の位置を指し示す。リストにあるデータは連続した領域に格納される必要はなく一般に離れた領域のバラバラになる。

バラバラに格納されているため、各データはポインタを辿ることでしかアクセスできない。

上記で言えば、Redにアクセスしたいなら、BLUE→Yellowとたどらないといけない。
アクセスはめんどくさい。
一方で、データの削除や追加はしやすい。ポインタを組み替えて作成しなおせば、削除や追加ができる!!

計算時間は、データの数をnにした場合の計算時間が(線形探索になるので)アクセスしたいデータが後の方にある場合はO(n)になる!追加・削除時間はO(1)の時間になる!

各自で調査して欲しい単語
環状リスト
双方向リスト

1. 配列
   配列はデータ構造の一つで、データを一列に並べる。リストとは対称的に「データへのアクセスは簡単だが追加や削除には時間がかかる。」

配列のなかのデータには添え字 ([0],[1]...)が存在し、メモリの連続した領域に順番通り格納される!
アクセス時は、添字を使って計算ができ各データに直接アクセスできる(ランダムアクセス)

一方で、データ追加・削除はコストがかかる。
空白のデータは末尾に作り、追加箇所　≒該当箇所までずらしていく。

削除する際は、先に該当箇所(データ)を削除し、空白ができるのでずらして埋める。

配列の計算時間
アクセスする時間は、「O(1)」。削除や追加する際は、1つずつずらさないといけないため、データ数nに対し、O(n)かかる。

1. スタック
   スタックは、データを1列に積み上げた時のように新しく追加したデータからしかアクセスできない。新しいデータが到着すると、現在のデータの一番上に置かれる。スタックからデータを取り出す場合は一番上　つまり、最新のデータから取り出される。
   スタックのように後から入れたデータを先に取り出すことをLIFOと呼ぶ

2. キュー

   1. キューはデータを一列に並べた構造である。簡潔に話せば、待ち行列である。行列はアタrしく来た人は一番後ろに座り、一番前の人から処理される。　スタックと真逆の処理がなされる。

3. ハッシュテーブル

4. ヒープ
   ヒープはプライオリティキューを実現するために使われている。プライオリティキューは「データ構造の1種で、データを自由に追加できる。一方で、データを取り出すときには最小値から選ばれる。自由に追加でき、小さいものから取り出す。」ヒープを取り出す木構造は各頂点をノードと呼ぶ

   ヒープの基本: 親が一番最小値になるようにセットする。データを追加する際に、親の数字　 > 子供の数字になっていたら繰り返し取り替えていく。

5. 2分探索木