こんにちは。
今回は前回のアルゴリズムに引き続き、データ構造の基礎を自分の中でまとめるための備忘録です。

##データ構造とは
データ構造とはコンピューターの中にデータを格納する型のことを指します。
プログラミングを設計する上で、データの処理の方法を事前に考え、最適なデータ構造を用いる必要があります。

##データ構造の種類
データ構造にはいくつか種類があり、データの扱いによってそれぞれ適した型があります。
ここでは元Googleのソフトウェアデベロッパーとして働かれていたCSDojoというYou　Tuberの動画で挙げられている例を参考に、代表的な配列（Array）とリスト（Linked list）というデータ構造についてまとめていきます。

例:
あるところで100人が参加するパーティが開かれます。
主催者はとても忙しく、パーティ当日に来た参加者の名簿を管理する時間がありません。
そこで参加者にひとりひとり自分の名前が書かれたボールを持ってきてもらい、
会場の入り口で用意した箱に自分のボールを入れてもらうことにしました。

この箱の形を以下の画像のように一続きに繋がった配列（Array）と、それぞれの箱が独立してその前後の箱同士の情報が連なっているリスト（Linked list）に分けて扱い、データ構造をみていきます。

####配列（Array）
画像の上段の配列（Array）によるパーティ出席者の名簿管理方法は、1番から100番までの箱が一つに繋がったものを使用します。
参加者はきた順番に左から自分の名前が書かれたボールを入れていきます。
画像ではDavid、Kevin、Andrewの順番にボールが入れられています。
######配列を使うメリット
もし仮に98番目に来たJamesが自分の名前のスペルを間違えてボールを箱に入れていたとします。
その場合、長い箱の中から順番に数えて98番目の箱にあるボールを正しくスペリングしたものと入れ替えれば良いため、98個目の箱を簡単に探すことができます。
######配列を使うデメリット
今回のパーティの事前予約は100人でしたが、参加者の数名が予約をしていなかった友達を連れてきてしまったため参加者が100人を超えてしまいました。
もともと100個の箱が連なる長い箱を用意しましたが、これでは全ての参加者のボールを格納することができません。
そこで主催者は忙しいにも関わらず次の二つの選択肢から新たな箱を用意しなければなりませんでした。
1. 既に作っていた100個続きの箱Aとは別に新たな100個続きの箱Bを作って箱Aと箱Bを同時に使う
2. 新たに200個の箱が連なった長い箱Cを作り、そこに既に箱Aに入れられていたボール100個を移し替え、そのあとにきた新たな参加者のボールを追加する

####リスト（Linked list）
画像の下段のリスト（Linked　list）によるパーティ出席者の名簿管理方法は、1番から100番までの箱がその前後同士のみで繋がったものを使用します。
箱が置かれている位置はバラバラで、例えば1番の箱は玄関に置かれており、そこには次の番号である2番の箱の情報が「2番の場所はリビングのソファの下」という風に示されています。
参加者は若い番号の箱に順番に、自分の名前が書かれたボールを入れていきます。
画像では配列(Array)と同様、David、Kevin、Andrewの順番にボールが入れられています。
######リストを使うメリット
配列では新たに予想外の参加者が来た時、大きな手間が発生しましたが、リストの場合必要分の小さな箱を用意し前後の情報を繋げるだけで簡単に対応することができます。
######リストを使うデメリット
配列では98番目に来たJamesのスペルの間違ったボールを簡単に取り替えることができましたが、リストの場合1番から順番に情報をたどって98番目の箱を探しに行かなくてはなりません。
主催者は忙しいにも関わらず**「玄関→リビングのソファの下→トイレの芳香剤の裏→寝室の枕の下...」という風に一つ一つの箱に書いてある次の箱の情報をたどって98番目の箱を探す羽目になってしまいました。**

##まとめ
以上、今回はパーティの例を参考に代表的なデータ構造である配列とリストについてまとめました。
もしこの記事の解釈が間違っているということがあれば気軽にご指摘ください！