53ningen.com53ningen.com
Loading...

連結リストのバリエーション

2014/06/10 10:35
2014/06/10 10:35
Programming
アルゴリズム
データ構造
連結リストには単方向リストだけでなく様々なバリエーションがある。たとえば Java の LinkedList は双方向リストとして実装されている。その他にも単方向・双方向な循環連結リスト、メモリ効率二重連結リストなどがある。

双方向連結リスト(Doubly-linked list)

単方向リストは次のノードへの参照：next しかもたなかったが、双方向連結リストは前のノード：prev への参照も持つ。

循環連結リスト(Circular linked list)

↓ こんなやつ

メモリ効率二重連結リスト(XOR linked list)

☆ 次の性質を利用して双方向リストを実現している。
X⊕X=0 X⊕0=X X⊕Y=Y⊕X (X⊕Y)⊕Z=X⊕(Y⊕Z)