双方向リストクラス std::list とは std::list とは C++ で標準に使用できる便利な双方向リストクラスでござるぞ。 「双方向リスト」とは、要素を格納するノードが前後のノードへのポインタを持ち、どの位置への挿入・削除でも O(1) と高速に処理できるコンテナクラスだぞ。 ※ 「コンテナクラス」とは、単一タイプ・データ構造の複数のデータを取り扱うためのクラスのことだぞ std::list と対比されるのは std::vector である。 vector は末尾への挿入・削除は O(1) と高速だが、それ以外の位置への挿入・削除は O(N) で、データ数に比例した処理時間を要してしまう。 その半面、どの位置のデータへも O(1) と高速にアクセス(参照・代入)することができる。 任意の位置へのアクセスをランダム・アクセスと呼ぶので、vector はランダム・アクセスが O(1
![C++ 双方向リストクラス std::list 入門](https://cdn-ak-scissors.b.st-hatena.com/image/square/de1bd942ad80cf83ce4fc9ab91c80f980efd3698/height=288;version=1;width=512/http%3A%2F%2Fvivi.dyndns.org%2Ftech%2Fcpp%2Flist-struct.png)