Data & Algorithm 今回のお題：
『ギャップリスト』

●概要

ギャップリストも、双方向リストを単方向リストと同じメモリ使用量で実現する方法の 1 つです。 p から前は 1 つ前を、n 以降は 1 つ先を指しています。

(a) Gap-List
図 (a): ギャップリスト

マジックリストと比較しての長所・短所は以下の通りです。たぶん。

・長所
ビット演算などの面倒な処理がいらないため、分かり易く、比較的高速。
・短所
リストが途中で切れているため、基本的に、1 つのリストを 2 つ以上のポインタで指すことができない。

●実装

構造体はマジックリストと変わらず単方向リストと同じやつです。(当たり前) アクセスする方法も、同じように n と n-1 (以下 p とする) のアドレスを常にとっておいて、 

/* １つ進む */
tmp = n->next;
n->next = p;
p = n;
n = tmp;
/* 向きを逆にする */
tmp = p;
p = n;
n = tmp;

とすればOKです。ややっこしい演算とかが無いぶん分かり易いと思います。

あと、マジックリストと同じで、何もしないと向きが判らなくなってしまうので、 向きを表す変数を用意しておきましょう。

●サンプル

マジックリストのソースを一寸弄って、サンプルを作ってみました。 基本的には、マジックリストのと変わりません。 追加・削除はだいぶすっきりしました。
C++で書いてみたサンプル (download)

●備考

今回もbitのパクりです。次回は「固定小数点」か「連想配列」をやろうと思っています。
でも、固定小数点ってこの間チャーパーさんが説明してた奴そのままになりそう……。 頑張ってネタをひねり出さねば。

# ……固定小数点も連想配列もアルゴリズムじゃなくってデータ型だ(汗

戻る