この記事では配列とリストについてIT初心者にも分かりやすく解説します。
配列
- 変数はプログラム内で数字や文字列を入れる箱
- 配列は複数の変数を1つにまとめたもので、長さを指定して定義する必要がある(長さが固定)、添字でデータ位置を示すので直接データにアクセスできる特徴がある
- 配列はデータの挿入と削除が苦手
リスト
- リストも複数の変数を1つにまとめたものだが、配列と違い、ポインタを使って次のデータの場所を指定する
- リストはデータにアクセスするとき、前から順番に辿っていく必要がある
- リストはデータの挿入と削除が得意
応用情報では配列とリストに関する問題が出ます。是非最後までご覧ください。
変数と配列
変数とはプログラミングで数字や文字列を入れておく箱のようなものです。
例えば、ユーザに年齢を入力させて大人料金なのか子供料金なのか、メッセージを表示するプログラムの例では、「age」が年齢を入れる変数になっています。
配列は、複数個の変数を1つにまとめたものです。
配列には同じサイズの変数が入りますが、それらを区別するのが添字です。配列内のデータにアクセスする時は、「2番目のデータを取得」のように添字を指定します。
また、配列は長さを指定して定義するため、途中にデータを挿入したり削除することが苦手です。（完全に出来ないわけではありません）
実際に配列がプログラミングで使われている所を見てみましょう。
下の例では、5人分の点数をscores()という配列に入れています。
ポインタを使うリスト
リストは配列と同じように複数の変数を1つにまとめて管理します。
リストはポインタを使って次のデータがどこにあるのかを指定します。
リストは最初のデータからポインタを辿ることでデータにアクセスします。
リストはデータの追加や削除が簡単に行えます。
リストはポインタを最初から順番に辿らないと、欲しいデータにアクセス出来ません。
一方、配列は添字を指定することで直接データにアクセス出来ます。
リストはポインタの持ち方によって分類されます。ここでは単方向リストと双方向リストを紹介します。
単方向リスト
単方向リストは一方通行で次のデータを指定するリストです。
最も基本的な構造のリストですね。
双方向リスト
双方向リストは次のデータのポインタと、前のデータのポインタの両方を持つので、前後どちらにも辿ることが出来ます。
応用情報技術者試験での出題例
令和5年度秋期問5
応用情報技術者
午前試験 令和5年度秋期問5
双方向リストを三つの一次元配列elem[i]，next[i]，prev[i]の組で実現する。双方向リストが図の状態のとき，要素Dの次に要素Cを挿入した後のnext[6]，prev[6]の値の組合せはどれか。ここで，双方向リストは次のように表現する。
・双方向リストの要素は，elem[i]に値，next[i]に次の要素の要素番号，prev[i]に前の要素の要素番号を設定
・双方向リストの先頭，末尾の要素番号は，それぞれ変数Head，Tailに設定
・next[i]，prev[i]の値が0である要素は，それぞれ双方向リストの末尾，先頭を表す。
・双方向リストへの要素の追加は，一次元配列の末尾に追加
正解は”ウ”
問題で与えられたリストを整理してみましょう。
まず、Headの要素番号が1なので先頭はA、Tailの要素番号が2なので最後はFです。
Aの次の要素番号(next
)は4なので、Aの次はBですね。と言う感じでリストを繋げると次のようになります。
このリストのDの後にCを挿入したいので、next[6]はEの要素番号である5を、
prev[6]はDの要素番号である3を指定します。
よって、答えはウです。
令和4年度春期問5
応用情報技術者
午前試験 令和4年度春期問5
リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。
ア リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
イ リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
ウ リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
エ リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。
正解は”ア”
ア 配列の場合は長さを指定して定義するので、全ての要素を使っていなくても定義した長さ分の領域を確保する必要があります。よって正しいです。
イ ポインタは先頭からデータを辿る必要があります。一方、配列は添字を指定してデータにアクセスします。イの説明はポインタの説明なので誤りです。
ウ 次の領域の場所を示す必要があるのはポインタです。よって誤りです。
エ ポインタの場合はどこに要素を追加するにしても同じように追加します。一方、配列は追加する箇所の後ろにあるデータを全て後ろにずらす必要があります。なので、ずらすデータの数が多いと時間が長くなります。よってエはポインタの説明なので誤りです。
