基本情報技術者試験のデータ構造について初心者向けに分かりやすく解説します。
配列とリストの仕組みや特徴、単方向リスト・双方向リスト・環状リストの違いを図付きで学べます。
データ構造
データ構造とは
データ構造とは、データを効率よく格納し、検索・追加・削除などの操作を行いやすくするための仕組みです。
例えばショッピングサイトのショッピングカートに購入したい商品を格納したり、社員番号の大小関係を利用したツリー構造で効率の良い検索をしたりします。
基本情報技術者試験では、配列、リスト、スタック、キュー、木構造がありますが、本書は配列とリストについて説明します。
キューとスタックについてはこちらを参照ください。
配列
配列は、同じ種類のデータを順番に並べて管理する最も基本的なデータ構造です。
各データには「添字（インデックス）」と呼ばれる番号が付けられており、その番号を指定することで目的のデータへ素早くアクセスできます。
基本情報技術者試験では、配列の仕組みや添字の考え方、配列へのアクセス方法などがよく出題されます。
添字（インデックス）は多くのプログラミング言語で0から始まります。
基本情報技術者試験でも基本的に0始まりです。
配列とは
配列とは、複数のデータを連続した領域に順番に格納するデータ構造です。
例えば、5人分のテストの点数を管理する場合、1つずつ別々の変数を用意するのではなく、配列を使うことでまとめて管理できます。
配列の特徴
配列は次の特徴があるので、プログラム開発時によく用いられます。
- 同じ種類のデータをまとめて管理できる
- 添字（インデックス）を指定して素早くアクセスできる
- データが連続して格納されるため、検索や読み込みが高速
配列には次の注意点もあります。
- 途中への追加や削除では、後ろのデータを移動する必要がある
- 格納できる要素数は途中で変更できない場合がある（静的配列）
配列の出題傾向
基本情報技術者試験では配列に格納されている値の検索や、配列を使った計算といった問題が出題されます。
配列を使った問題の例については、疑似言語のページを参照ください。
リスト
リストは配列と似ていますが、仕組みが異なります。
混在しないよう、一緒に覚えるようにしましょう。
リストとは
リストとは、データと次のデータの位置（ポインタ）を持つデータ構造です。
ポインタとは、データの場所を示す情報です。
各データはポインタによって順番につながっており、このつながりをたどることでデータを管理します。
配列のようにデータを連続して格納する必要がないため、途中への追加や削除を効率よく行えることが特徴です。
リストの特徴
リストには次の特徴があります。
- データをポインタでつないで管理する
- データの追加や削除が容易
- データを連続したメモリに格納する必要がない
リストは次のデメリットもあります。
- 先頭から順番にたどるため、目的のデータを探すには時間がかかる
単方向リスト
上の章の説明で出したリストは、単方向リストです。
単方向リストは、各データが「次のデータ」へのポインタだけを持つリストです。
データは先頭から末尾へ向かって順番にたどることができますが、逆方向へは移動できません。
構造がシンプルでメモリ使用量が少ないため、多くのプログラムで利用されています。
双方向リスト
双方向リストは、「前のデータ」と「次のデータ」の両方へのポインタを持つリストです。
そのため、前後どちらの方向にも移動でき、途中のデータを削除したり挿入したりする処理を効率よく行えます。
ただし、単方向リストよりも保持するポインタが増えるため、使用するメモリ容量は大きくなります。
環状リスト
環状リストは、最後のデータが先頭のデータを指すようにつながったリストです。
通常のリストでは最後のデータの次は存在しませんが、環状リストでは先頭へ戻るため、データを繰り返し順番に処理できます。
このような特徴から、順番に処理を繰り返すシステムやスケジューリングなどで利用されます。
配列とリストの違い
| 項目 | 配列 | リスト |
|---|---|---|
| アクセス | 早い | 遅い |
| 追加 | 苦手 | 得意 |
| 削除 | 苦手 | 得意 |
| メモリ上のデータ | 連続 | 連続でなくて良い |
腕試し（理解テスト）
腕試し（理解テスト）に挑戦する場合はこちらをクリック。
コメント