【就プロ】配列とリスト

はじめに

線形データ構造の中の最も簡単な配列とリストについて説明します。

配列

配列はメモリ上の連続した領域に順番にデータを格納する方法で、以下のようになります。

利点

• ランダムアクセスが定数時間$O(1)$で行える

欠点

• 挿入・削除には最悪計算時間$O(n)$が必要である

リスト

リストは挿入・削除の速度を向上させるために作られました。
配列とは異なり、データ本体と次の要素へのポインタをセットにして保存しておく方法で、以下のようになります。
一番最後の要素のポインタにはヌルポインタを格納しておきます。

このように特に次の要素のポインタの情報のみを追加で持ったデータ構造を「単方向連結リスト（Singly Linked List）」と呼びます。
また次の要素へのポインタだけでなく、前の要素へのポインタも格納したものを「双方向連結リスト（Doubly Linked List）」と呼びます。

利点

• 挿入・削除が定数時間$O(1)$で行える

欠点

• ランダムアクセスには最悪計算時間$O(n)$が必要である

C++

配列

固定長（追加・削除をしない）の配列はデフォルトで使用できます。
可変長の配列については、動的配列クラスvectorがコンテナクラスに用意されています。

リスト

リストについては、単方向クラスforward_listと双方向リストクラスlistがコンテナクラスに用意されています。