線形リスト

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

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

各要素がデータと次の要素を指すポインタを持ち、ポインタでつながったデータ構造で、線形リストともいう。ポインタを付け替えるだけで要素の挿入や削除ができるが、特定の要素を参照するには先頭から順にたどる必要がある。単方向リスト、双方向リスト、環状リストがある。

同じ型のデータを連続したメモリ領域に格納するデータ構造。添字（インデックス）を用いて各要素に直接アクセスできるため、参照がO(1)で高速。挿入・削除はデータの移動が必要なためO(n)。

各要素が前方と後方の両方へのポインタを持つリスト構造。前後どちらの方向にも辿れるため、要素の削除が単方向リストより効率的。ただしポインタが2つ必要なためメモリ使用量が増える。

データの挿入と取り出しが同じ端（先頭）から行われるデータ構造。LIFO（Last In, First Out：後入れ先出し）の原則に従う。関数の呼び出し管理、括弧の対応チェック、逆ポーランド記法の計算に使用される。

データの挿入を末尾、取り出しを先頭から行うデータ構造。FIFO（First In, First Out：先入れ先出し）の原則に従う。タスクの待ち行列管理やプリンタのジョブ管理に使用される。

各ノードが最大2つの子ノードを持つ木構造。左の子と右の子に分かれる。2分探索木、ヒープ、式木など多くの応用がある。探索や整列の効率的な実装に使われる。

左の子ノードの値が親より小さく、右の子ノードの値が親より大きいという条件を満たす2分木。探索・挿入・削除の平均計算量がO(log n)で効率的。バランスが崩れるとO(n)に悪化する。