連結リスト

各要素がデータとポインタ（次の要素への参照）を持ち、鎖状に連結されたデータ構造。要素の挿入・削除がポインタの変更のみで可能だが、特定要素の参照には先頭から辿る必要がある。

各要素がデータとポインタ（次の要素への参照）を持つデータ構造。単方向リスト、双方向リスト、環状リストがある。挿入・削除がO(1)で可能だが、ランダムアクセスにはO(n)必要。メモリの動的確保に適する。

データとほかの要素を指すポインタの組を要素とし、ポインタをたどってつないだリストで、線形リストともいう。次の要素だけを指す単方向リスト、前後を指す双方向リスト、末尾が先頭を指す環状リストがある。位置が分かっていれば要素の挿入・削除をポインタの付替えだけでO(1)で行えるが、k番目の要素を参照するには先頭からたどるのでO(n)かかる。

連結リストの最後の要素のポインタが先頭の要素を指し、要素が輪のようにつながったリスト。どの要素からでもすべての要素をたどることができ、順番に繰り返し処理する場合などに使う。

各要素が次の要素を指すポインタを1つだけ持つ線形リスト。先頭から順にたどることしかできず、直前の要素へは戻れない。挿入・削除はポインタの付け替えだけで済むが、目的の要素の探索には時間がかかる。

実行中に要素を追加・削除して大きさを変えられる配列。確保した領域が足りなくなると、より大きな領域（例えば2倍）を確保して要素を写し替えるので、末尾への追加は平均してO(1)で行え（償却計算量）、添字によるO(1)のアクセスも保てる。PythonのリストやJavaのArrayListが当たる。