今回は、配列とリストについてそれぞれの使い方と、それに対する演習問題をご紹介していこうと思います。
インプットも、アウトプットも同時に試せてしまうため、本記事を通して配列・リストの知識を定着させてしまいましょう。
また、本記事では大半の問題を基本情報技術者試験の過去問から持ってきているので、試験対策にもなります。
ぜひ最後まで見ていってください。
この記事でわかること
- 配列について
- リストの種類とそれぞれの使い方
- 配列・リストに関する演習問題
目次
用語解説
では、まずは配列やリストなどの用語についてわかりやすいように解説していきます。
配列とは？
配列とは、同じデータ型の複数の変数を連続して配置するようなデータ構造のことです。
各データのことは、その配列の『要素』と呼んだりするので覚えておきましょう。
例えば、下の図でいうと『Orange』は配列Cの1番目の要素といった感じですね。
また、各データの中身が見たい場合は『配列名[番号]』というようにしてアクセスします。
ちなみに、ここでいう番号というのは、配列の左から数えて何番目に位置しているかを表す数値ですね。
リストとは？
リストは、複数の要素を連結させたデータ構造で、一つの要素につき『データ部』と『ポインタ部』を一つずつ持っています。
言葉のみだと少しイメージが湧かないと思うので、少し図を使って確認していきましょう。
このような形です。
配列と異なり、ポインタで要素同士がつながっているのが特徴的ですね。
様々なリスト
実は、先ほど示したリストは『単方向リスト』と呼ばれており、リストには単方向リストの他にも以下のようなものがあります。
単方向リストでは、要素をたどるときに片方向にしかたどれなかったのですが、『双方向リスト』『環状リスト』では前の要素に戻ることが出来るので、単方向リストの時よりもできることが増えます。
覚えておきましょう。
【頻出】配列とリストの違い
配列とリストは、複数のデータを扱うといった点から少し仕組みが似ているのでよく比較されて、試験に出題されます。
そのため、配列とリストの違いを具体的に抑えておく必要があります。
基本的に抑えるべき違いは以下の通りです。
配列とリストの違い
- データ探索（データアクセス）は配列の方が速い
- データの追加・削除はリストの方が速い
- 格納領域はリストの方が優れている
以下でそれぞれについて簡単に理由を説明します。
①：データ探索（データアクセス）は配列の方が速い
配列や、リストはたくさんのデータから構成されるデータ型になっているので、今見たいデータをすぐに探せるかどうかは結構重要な要素になっており、この点では配列が優れています。
配列では、指定のデータにアクセスするのに『配列名[番号]』という風に番号を指定するだけでよいので、例えば前から数えて100番目のデータを取り出したい！といった場合にも、『配列名[100]』と指定するだけでOKです。
しかし、リストの場合は前から100番目のデータを取り出したい！となった場合は、先頭の要素から矢印をたどって順に探さないといけません。
そのため、時間がかかってしまいます。
配列は瞬時に要素を指定できるのに対し、リストは要素を探す際に必ず前から探さなければならないので、データアクセスが遅いんですね。
②データの追加・削除はリストの方が速い
指定のデータを追加・削除するといった動作に関しては配列よりもリストの方が速いです。
配列では、要素を100番目に追加しようと思ったら、もともと100番目にあった要素はひとつ後ろにずれなければなりません。
そうなると、もちろんもともと101番目にあった要素は102番目に、102番目にあった要素は103番目にずれる必要があるため、要素を一つ追加するだけなのにいくつものデータを動かさなければならないんです。
これは削除の際も同じです。
では、リストの場合はどうでしょうか。
リストの場合は言葉のみですと少しイメージが湧きにくいと思いますので、図を用いて説明していきます。
このように、リストの場合は要素の追加や削除を行う際に、矢印の向きを変更するだけでOKなんです。
つまり、中途半端な位置に要素を追加しても、わざわざ後ろの要素まで動かす必要がないということです。
よって、リストの方が要素の追加・削除は速いといえます。
③格納領域はリストの方が優れている
配列は用意する際に、『100個分のデータが入る配列を用意しますね』と宣言しなくてはならないため、どうしても途中で使わない領域が発生してしまいます。
しかし、リストの場合は矢印を追加するだけでいつでも要素数を変更することが出来ます。
なので、使わない領域が発生してしまうといった現象は起きないんですね。
よって格納領域に関してもリストの方が優れていると考えられるでしょう。
演習問題
続いては演習問題です。
インプットした知識を演習を通じてアウトプットして、知識の定着を図りましょう。
演習問題①
リストは，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。
[基本情報技術者平成25年秋期 午前問6]
ア. リストにある実際の要素数にかかわらず，リストの最大長に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
イ. リストにある実際の要素数にかかわらず，リストへの挿入と削除は一定時間で行うことができる。
ウ. リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくので，要素数に比例した時間が必要となる。
エ. リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
演習問題②
データ構造の一つであるリストは、配列を用いて実現する場合と、ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで、配列を用いたリストは、配列に要素を連続して格納することによって構成し、ポインタを用いたリストは、要素から次の要素へポインタで連結することによって構成するものとする。
[基本情報技術者平成24年春期 午前問4]
ア. 位置を指定して、任意のデータに直接アクセスすることができる。
イ. 並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
ウ. 任意のデータの参照は効率的ではないが、削除や挿入の操作を効率的に行える。
エ. 任意のデータを別の位置に移動する場合、隣接するデータを移動せずにできる。
演習問題③
リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭(1番目)の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。
[基本情報技術者平成30年春期 午前問6]
ア. 3
イ. 5
ウ. 7
エ. 8
演習問題④
多数のデータが単方向リスト構造で格納されている。このリスト構造には，先頭ポインタとは別に，末尾のデータを指し示す末尾ポインタがある。次の操作のうち，ポインタを参照する回数が最も多いものはどれか。
[基本情報技術者平成24年春期 午前問7]
ア. リストの先頭にデータを挿入する。
イ. リストの先頭のデータを削除する。
ウ. リストの末尾にデータを挿入する。
エ. リストの末尾のデータを削除する。
演習問題⑤
配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。
[基本情報技術者平成21年春期 午前問6]
ア. 要素を更新する場合，ポインタを順番にたどるだけなので，処理時間は短い。
イ. 要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するので，処理時間は長い。
ウ. 要素を参照する場合，ランダムにアクセスできるので，処理時間は短い。
エ. 要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。
まとめ
今回は、配列とリストについてそれぞれの特徴と違いを解説した後、それらに関する演習問題まで紹介してきましたがいかがだったでしょうか。
配列とリストの違いを簡単にまとめると、
- データのアクセス・更新は配列が速い
- データの追加・削除はリストが速い
- データの格納効率はリストのほうが良い
となります。
よく覚えておきましょう。