Datenstrukturdienstag:
Mir ist aufgefallen, das ich sehr viele Bäume poste. Heute mal kein Baum, sondern eine verkettete Liste mit einem Trick: Die XOR-Linked-List.

Das ist eine Doppelt-Verkettete-Linked-List. Bei dieser Variante wird an jedem Knoten aber nur ein Pointer für die Prev- bzw. Next-Nodes benötigt. Dieser Pointer ist kein Pointer in dem Sinne, sondern das XOR des Prev- und Next-Pointers.

Das geht, weil man beim Traversieren der Liste ja weiß, von welchem Element man kommt. Man kann deshalb immer die Adresse des nächsten (bzw vorherigen) kNotens ausrechnen, indem man den Pointer, von dem man kommt, mit XOR drauf rechnet.

Warum man diese Struktur in der Praxis nicht wirklich sieht? Das kann man gut an der Sektion “Drawbacks” auf Wikipedia lesen. Naja, und eigentlich ist’s jetzt nicht so krass, einen Pointer pro Node einzusparen.