Data & Algorithm 今回のお題:
『マジックリスト』

●概要

マジックリストは、双方向リストを、 単方向リストと同じメモリ使用量で実現する方法の 1 つです。

図 (a): マジックリスト

まぁ、ありがちと言えばありがちなんですが、XOR (排他的論理和) を上手く使って、 2 つのデータを 1 つにまとめてあります。 ( A XOR B ) XOR B = A という、XORの性質を利用した方法です。 ＃「リストって何？」という方は、ほかのサイトや本などを参考にして下さい。 そこまで説明する気力がありません。悪しからず。

●実装

データ型の定義には構造体を用います。

struct MagicList {
    int                 data;
    struct MagicList    *next;
};

実際にアクセスするには、n と n-1 (以下 p とする) のアドレスを常にとっておいて、

/* 1 つ進む */
tmp = n;
n = p ^ n->next;
p = tmp;

/* 向きを逆にする */
p = p ^ n->next;

とすればいいわけです。( ^ は XOR の意味 )

実際には、ポインタ同士でbit演算をしているので、 Cではこのままでは通りません。int型にキャストしてやりましょう。
あと、右へ進むのも左へ進むのも同じ動作で済んでしまうので、 下手をすると現在の向きが判らなくなってしまいます。 そのため、向きを表す変数を用意する必要があります。

●サンプル

勉強を兼ねて、こんな感じのモノを作ってみました。 問題ありまくりの上、読みづらいと思いますが、参考になれば幸いです。 「こんなソースダメダメ〜」とかありましたら、バシバシご指導お願いします〜。
C++ で書いてみたサンプル (download)

●備考

今回は bit の連載で取り上げられていたものを実際に組んでみました。 よってアイデアの絞り出しも何も無い上に、「n」とか「p」とかまで bit と同じです。ずびばぜ〜ん。(ぉ