4 ms·
XOR linked list: http://en.wikipedia.org/wiki/XOR_linked_list http://en.wikipedia.org/wiki/XOR_linked_list It's a double-linked list with just one link per nod
by abcd_f 13y ago
XOR linked list: http://en.wikipedia.org/wiki/XOR_linked_list http://en.wikipedia.org/wiki/XOR_linked_list
It's a double-linked list with just one link per node. However, to start traversing it you have to know at least two adjacent nodes.
PS. May not be useful per se, but interesting nonetheless.
- aaronem 13y agoThe XOR swap is interesting, too. But I wouldn't want to see one in code someone wrote today, and which wasn't targeted at an embedded platform -- and a heavily constrained embedded platform, at that. (MSP430? Sure. ARM Cortex-M3? You've got enough space to do it properly.)
- dllthomas 13y agoIt's not just "you've got enough space" - it's only relevant if both operands are in registers already. If they're both in memory, then the xors are entirely redundant (first things you'd have to do is read values into two registers, at which point you can just write it back the other way). I wouldn't object to seeing it in a critical section in high performance code with substantial register pressure, but ideally it could be inserted by the compiler!