単方向連結リスト

ノードとは、値を保持するフィールド $\mathrm{value}$ と、別のノードへの参照または $\mathrm{nil}$ を保持するフィールド $\mathrm{next}$ からなる区画をいう。ノード $p_0, p_1, \ldots, p_{n-1}$ が

を満たすとき、この列を単方向連結リストといい、先頭ノードへの参照 $\mathrm{head} = p_0$ によってリスト全体を表す。空のリストは $\mathrm{head} = \mathrm{nil}$ で表す。各ノードが $\mathrm{prev}$ フィールドも持ち $p_{j+1}.\mathrm{prev} = p_j$ を満たすものを双方向連結リストという。