基本情報技術者試験に向けて覚えておくべきデータ構造について解説

コンピュータ上ではどのようにデータを保管しているのでしょうか。コンピュータ上のメモリは有限ですので、メモリを効率的に使うためにもデータを保管する方法には工夫が必要です。そこで、データの特性に応じて、様々な構造を用いてデータを保管する必要があります。

基本情報技術者試験においても、様々なデータ構造についての理解が問われるため、対策として主要なデータ構造とそれらの特徴について押さえておく必要があるでしょう。

この記事では、基本情報技術者試験の対策としてデータ構造についての解説を行います。

データ構造とは

コンピュータでデータを扱うためには、それをどのような形式で保管するか定める必要があります。コンピュータ処理においてはメモリ上でデータを保管することになりますが、どのようにメモリを利用してデータを取り扱うかは、様々な方法が考えられます。

例えば、全く同じ大きさのデータであれば、一定間隔ごとにメモリを区切ってデータを格納していくのが最も効率的にメモリを使う方法でしょう。一方で、データの順序を頻繁に入れ替える場合は、一定間隔ごとに格納する方法でこのような保管方法をすると、データ入れ替えの度に多くのデータの配置を換える必要があり、非効率です。このような用途では別の管理方法が必要になるでしょう。

このように、データの特性に応じてメモリ上でデータを管理する形式は様々考えられます。この、データを管理するための様々な形式をデータ構造といいます。データの特性に応じて効率的にデータを保管できる形式として、様々なデータ構造が考え出され、利用されています。

以下では、主要なデータ構造についてその概要と特性を紹介していきます。

配列

配列とは、同じ形のデータを等間隔で順番に並べたものをいいます。例えば、コンピュータで文字情報を取り扱う際や、名簿など多数の同形式かつ多数の情報を取り扱う際などによく用いられるデータ構造です。

配列はもっとも基本的なデータ構造であり、利用頻度も高いです。

配列では、具体的には下図のようにデータを取り扱います。イメージとしては、コインロッカーのように同じ大きさの箱が多数並んでいる様子を思い浮かべるとよいでしょう。

配列においては等間隔でデータが並んでいるため、目的のデータが何番目に存在するかを指定することで、配列中の特定のデータを抜き出すことができます。配列の位置を指定する番号をインデックスといい、配列中に存在する各データを要素と呼びます。

一般的なプログラミング言語では、配列のインデックスは0からスタートしますので、例えば配列の10番目を指定したい場合には、インデックスは9を指定することになります。

配列には、インデックスを1つだけ使う1次元配列だけではなく、2つのインデックスを使う2次元配列、3つ使う3次元配列など、用途に応じて並びや大きさを変えることができます。

キュー

キューとは、筒にタスクを入れていくように先に入れたものから先に処理を実施していくデータ構造を言います。

キューを用いる場合、下図のようにデータを取り扱います。イメージとしてはコンビニのレジなどの待ち行列を想像していただけるとよいでしょう。先に並んだ人が先に処理を行うというのがキューの特徴となります。

キューは、処理の順序を変えずに一時的にデータを格納しておきたいときに良く用いられます。具体的には、ディスクへの書き込み待ちや、インターネット通信におけるデータの転送待ちなどにおいて、キューを用いてデータを管理することが多いです。

キューのように、先に来たデータを先に処理することを、FIFO（First in First out：先入先出法）といいます。合わせて覚えておくとよいでしょう。

スタック

スタックとは、コップにタスクを入れていくように、後に入れたものから先に処理していくデータ構造を言います。

スタックを用いる場合、下図のようにデータを取り扱います。イメージとしては、不精な人が管理する倉庫を想像していただけるとよいでしょう。先に入れたものから先に利用していくため、古いものはずっと倉庫に残ったままになるイメージです。

スタックは、新しいデータを先に処理したい場合に用いられます。よく利用されるのが、プログラミングの処理における関数の呼び出しです。

プログラムの流れにおいて、ある関数Aが呼び出されると、実行中の処理は中断してその関数Aの処理を開始します。その途中でさらに別の関数Bが呼び出されると、その関数Aの処理を中断して関数Bの処理を行います。そして、関数Bが完了すると関数Aに戻り、関数Aが完了すると呼び出し元に戻ります。

このような処理には、スタックを使った順序管理が適しています。

スタックのように、後に来たデータを先に処理することを、LIFO（Last in First out：後入先出法）といいます。合わせて覚えておくとよいでしょう。

リスト構造

リスト構造とは、データとデータの参照先（ポインタ）を合わせたデータ単位で構成され、次のデータの参照先を順々にたどっていくことでデータを参照していくデータ構造です。

リスト構造においては、ポインタの情報を変更することで、簡単にデータの並び変えやデータの追加・削除が可能であるため、頻繁に変更されるようなデータの取り扱いに適した構造です。一方で、目的のデータにたどり着くためにはポインタを何度もたどってデータを探さなければならないため、頻繁に参照されるようなデータには不向きの構造でもあります。

リスト構造には、大きく単方向連結リストと双方向連結リストの2種類が存在します。以下で、それぞれのデータ構造について解説します。

単方向連結リスト

単方向連結リストは、下図のように次のデータの参照先のみをリスト項目に保持するリストのことです。

次のデータの参照先のみを保持するため、逆戻りはできないものの、データ量を少なく抑えることができます。また、データの追加・削除時においても一つのデータのポインタのみを変更すればよいため、処理量が少なく済みます。

双方向連結リスト

双方向連結リストは、次のデータの参照先と前のデータの参照先のどちらもリスト項目に保持するリストのことです。単方向リストとは異なり、参照中に前の参照先に戻ることができます。ただし、その分データ量は多くなってしまいます。

リストへのデータ追加・削除

上述の通り、リストにデータを追加したり削除したりする場合は、リストのポインタを変更することで実施できます。他の構造と比較してデータの追加や削除がしやすいのがリスト構造のメリットです。

ここでは、単方向リストでのデータの追加を例に図示したいと思います。単方向リストにデータを追加する場合は、下図のようにデータの追加位置の前のデータのポインタと、追加するデータのポインタを書き換えることで実施が可能です。

木構造

木構造とは、階層構造を作るようにデータを保持し、データ同士に親子関係を持たせたものです。階層構造を持ったデータは、まるで木のように伸びていくことから、木構造またはツリーと呼ばれます。

木構造の頂点のことを根（ルート）といい、一つ一つの要素のことを節（ノード）といいます。また、節同士をつなぐ線のことを枝といい、木の終端の要素を葉といいます。

木構造には、木の作成の仕方に応じて様々な種類が存在します。ここでは、2分木、2分探索木、ヒープの3種類を紹介します。

2分木

2分木は、それぞれの項目から伸びる枝が必ず2本である木構造のことを呼びます。また、その中でもすべての節の深さが同じ（= 根からの葉の距離がすべて同じ）である場合は、完全2分木と呼びます。

2分木の用途としては、情報の探索などがあります。検索対象となるデータ群をまず2分木にすることで、データの探索時間を短縮することができます。特に探索を行う際には、後述する2分探索木を用いると効率的な探索が可能となります。

2分探索木

2分探索木は、2分木のうち、常に親のデータが左部分木のデータより大きく、右部分木のデータよりも小さくなるように構成されているものをいいます。具体的には下図の通りです。

2分探索木を作ることで高速にデータ探索を実現することができます。例えば、上図の2分探索木において8を探したい場合は、以下のように探索をすることでとても少ないステップ数で対象のデータを見つけ出すことができます。

1. ルートの値：10　→　8より大きいので、左に進む。
2. ノードの値：7　→　8より小さいので、右に進む。
3. ノードの値：8　→　8を発見。

ヒープ

ヒープとは、2分木のうち、すべての節で親より子のほうが小さくなっているもの（または大きくなっているもの）をいいます。具体的には、下図のようなイメージとなります。

ヒープは、特に探索を行う際に用いられるデータ構造です。2分木の根部分が必ず最大となるため、ヒープを作りながら根を抜いていくことを繰り返すことで整列を行うことができます。これをヒープソートといいます。

まとめ

この記事では、基本情報技術者試験を受けようとされている方に向けて、データ構造に関する内容の解説を行いました。

データ構造は、特にプログラミングを行う際には必須の知識となるでしょう。効率的にデータを取り扱うことは、優れたプログラミングを行うための必須知識です。これを機に、ぜひデータ構造について頭の中を整理してみることをおすすめします。