双方向リストを実装するには一般に pointer 2つ分のメモリ領域が必要である。 このため、双方向リストの任意のポイントを知ると、 そこからリストの前後双方向に移動することができる。 しかし、 このようなリストを作るには本当に「常に」 pointer 2つ分必要な わけではない。
「リスト上の連続した2つの要素」が得られるとしよう。 この場合、その 2つの要素の順序も判っていて、 どちらからどちらの方向へ移動する、とはどう言うことなのか、 ごと判っているとしよう。 この場合、リストの要素が必要とする「双方向リスト」を作るために 必要なメモリは pointer 1つ分ですむ。 このように作られているリストを Magic List と言う。
Magic List では pointer 1つ分の所に、 自分の前の要素のアドレスと、自分の次の要素のアドレスを bitwize xor した結果を Pointers として登録しておく
仮に、今 2つのポインターを持っていて、
Magic List の1つの要素と、その「前の」要素のアドレスを保持しているとしよう。
この場合 Magic List では
「NextP = CurrentP->Pointers xor PreviousP」
という計算で、「次の要素の位置」を求めることができる。
当然、逆向きもまたしかりである。
もし、CurrentP がリストの末端の場合 NextP は NULL になる。
また、PreviousP が NULL の場合、CurrentP->Pointers は
PreviousP xor NextP
が常に成立しているはずなので、NextP は常に適切に処理されるはずだ。
このメモリを節約するという意味においてとても有益なリスト構造には いくつかの弱点があった。 このため、このアルゴリズムが今日、一般的に使われることはありません。
弱点のなかでも最大のものは、
「CurrentP と PreviousP をつねに正しく知る必要がある」
という点です。
リンクリストを端から手繰るのであればともかく、
いきなりリンクリストのど真ん中の要素を与えられる場合、
その前後の要素がどこにあるのか、
同時に獲得できることは一般にはあり得ません。
その情報を保持する、と言う事はリストの性質を知っている、
と言う事であり、そんなものを覚える必要があるのでは、
単にポインターのありかを移動したに過ぎないからです。
この場合は双方向リストを使った方がはるかに有利になります。
2つ目の弱点は、
CurrentP と PreviousP のどちらかを間違えた場合の、破綻状況です。
CurrentP と PreviousP が実は隣接しておらず、
なおかつ CurrentP と PreviousP が共にリンクリストの要素だった場合、
リンクリストを適切に手繰ることができなくなります。
が、この様な状態はマルチスレッドなど、
同時に複数のプログラムがリンクリストを操作する場合、
容易に起ります。
仮に「Link Pointer 変更」とそのメモリへの反映は
きちんと排他制御されていたとして、
なおかつリンクを手繰るためのポインター参照は常にメモリを
相手にしていたとするならば、
通常の双方向リストであれば一応リストを適切に手繰ることはできます。
しかし Magic List の場合、
それまで「隣接している」と思っていた2要素の間に新しい要素を
挿入されると、
意味不明なアドレスを生成するようになってしまい、
適切な操作が不可能になります。