プログラミングの足場は「データ構造」(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