|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。
XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。 == 概要 == 通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。 XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。 このリストを左から右に走査するとして、現在 C を見ているとすると、前に走査した B のアドレスが分かっており、同時に C のリンクフィールドの値 (B⊕D) も分かっている。これらの情報から D のアドレスが求められ、リストの走査を続行できる。逆方向からの走査も同様である。 リスト上のある位置からどちらかの方向に走査を開始するには、連続する2つのノードのアドレスを知る必要がある。ひとつのノードのアドレスが分かっているだけでは、リスト上を移動できない。2つのノードがリスト上どういう順序で連結されているかが分からないと、どちらの方向に走査しているのか分からなくなる。 XOR連結リストは、以下のような問題を抱えている。 * 汎用的なデバッガはXOR連結リストを追うことができないので、デバッグが難しくなる。 * メモリ使用量を削減するのと引き換えにコードの複雑性が増し、コード保守が大変になる。 * 多くのガベージコレクション手法では、実際のポインタでないとうまく機能しない。 * ポインタ型のXOR演算は定義されていないことがある（例えば、C言語）ので、ポインタ型と整数型の間で型変換が必要となる。 * リスト上を走査する場合、常に1つ前のノードのアドレスを保持していないと、走査できない。 * 例えば、別の構造体にXOR連結リスト上のノードのアドレスがある場合、その構造体からノードが得られても、そのノードをリストから外す操作やそのノードの次に別のノードを挿入する操作が不可能である。例えば、使用中のプロセス制御ブロック(PCB)を対応するプロセスの終了時に使用中リストからフリーリストに繫ぎ変えるといった場合、使用中PCBリストはXOR連結リストでは構成できない。 コンピュータのメモリは増大しているため、XOR連結リストは一部の組み込みシステムのようなメモリが限られている場合以外では無用となっている。組み込みシステムでも、Unrolled linked list の方がより実用的である（キャッシュヒット率を向上させ、ランダムアクセス性能が向上するという利点もある）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「XOR連結リスト」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 XOR linked list 」があります。 スポンサード リンク
|