XOR linked listとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > XOR linked listの意味・解説 

XOR連結リスト

(XOR linked list から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/12/12 22:35 UTC 版)

XOR連結リスト: XOR linked list)は、プログラミングにおけるデータ構造の一種。ビット毎排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。

概要

通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。

  ...  A       B         C         D         E  ...
           –>  next –>  next  –>  next  –>
           <–  prev <–  prev  <–  prev  <–

XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。

  ...  A        B         C         D         E  ...
          <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

このリストを左から右に走査するとして、現在 C を見ているとすると、前に走査した B のアドレスが分かっており、同時に C のリンクフィールドの値 (B⊕D) も分かっている。これらの情報から D のアドレスが求められ、リストの走査を続行できる。逆方向からの走査も同様である。

リスト上のある位置からどちらかの方向に走査を開始するには、連続する2つのノードのアドレスを知る必要がある。ひとつのノードのアドレスが分かっているだけでは、リスト上を移動できない。2つのノードがリスト上どういう順序で連結されているかが分からないと、どちらの方向に走査しているのか分からなくなる。

XOR連結リストは、以下のような問題を抱えている。

  • 汎用的なデバッガはXOR連結リストを追うことができないので、デバッグが難しくなる。
  • メモリ使用量を削減するのと引き換えにコードの複雑性が増し、コード保守が大変になる。
  • 多くのガベージコレクション手法では、実際のポインタでないとうまく機能しない。
  • ポインタ型のXOR演算は定義されていないことがある(例えば、C言語)ので、ポインタ型と整数型の間で型変換が必要となる。
  • リスト上を走査する場合、常に1つ前のノードのアドレスを保持していないと、走査できない。
  • 例えば、別の構造体にXOR連結リスト上のノードのアドレスがある場合、その構造体からノードが得られても、そのノードをリストから外す操作やそのノードの次に別のノードを挿入する操作が不可能である。例えば、使用中のプロセス制御ブロック(PCB)を対応するプロセスの終了時に使用中リストからフリーリストに繋ぎ変えるといった場合、使用中PCBリストはXOR連結リストでは構成できない。

コンピュータのメモリは増大しているため、XOR連結リストは一部の組み込みシステムのようなメモリが限られている場合以外では無用となっている。組み込みシステムでも、Unrolled linked list の方がより実用的である(キャッシュヒット率を向上させ、ランダムアクセス性能が向上するという利点もある)。

特徴

  • リスト上の1つのノードだけが分かった状態では、そのリスト上の他のノードのアドレスは得られない。
  • あるノードから次のノードに移動(走査)していくには、XOR演算を2回行えばよく、どちらの方向でも同じ処理になる。{…B C D…} というリストがあって、レジスタ R1 には現在のノードのアドレス(例えば C)、レジスタ R2 には前のノード(例えば D)のアドレスと現在のノード(C)のアドレスを XOR したもの(C⊕D)が格納されているとする。このとき、次のノードのアドレスを得る処理を System/360 の命令で表すと次のようになる。
 X  R2,Link    R2 <- C⊕D ⊕ B⊕D (すなわち、B⊕C となる。"Link" は現在ノードのリンク
                                   フィールドであり、B⊕D が格納されている)
 XR R1,R2      R1 <- C ⊕ B⊕C    (すなわち、B が得られる)
  • リストの終端は次のノードのアドレスがゼロであるとしておく({0 A B C…})。すなわち、A のリンクフィールドは 0⊕B となる。従って、上記の命令列の後で得られたアドレスがゼロかどうかをチェックしなければならない。この場合、リストの先頭を保持するときに A のアドレスだけを保持すればよい(1つ前のアドレスがゼロであることが自明であるため)。
  • 別の方式として、リスト終端が走査に対して自動的に反射するようにもできる。この場合は端のノードのリンクフィールドをゼロにしておく。例えば、B から A の方向に移動してきたとき、A のリンクフィールドがゼロであれば、上記命令列を実施すると B のアドレスが得られる。ただしこの場合、リストの先頭を保持するときに A と B のアドレスを保持しておく必要がある(A だけでは次のノードのアドレスが全く分からないため)。

なぜうまくいくのか?

鍵となるのは、最初の命令と以下のようなXORの性質である。

  • X⊕X=0
  • X⊕0=X
  • X⊕Y=Y⊕X
  • (X⊕Y)⊕Z=X⊕(Y⊕Z)

R2 レジスタには、現在のノード C のアドレスと1つ前のノードのアドレス P の XOR、すなわち C⊕P が常に格納されている。ノードのリンクフィールドには、前後のノードのアドレスのXOR、すなわち L⊕R が格納されている。従って、R2 (C⊕P) と現在のリンクフィールド (L⊕R) の XOR を求めると C⊕P⊕L⊕R となる。

  • 1つ前のノードが L であった場合、P と L は同じなので打ち消しあい、C⊕R が残る。
  • 1つ前のノードが R であった場合、P と R は同じなので打ち消しあい、C⊕L が残る。

どちらの場合も、残るのは現在のアドレスと次のノードのアドレスの XOR である。これを R1 にある現在ノードのアドレスと XOR することで次のノードのアドレスだけが残る。このとき、R2 には新たな現在ノードと1つ前のノードのアドレスの XOR が残されている。

変種

XOR連結リストの考え方は、同様の性質を持つ任意の二項演算にも応用できる。XORを加算や減算に置換したものは、XORの場合とは微妙に異なるが、ほぼ同等な機能を持つ。

加算連結リスト

  ...  A        B         C         D         E  ...
          <–>  A+C  <->  B+D  <->  C+E  <->

この場合、次のノードのアドレスは、1つ前のノードのアドレスを現在ノードのリンクフィールドの値から減算することで得られる。XOR連結リストとほぼ同じだが、終端ノードのリンクフィールドをゼロにしても反射することはない。なお、加算によってオーバーフローを起こしても何ら問題はない。

減算連結リスト

  ...  A        B         C         D         E  ...
          <–>  C-A  <->  D-B  <->  E-C  <->

この場合、走査する方向によって処理が異なる。順方向の場合、現在のリンクフィールドの値に1つ前のノードのアドレスを加算することで、次のノードのアドレスが得られる。逆方向の場合、現在のリンクフィールドの値を1つ前のノードのアドレスから減算することで、次のノードのアドレスが得られる。

減算連結リストは、リスト全体をノード間の位置関係を保ったままメモリ上で移動させた場合、リンクフィールドに全く変更を加える必要がない。これはXOR連結リストにも普通の連結リストにもない利点である。また、C言語ではポインタ型を整数型にキャストする必要もない。C言語では2つのポインタの減算結果は自動的に整数[1]になるからである。

脚注

  1. ^ ただし、そのポインタが指す型に依った値になる。また、標準では1個の配列の中を指すポインタ同士でなければならないことになっている。

関連項目


「XOR linked list」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「XOR linked list」の関連用語

XOR linked listのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



XOR linked listのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのXOR連結リスト (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS