線形リスト

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

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

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

演算子をオペランドの後に置く数式の表記法（後置記法）。括弧が不要でスタックを用いて容易に評価でき、コンパイラの中間コード生成や電卓の実装に利用される。例：「3 4 + 5 *」は(3+4)*5を表す。

同一型のデータを連続したメモリ領域に格納するデータ構造。インデックスによるO(1)のランダムアクセスが可能。静的配列はサイズ固定、動的配列は必要に応じてサイズを変更できる。多次元配列で行列などを表現。

LIFO（Last In First Out）方式でデータの出し入れを行うデータ構造。プッシュ（追加）とポップ（取出し）の2つの操作を持つ。関数呼出しの管理、式の評価、Undo機能の実装などに利用される。

FIFO（First In First Out）方式でデータの出し入れを行うデータ構造。エンキュー（追加）とデキュー（取出し）の操作を持つ。タスクスケジューリング、バッファ管理、幅優先探索に利用される。優先度付きキューでは優先度の高い要素から取り出す。

各ノードが最大2つの子ノードを持つ木構造。完全2分木は最下段以外の全階層が埋まった構造。2分探索木は左の子が親より小さく右の子が親より大きい性質を持ち、探索・挿入・削除をO(log n)で実行可能。

各ノードの左右部分木の高さの差が1以下に保たれる平衡2分探索木。挿入・削除時に回転操作（単回転・二重回転）でバランスを維持し、最悪ケースでもO(log n)の探索時間を保証する。