取り出す順番で構造を選ぶ

1次の要素への道しるべで並びを作る

リストは、要素に順序があるデータの並びです。連結リストでは、各要素に「次の要素はどこか」を示す参照を持たせます。参照は、別のデータをたどるための情報です。配列のように、要素を連続した位置に並べる仕組みとは区別します。

例えばA→B→Cという連結リストで、AとBの間にXを入れるなら、まずXの次をBへつなぎ、次にAの次をXへつなぎます。並びはA→X→B→Cになり、Bの次がCであることは変わりません。ここで矢印は、時間の経過ではなく「次の要素への参照」です。

途中への挿入は参照のつなぎ替えで行えますが、挿入場所を見つける探索は別に必要です。何でも配列より高速と考えず、どんな操作をよく行うかで選びます。

2キューは先に来たものから

キューは先入れ先出し、FIFO（First In, First Out）で取り出す構造です。A、B、Cの順に追加すれば取り出す順もA、B、Cです。印刷要求を到着順に処理する場面に使います。

末尾に追加し先頭から取り出す、という操作を守ることが特徴です。優先度による処理を行う場合は、通常の到着順キューと違う規則を用意します。

3スタックは最後に入れたものから

スタックは後入れ先出し、LIFO（Last In, First Out）で取り出します。A、B、Cの順に積むと、最初に取り出すのはCです。追加をpush、取り出しをpopと呼びます。

直前の操作から取り消す処理や、関数を呼び出した後に戻る場所の管理で利用できます。空の状態から取り出すことはできないので、空かどうかの確認も必要です。

4木は親子で階層を表す

木構造は根（ルート）から親子関係で枝分かれする構造です。節（ノード）のうち子をもたないものを葉と呼び、2分木では一つの節がもつ子は高々二つです。

フォルダ階層では子をもつ中間の節がディレクトリ、葉はファイル又は空ディレクトリです。空フォルダも子がないので葉になれます。「節」という語は広義では葉を含む全ノード、問題によっては葉と対比した中間ノードを指すので文脈を読みます。