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