Gap List

Magic List と同様、 pointer 1 つ分の領域だけを使って双方向リスト相当な処理を行う データ構造。 これまた Magic List と同様あまり使われていないが、 Magic List と同様 CurrentP と PreviousP の2つのポインター を使うことで実現されている。

Gap List の場合、一番最初、誰も何もしていない頃のリストは、 単方向リストそのものである。 そして、Gap List はその単方向リストの先頭からしか 手繰ることは許されない。

通常の単方向リストと何が違うのかは、次の図を見れば判る。

Middle State of GapList

そう。Gap List はリスト構造を手繰る度に、 リスト構造が指しているポインターの向きを逆転させてしまうのだ。 この様に操作することで、1つのリストを「Current を管理している」 ポイントを起点とする2つの単方向リストに直し、 それによって任意の方向に移動できることを可能にしている。

例えばエディターなどの場合、 カーソルの存在する行を Current として管理すると、 カーソルを上に移動するのも、下に移動するのも、 同じ操作になる (CurrentP と PreviousP を交換すれば、だが)。


Gap List も Magic List と同様数多くの弱点を持っており、 そのために広く使われることはなかった。

弱点の最大のものは、
「一度に複数の current を持てない」
という点だ。 current が複数存在すると、 ある current からみて「次」にあるべき要素は、 別の current から見ると「前」になる。 この場合、要素が指すべきポイントは「次」なのか「前」なのか…。

また、この方法は移動の度にポインタの書き換えが発生する。 旧式の、キャッシュなど必要としなかった時代の計算機ならばともかく、 昨今の計算機では局所的な書き換えが大量に発生すると、 動作速度が著しく落ちる。