Magic List と同様、 pointer 1 つ分の領域だけを使って双方向リスト相当な処理を行う データ構造。 これまた Magic List と同様あまり使われていないが、 Magic List と同様 CurrentP と PreviousP の２つのポインター を使うことで実現されている。
Gap List の場合、一番最初、誰も何もしていない頃のリストは、 単方向リストそのものである。 そして、Gap List はその単方向リストの先頭からしか 手繰ることは許されない。
通常の単方向リストと何が違うのかは、次の図を見れば判る。
そう。Gap List はリスト構造を手繰る度に、 リスト構造が指しているポインターの向きを逆転させてしまうのだ。 この様に操作することで、1つのリストを「Current を管理している」 ポイントを起点とする2つの単方向リストに直し、 それによって任意の方向に移動できることを可能にしている。
例えばエディターなどの場合、 カーソルの存在する行を Current として管理すると、 カーソルを上に移動するのも、下に移動するのも、 同じ操作になる (CurrentP と PreviousP を交換すれば、だが)。
Gap List も Magic List と同様数多くの弱点を持っており、 そのために広く使われることはなかった。
弱点の最大のものは、
「一度に複数の current を持てない」
という点だ。
current が複数存在すると、
ある current からみて「次」にあるべき要素は、
別の current から見ると「前」になる。
この場合、要素が指すべきポイントは「次」なのか「前」なのか…。
また、この方法は移動の度にポインタの書き換えが発生する。 旧式の、キャッシュなど必要としなかった時代の計算機ならばともかく、 昨今の計算機では局所的な書き換えが大量に発生すると、 動作速度が著しく落ちる。