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

配列と連結リストは、順序を持つデータを扱う代表的な構造です。添字で直接読むか、リンクをたどるか。追加・削除する場所が分かっているか。この二つを分けて比べると、計算量を理解しやすくなります。

配列とは

ここでは、同じ大きさの要素を連続した領域に並べる基本的な配列を考えます。要素を指定する番号を添字（インデックス）と呼びます。開始番号は言語や問題の定義で確認します。

添字	0	1	2	3
値	75	12	97	30

0始まりならa[1]は「2番目」の12、a[2]は「3番目」の97です。「添字2」と「2番目」を混同しないようにしましょう。要素の大きさが一定なら、先頭位置と添字から位置を計算できます。

i=3、j=2のとき、式2*i+jは8です。a[2*i+j]は添字8の要素で、0始まりなら9番目です。添字8が範囲内にあるかも確認します。

a[i][j]は、表の例ではiを行、jを列として読めます。0始まりならa[1][2]は2行目・3列目の要素です。添字の範囲、格納順、配列の実装は言語や問題の前提で確かめます。

各ノードが値と次のノードへのリンクを持つ構造です。リンクはアドレスや参照、配列上の番号などで表現できます。必ずしも物理的に隣り合う領域に並ぶ必要はありません。

先頭 → [75 | 次へ] → [12 | 次へ] → [97 | 終端]

先頭から3番目を調べるなら、先頭→次→次とたどります。すでに目的のノードへの参照を持っている場合と、位置を探す場合は区別します。

「リスト」は抽象的なデータ型や、言語固有のコンテナ名を指す場合もあります。単にリストと書かれていたら必ず単方向の連結リスト、と決め付けないようにします。

配列の添字アクセスはO(1)です。ただし未整列の配列から値を線形探索するなら最悪O(n)です。連結リストで先頭からi番目へ進む操作は最大O(n)になります。nは要素数です。

配列の途中へ順序を保って挿入する場合、後続の要素をずらすため最悪O(n)です。単方向リストは、挿入位置の直前ノードへの参照が分かっていれば、リンクの付替え自体はO(1)です。削除でも、対象の直前ノードが必要になります。先に位置を探すなら、その探索時間を加えます。

操作・前提	配列	単方向の連結リスト
先頭からi番目へアクセス	O(1)	最悪O(n)
未整列データから値を探す	最悪O(n)	最悪O(n)
途中へ順序を保って挿入	最悪O(n)	直前ノードが既知なら付替えO(1)。探索込みなら最悪O(n)
途中の要素を順序を保って削除	最悪O(n)	対象と直前ノードが既知なら付替えO(1)。探索込みなら最悪O(n)