takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

【就プロ】配列とリスト

はじめに

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

配列

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

f:id:takahiro_itazuri:20180111154648p:plain

利点

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

欠点

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

リスト

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

また次のデータのポインタだけでなく、前のデータのポインタも格納したものを「双方向リスト」と呼びます。

f:id:takahiro_itazuri:20180111155519p:plain

利点

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

欠点

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

C++

配列

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

リスト

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