魔法のリスト

プログラミングの足場は「データ構造」(data structure)と「アルゴリズム」 (algorithm)ですが、このデータ構造として最も有効なものの一つが「リスト」 (list)ではないかと思います。これほどシンプルで応用範囲の広いものはありませ ん。

このリスト構造は、データを記憶するメモリの断片(cell)を線状につないだもので、 双方向の場合は、普通、次のように、行と戻りの二つのポインタ・フィールドを必 要とします。

  struct list {
        /* data */
        struct list *prev;
        struct list *next;
  };
つまり、次のような構造です。
     +-----+      +-----+      +-----+   
  .. | next|----->| next|----->| next| ..
     |prev |<-----|prev |<-----|prev |
     +-----+      +-----+      +-----+
さて、この隣のセルのアドレスを得るためのポインタ・フィールドである next と prev はデータ構造の実現にのみ必要で、格納すべき情報にとってはオーバーヘッ ドですから、できることなら少しでも小さくしたいわけですが、
  struct list {
	/* data */
	struct list *ptr;
  };
だけで双方向リストを実現することができるでしょうか。つまり、次のような構造 は実現可能でしょうか。
     +-----+      +-----+      +-----+
  .. | ptr |--><--| ptr |--><--| ptr | ..
     +-----+      +-----+      +-----+

さあ、ここで答えを見る前に、少し考えてみてください。せっかくの楽しみを棒に ふることはありません。

続く ..

平林浩一, 1998