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

連結リストには単方向リストだけでなく様々なバリエーションがある。たとえば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)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です