配列で作るリストの特徴は？連結リストとの違いで見分ける
基本情報技術者試験 平成29年度春期 午前 問4 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
データ構造の一つであるリストは，配列を用いて実現する場合と，ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで，配列を用いたリストは，配列に要素を連続して格納することによって構成し，ポインタを用いたリストは，要素から次の要素へポインタで連結することによって構成するものとする。
- ア
位置を指定して，任意のデータに直接アクセスすることができる。
- イ
並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
- ウ
任意のデータの参照は効率的ではないが，削除や挿入の操作を効率的に行える。
- エ
任意のデータを別の位置に移動する場合，隣接するデータを移動せずにできる。
会話形式の解説
講師今回は、同じリストを配列で作るか、ポインタでつないで作るかを比べる問題です。配列のリストは要素を連続した領域に順に並べる、という前提に注目してください。
受験者連続して並んでいるなら、何番目かを指定してすぐ取り出せそうです。位置を指定して直接アクセスできるという選択肢が配列の特徴だと思いました。
講師その読みで合っています。要素が連続していれば、先頭の位置と要素1個分の大きさから、何番目の要素がどこにあるかを計算で求められます。先頭から順にたどらなくても、添字、つまり要素の番号から格納位置が分かるわけです。
受験者先頭にデータを効率的に挿入できるという選択肢も、配列なら先頭がすぐ分かるので当てはまりそうな気がして迷いました。
講師先頭の位置が分かることと、そこに挿入しやすいことは別の話です。配列の先頭に新しい要素を入れるとき、既存の要素はどうなるでしょうか。
受験者先頭はもう埋まっているので、空きを作るために全部の要素を1つずつ後ろへずらす必要があります。要素が多いほど手間がかかりますね。
講師そのとおりです。ポインタのリストなら、新しい要素から今の先頭へポインタでつなぐだけで済むので、効率的に挿入できるのはそちらです。
受験者参照は効率的ではないが削除や挿入は効率的、という選択肢は、配列とは逆のことを言っているように見えます。
講師よく気付きました。配列は添字で直接参照できるので参照は得意です。一方、挿入では後ろの要素を後ろへずらし、削除では空いたところを埋めるために後ろの要素を前へ詰める必要があり、こちらは不得意です。この選択肢は、先頭から順にたどって参照し、ポインタの付け替えで挿入・削除する、ポインタのリストの説明です。
受験者隣接するデータを動かさずに別の位置へ移せるという選択肢も、ポインタを付け替えるだけで並び順を変えられる、ポインタのリスト側の特徴ということですか。
講師はい。配列では並び順が格納位置そのものなので、ある要素の位置を変えると、移動元と移動先の間にある要素をずらす必要があります。
受験者まとめると、配列は参照に強く、挿入・削除・移動には要素の移動が伴う。ポインタのリストはその逆で、参照には順にたどる手間がかかる、ということですね。
講師その対比を押さえておけば、この種の問題は判断しやすくなります。よくある引っかけは、今回のように配列とポインタのリストの特徴を入れ替えた選択肢です。選択肢を読んだら、要素の移動が必要になるか、先頭から順にたどる必要があるかを当てはめて確かめてください。
まとめ
配列で作るリストは要素を連続した領域に並べるため、先頭の位置と要素の大きさから、どの要素の格納位置も計算で求められ、位置を指定して直接アクセスできます。その反面、挿入では後ろの要素を後ろへずらし、削除では前へ詰める必要があり、先頭への挿入や要素の移動は効率がよくありません。ポインタのリストはポインタの付け替えで挿入・削除・並べ替えができますが、目的の要素までは先頭から順にたどる必要があります。「参照に強い配列」「挿入・削除に強い連結リスト」という対比で選択肢を見分けるのが要点です。
解答・解説
正解はアです
この問題のテーマ
リストを配列で作る場合とポインタで作る場合を比べ、配列で作ったリストに当てはまる特徴を選ぶ問題です。
解き方の考え方
配列のリストは要素を連続した領域に順に並べます。そのため、添字を指定すれば格納位置がすぐに分かりますが、並びの途中で要素を増やしたり減らしたりすると、後ろの要素をずらして詰め直す必要があります。この2つの性質を各選択肢に当てはめ、ポインタのリスト（連結リスト）の特徴を述べている選択肢を外していきます。
選択肢ごとの解説
- ○ア 位置を指定して，任意のデータに直接アクセスすることができる。位置を指定して直接アクセスできるという説明は、配列に当てはまります。要素が連続して並んでいるので、先頭の位置と要素1個分の大きさから、何番目の要素がどこにあるかを計算で求められます。先頭から順にたどる必要がないため、どの位置の要素にも同じ手間で到達できます。
- ×イ 並んでいるデータの先頭に任意のデータを効率的に挿入することができる。先頭への効率的な挿入という説明は、配列には当てはまりません。配列の先頭に新しい要素を入れるには、空きを作るために既存の要素をすべて1つずつ後ろへずらす必要があり、要素が多いほど手間が増えます。先頭の手前にポインタでつなぐだけで済むポインタのリストなら、効率的に挿入できます。
- ×ウ 任意のデータの参照は効率的ではないが，削除や挿入の操作を効率的に行える。参照は非効率だが削除や挿入は効率的という説明は、配列の性質と逆になっています。配列は添字で直接参照できるので参照は得意ですが、挿入や削除のたびに要素をずらす必要があり、こちらは不得意です。この説明は、先頭から順にたどって参照し、ポインタの付け替えで挿入・削除するポインタのリストの特徴です。
- ×エ 任意のデータを別の位置に移動する場合，隣接するデータを移動せずにできる。隣接するデータを動かさずに別の位置へ移せるという説明は、配列には当てはまりません。配列の並び順は格納位置そのものなので、ある要素の位置を変えると、移動元と移動先の間にある要素をずらす必要があります。前後のポインタを付け替えるだけで並び順を変えられるのは、ポインタのリストです。
POINT
- 配列は要素が連続して並ぶため、添字から格納位置を計算して任意の要素に直接アクセスできます。
- 配列の途中や先頭への挿入・削除では、ほかの要素の移動が必要になり効率がよくありません。
- ポインタのリストはポインタの付け替えだけで挿入・削除ができますが、目的の要素までは先頭から順にたどる必要があります。
- 「参照に強い配列」「挿入・削除に強い連結リスト」という対比で選択肢を見分けると判断しやすくなります。