「変数」，「配列」，「リスト」，「スタック」，「キュー」などのデータ構造は，アルゴリズムやプログラミングを学ぶ上で必須となる重要分野です。しかし，「FIFOとLIFOの違いが分からない」，「木構造の探索が苦手」という方も多いのではないでしょうか。
このページでは，基本情報技術者試験で頻出となるデータ構造を，図や具体例を交えながらシンプルに整理していきます。
- 変数＝データを一時的に格納する記憶領域
- 配列＝同じ型のデータを連続して管理する構造
- リスト＝ポインタでデータ同士を連結する構造
- キュー＝先入れ先出し（FIFO）
- スタック＝後入れ先出し（LIFO）
- 木構造＝階層関係を表す構造
後半には練習問題も用意しています。理解を確認しながら進めていきましょう。
データ構造とは
変数とは
変数とは，データを一時的に格納する記憶領域のことをいいます。
※ データは，主記憶装置に格納される
※ 変数は，名前（変数名）を付けて管理する
※ 定数…値が変化しない数字や文字列
値の代入とは
変数に値を格納することを代入といい，擬似言語では次のように記述します。
※ 擬似言語…アルゴリズムを表現するための擬似的なプログラム言語。基本情報技術者試験などで使用される。詳細は「流れ図と擬似言語によるプログラミングの基礎まとめ」を参照
変数名 ← 値
※ 数字や文字などを代入することができる
たとえば，変数aに10を代入する場合は，次のように記述します。
a ← 10
※ 代入先の変数に値が格納されていた場合は，新しい値に置き換わる
練習問題
問1 変数とは何かを説明しなさい。また、変数と定数の違いも簡潔に述べなさい。
変数とは，データを一時的に格納し，必要に応じて値を変更できる記憶領域である。変数は値を変更できるが，定数は一度決めた値を変更できない。
問2 次の擬似言語の実行結果を答えなさい。
a ← 10
b ← a
a ← 20
10
配列とは
配列とは，同じデータ型の複数のデータを連続して配置するデータ構造のことをいいます。
一次元配列とは
一次元配列は，データが一方向に並んでいるデータ構造です。それぞれの要素の値は，添字を指定して参照します。
配列名[番号]
一次元配列への値の代入とは
一次元配列の要素に値を代入する場合，擬似言語では次のように記述します。
配列名[番号] ← 値
※ 数字や文字などを代入することができる
たとえば，配列bの4番目の要素に10を代入する場合は，次のように記述します。
b[4] ← 10
※ 代入先の配列の要素に値が格納されていた場合は，新しい値に置き換わる
二次元配列とは
二次元配列は，データが縦と横に並んでいるデータ構造です。それぞれの要素の値は，添字を指定して参照します。
配列名[行番号, 列番号]
二次元配列への値の代入とは
二次元配列の要素に値を代入する場合，擬似言語では次のように記述します。
配列名[行番号, 列番号] ← 値
※ 数字や文字などを代入することができる
たとえば，配列cの2行目4列目の要素に10を代入する場合は，次のように記述します。
c[2, 4] ← 10
※ 代入先の配列の要素に値が格納されていた場合は，新しい値に置き換わる
配列の操作とは
配列の探索とは
配列で要素の探索を行う場合は，先頭データから順に探索データが見つかるまで調べます（線形探索の場合）。
配列の更新とは
配列で要素の更新を行う場合は，更新するデータを探索により調べ，新しいデータに書き換えます。
配列への挿入とは
配列で要素の挿入を行う場合は，必要に応じて配列のサイズを拡張し，挿入する位置よりも後ろのデータを１つずつ後ろに移動して，空いた位置にデータを書き込みます。
配列からの削除とは
配列で要素の削除を行う場合は，削除するデータを削除し，空いた位置に後ろのデータを順に詰めて移動します。
練習問題
問1 一次元配列と二次元配列の違いを説明しなさい。
一次元配列はデータが一方向に並ぶ構造であり，二次元配列は縦と横の二方向にデータが並ぶ構造である。
問2 次の擬似言語の実行結果について，配列bの状態を答えなさい。
b[1]=2, b[2]=4, b[3]=6
b[2] ← b[1] + b[3]
b[1]=2, b[2]=8, b[3]=6
問3 次の文は，配列にデータを挿入・削除する手順を説明したものである。（ ）内に当てはまる語句を記入しなさい。
① 配列で要素の挿入を行う場合は，必要に応じて配列のサイズを（ ）し，挿入する位置よりも後ろのデータを１つずつ（ ）に移動して，空いた位置にデータを書き込む。
② 配列で要素の削除を行う場合は，削除するデータを削除し，空いた位置に（ ）のデータを順に詰めて移動する。
① 拡張，後ろ
② 後ろ
リストとは
リストとは，データを連結したデータ構造のことをいい，データを格納するデータ部と，次のデータの位置を格納するポインタ部から構成されます。
単方向リストとは
単方向リストは，次のデータの位置を示すポインタのみを持つリストです。データを，先頭から末尾の方向のみにたどることができます。
双方向リストとは
双方向リストは，前のデータの位置を示すポインタと，次のデータの位置を示すポインタを持つリストです。データを，先頭からも末尾からもたどることができます。
環状リストとは
環状リストは，単方向リストの最後のデータのポインタに，先頭データの位置を示すポインタを持たせたリストです。データを，環状にたどることができます。
リストの操作とは
リストの探索とは
リストで要素の探索を行う場合は，先頭から順にポインタをたどり探索データが見つかるまで調べます。
リストの更新とは
リストで要素の更新を行う場合は，更新するデータをポインタをたどって調べ，新しいデータに書き換えます。
リストへの挿入とは
リストで要素の挿入を行う場合は，挿入するデータのポインタに次のデータのアドレスを書き込み，挿入する位置の前のデータのポインタを挿入するデータのアドレスに書き換えます。
リストからの削除とは
リストで要素の削除を行う場合は，削除するデータの前のデータのポインタを，削除するデータの次のデータのアドレスに書き換えます。
配列によるリストとは
リストは，配列により表すこともできます。
練習問題
問1 単方向リストと双方向リストの違いを説明しなさい。
単方向リストは次の要素の位置を示すポインタのみを持つが，双方向リストは前後の要素の位置を示す2つのポインタを持つ。
問2 次の文は，リストにデータを挿入・削除する手順を説明したものである。（ ）内に当てはまる語句を記入しなさい。
① リストで要素の挿入を行う場合は，挿入するデータのポインタに（ ）のデータのアドレスを書き込み，挿入する位置の（ ）のデータのポインタを挿入するデータのアドレスに書き換えます。
② リストで要素の削除を行う場合は，削除するデータの（ ）のデータのポインタを，削除するデータの（ ）のデータのアドレスに書き換える。
① 次，前
② 前，次
問3 次の①，②に答えよ。
① 次の単方向リストにおいて，データBの次にデータXを挿入した後のリストの状態を答えなさい。
A → B → C → D
② 次の単方向リストにおいて，データCを削除した後のリストの状態を答えなさい。
A → B → C → D
① A → B → X → C → D
② A → B → D
広告
キューとは
キューとは， 先に格納したデータを先に取り出す，先入れ先出しの性質を持つデータ構造です。
※ キューは，待ち行列とも呼ばれる
※ 先入れ先出し…FIFO（First In First Out）
- エンキュー（ENQ：enqueue）… キューにデータを格納すること
- デキュー（DEQ：dequeue）… キューからデータを取り出すこと
キューへのデータの格納とは
配列を使用してキューにデータを格納する方法は，次のとおりです。
キューからのデータの取り出しとは
配列を使用してキューからデータを取り出す方法は，次のとおりです。
練習問題
問1 キューの特徴を説明しなさい。
キューは先入れ先出しのデータ構造である。
問2 次の操作後のキューの状態を答えなさい。
enqueue A
enqueue B
dequeue
enqueue C
スタックとは
スタックとは，後に格納したデータを先に取り出す，後入れ先出しの性質を持つデータ構造です。
※ 後入れ先出し…LIFO（Last In First Out）
- プッシュ（push）…スタックにデータを格納すること
- ポップ（pop）…スタックからデータを取り出すこと
スタックへのデータの格納とは
配列を使用してスタックにデータを格納する方法は，次のとおりです。
スタックからのデータの取り出しとは
配列を使用してスタックからデータを取り出す方法は，次のとおりです。
練習問題
問1 スタックの特徴を説明しなさい。
スタックは後入れ先出しの構造である。
問2 次の操作後のスタックの状態を答えなさい。
push A
push B
pop
push C
木構造とは
木構造とは，要素同士の関係を階層構造で表すデータ構造のことをいいます。
2分木とは
2分木とは，すべての枝の分岐が2つ以下である木構造をいいます。
2分木の走査とは
走査とは，すべての節を一定の順序でたどることをいい，次のような種類があります。
完全2分木とは
完全2分木とは，根から葉までの深さがすべて等しいか，1つだけ深い根が木全体の左側にある木構造のことをいいます。
2分探索木とは
2分探索木は，データの探索に適したデータ構造で，「左の子の値＜節の値＜右の子の値」という大小関係を持っています。
2分探索木の探索とは
2分探索木への挿入とは
2分探索木からの削除とは
ヒープとは
ヒープとは，すべての節で「親の節の値＞子の節の値」，または，「親の節の値＜子の節の値」の大小関係が成り立つ木構造をいいます。
練習問題
問1 次の2分木について，①，②に答えなさい。
① 根・葉・節を答えなさい。
② 先行順・中間順・後行順でたどった結果を答えなさい。
① 根：A 葉：D，E，F 節：A，B，C，D，E，F
② 先行順：A → B → D → E → C → F
中間順：D → B → E → A → C → F
後行順：D → E → B → F → C → A
問2 次の2分木について，①～③に答えなさい。
① データ「6」を探索するときにたどる順序を答えなさい
② データ「4」を追加した後の状態を答えなさい。
③ データ「1」を削除した後の状態を答えなさい。
① 5 → 7 → 6
② 
③ 
問3 次の2分探索木の説明文の（ ）内に当てはまる語句を記入しなさい。
2分探索木では，左の子には親より（ ）値を，右の子には親より（ ）値を格納する。
小さい，大きい
まとめ
今回は，データ構造について，基本情報技術者試験で重要となる内容を中心にシンプルにまとめました。特に重要なのは，各データ構造の特徴と用途を整理して理解することです。変数は単一のデータを保存する基本要素です。配列は複数データを連続して格納し高速にアクセスできます。リストは挿入・削除に強い構造です。キューは先入れ先出しで順番処理に使われます。スタックは後入れ先出しで再帰や式処理に使われます。木構造は階層データや探索に利用されます。さらに，二分探索木やヒープは探索やソートと関係が深く，効率的な処理を支えます。暗記ではなく，データの流れを意識して理解することが重要です。
実践的な内容を学びたい方は，開発環境を構築するところからはじめてみてください。
理解が進んだら，基本情報技術者試験の過去問題にもチャレンジしてみてください。
- データ構造の過去問・解説
※ このページでは読みやすさを考慮し「コンピューター」，「サーバー」など長音付きで表記していますが，試験では「コンピュータ」，「サーバ」と表記されます
