データ構造

データとはコンピュータが扱う情報のことを指します。データはコンピュータ内の主記憶装置（ハードディスクHDDやSSD）に保存されます。そしてこの保存された時のデータの並べ方によって処理速度が速くなったり遅くなったりします。このデータの並べ方をデータ構造と呼びます。

5種類のデータ構造

データ構造は以下の５つがあります。
スタック｜キュー｜配列｜連結リスト｜木構造（ツリー構造）

スタック

スタックはデータを１列に並べて後入先出（LIFO：Last In First Out）する方法です。本を積み上げるようなイメージでデータを追加する（push CでCを追加するという意味）ときは一番上に本を置く、そしてデータを取り出す時（popは指定なし）は一番上から取り出します。真ん中の本は取り出せないようにデータも取り出すことはできません。

スタックの特徴として行なった処理の過程を記録しておくと元の処理に戻ることができるというものがあります。

キュー

キューはデータを１列に並べて先入先出（FIFO：First In First Out）する方法です。待ち行列とも呼ばれます。キューを使うメリットとして命令を順番通りに処理できるというものがあります。enqueue DはDをキューに追加するという意味です。データを取り出すことをdequeue（指定なし）と言います。

試験によく出る項目

・スタックとは、先入後出しのデータ構造
・キューは先入先出のデータ構造

配列

配列はデータを表の形に並べたデータ構造です。配列では個々のデータを要素、要素の位置はインデックス（添え字）という数字で表します。

１次元配列

要素が１列に並んでいる配列は１次元配列と言います。以下配列をテスト配列Tとして定義します。

添え字	0	1	2	3
要素	菅野	山田	吉岡	高岡

ここで注意したいのが添え字が必ず０から始まるという点です。これはプログラミングを行なっていてもほとんどが０から始まるので注意しましょう。

配列から要素を取り出す

前述のテスト配列Tから２番目の要素を取り出したいとします。その際はT(1)として指定すると山田さんが取り出せます。この時T[1]としても同じ意味になります。

2次元配列

要素が縦の列と横の行を持っている配列を２次元配列と呼びます。表をイメージしてもらうとわかりやすいと思います。

添え字	0	1	2	3
0	吉田	女性	45歳	栃木県
1	狭山	男性	56歳	鳥取県

上記のような２次元配列Hから「２番目の行の４番目の列の要素」を取り出す例を考えてみましょう。H（1,3）で鳥取県という要素が取り出せます。

試験によく出る項目

２次元配列の要素を取り出す時の書き方は配列名（行,列）

連結リスト

連結リストの特徴としてポインタというものがあります。これまで要素（連結リストではセルと呼ばれることもあります）には添え字という数値がついてきました。それに対してポインタは「次の要素の主記憶装置上の位置」を示すものです。要素はこのポインタによって数珠つなぎに並んだ状態になっています。

↑この連結リストは単方向にデータを辿ることができるので単方向リスト（線形リスト）と呼ばれます。

循環リスト

単方向リストの最初と最後がつながっているものを循環リストと呼びます。

双方向リスト

単方向リストに対して双方向リストは前後の情報を持っている状態です。

配列と連結リストの違い

配列と連結リストはともにデータが順番に並んでいるというところは共通しています。しかし、データにアクセスする方法が違ってきます。

配列は添え字でアクセスすることでデータに直接アクセスできます。
一方で連結リストはポインタを使うことでリストの先頭から順番に要素を辿る必要があります。これらの特徴からメリットデメリットが生まれます。

連結リストのデメリット

連結リストは要素数が増えるとデータ呼び出し（データへのアクセス時間）に時間がかかるという特性があります。
これは配列にとっては逆の動きとなりメリットになりますので配列は要素数が増えてもデータ呼び出しが高速に行えるという特徴があります。

配列のデメリット

配列にもデメリットがあり、データを挿入、削除する際に発生します。後ろの要素を全て１つずつずらす必要が出てくるのです。
要素が増えると挿入、削除に時間がかかるという特徴があります。
これは連結リストでは逆の動きになるのでメリットとなり、要素が増えても挿入、削除が高速に処理できるという特徴があります。

試験によく出る項目

・配列は参照・更新が早く、挿入・削除が遅い
・連結リストは挿入・削除が早く、参照・更新が遅い

木構造（ツリー構造）

木構造の特徴は階層構造をもつデータ構造というところです。わかりやすいものとしては入れ子のカテゴリをイメージしてもらうと良いかもしれません。地域→県→市→町などのカテゴリはまさに階層を持った木構造といえます。

木構造の名称

ツリー構造には大きく３つの種類があります。
・２分木
・完全２分木
・２分探索木

２分木とは

以下の図のような木の形をしたデータ構造です。節から伸びる枝が２本以下であるものを二分木と呼びます。

完全２分木とは

前述の図では親から１つの子が伸びているところがありましたが、全ての親から子が２つ必ず伸びていてかつ深さが同じものを完全２分木と呼びます。（綺麗なピラミッド型の三角形になっているとも言えますね）

２分探索木

親と子の関係性が「左の子＜親＜右の子」となるものを２分探索木と呼びます。

木構造の親子関係