連結リスト

Linked List

れんけつりすと

各要素がデータとポインタ（次の要素への参照）を持つデータ構造。単方向リスト、双方向リスト、環状リストがある。挿入・削除がO(1)で可能だが、ランダムアクセスには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)の探索時間を保証する。