【応用情報技術者試験】配列とリスト（ポインタ）

配列とは

配列は、下のように同じデータ型の要素を番号順に並べたものを表します。

また、この番号は添字（インデックス）と呼ばれます。

添字は0スタートの場合と1スタートの場合がありますが、C言語を含む多くの言語は0スタートです。

配列の場合、指定したい要素を添字で指定します。

例えば、上の図の配列で2番目を指定すると97の要素を得ることができます。

また、添字を数字ではなく、2i + j のような数式で指定することもできます。

例えば、i = 3, j = 2 のときに 2i + j 番目を指定すると、8番目を計算してくれます。

また配列を2重に組み合わせて2次元配列をつくることができます。

2次元配列のイメージは、下のような行と列からできた表です。

基本的に2次元配列 a[i][j] の1つ目の添字 i が行、2つ目の添字 j が列を表します。

他に2次元配列で表現できるものとして、行列やビンゴカードなどがあります。

リストは、「要素」と「次のデータを指し示すポインタ（場所）」の2つからなるデータが数珠のようにつながっているデータ構造です。

例えば20番地のアドレスのデータには、要素である「75」と「次のデータのポインタ（40番地）」が入っています。

リストの場合、要素を探すために先頭からポインタをたどる必要があります。

例えば、上の図のリストで97の要素がある60番地のデータを探したい場合、「20番地→40番地→60番地」のように順番にたどることで目的の60番地のデータを見つけることができます。

リストには次のデータのポインタだけを持つ単方向リスト以外にも、前のデータのポインタも持つ双方向リスト、末尾と先頭のデータを連結させることで環状線のようにぐるぐるできる環状リストがあります。

単方向リスト以外にもこんなリストがあるんだな～ってことがわかればOKです。

なお、単にリストとだけ書いてあった場合は「単方向リスト」を表していると思ってください。

配列とリストはともに同じ型のデータですが、どちらも一長一短で使い分けられます。

データのアクセスの場合、配列の方が優れています。

配列は、添字（番号、インデックス）で要素を指定できるのでワンステップで要素を指定することができます。

一方リストは先頭からリストをたどっていくことでしか要素を探せないため、最大で要素数ステップの時間がかかってしまいます。

データの追加、削除はリストが優れています。

配列は、データを追加 or 削除するために、後ろにあるデータを下のようにずらす必要があります。そのため、ずらすデータの数だけ余計に処理時間がかかります。

配列の追加

配列の削除

リストでは、次のデータを指し示すポインタを下のように少し書き換えるだけでデータの追加、削除を行うことができます。そのため、後ろのデータに関係なく数ステップで処理ができます。

リストの追加

リストTの削除

格納領域も、リストの方が優れています。

配列の場合、最初に int data[100]; のように格納領域を指定するため、使わない無駄な領域が発生してしまいます。

一方リストはポインタだけで前後関係を表しているので、動的に拡張領域を変更することができ、無駄な領域が発生しません。

頻繁にデータにアクセスするようであれば配列を、頻繁にデータを書き換える場合であれば連結リストのように使い分けると効率がよくなります。

念のため、データのアクセス、データの書き換えをオーダー表記で表したものを下に示しておきます。

操作内容	配列	リスト
データアクセス	O(1)	O(n)
データ挿入／削除	O(n)	O(1)