スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

xor linked list

前後のポインタを持つ代わりに、前後のポインタのxor値をもつ双方向リスト。
・ポインタ2個分のメモリが1個になる
・要素を操作するときには、操作する要素のポインタに加え、前後どちらかの要素がわかっていなければならない。
・ポインタ操作にxor演算がはいるので通常の双方向リストと比べて遅くなる。
という特徴をもつ。面白いけど使い所がわからない・・・

前後どちらかのポインタがわからない限りは、リストの先頭要素か最終要素しか操作できない。
前後のどちらかの要素が判明しているなら、その分のメモリを使って双方向リスト使えよという話になるので、(外部から前後の要素が判明するようなパターンを除いて)要素単体単体へ操作可能なシーンは期待できない。

・リストを前向きにも後ろ向きにも辿りたい
・メモリをポインタ1個分でいいから削りたい
・追加と削除はリストの先頭あるいは最後尾の要素に発生する
・要素の走査はリストの先頭あるいは最後尾からしか発生しない
という要求のときぐらいにしか使えない?


スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。