it only works if you are linearly iterating from the start/end of a list.
IMHO one of the (few) primary benefits of linked lists is random access to insert/delete/iterate an element without having to traverse the entire list. Something that breaks with xor lists.
Secondly if you have so many nodes that the memory saving of one pointer is significant. Its likely traversing that list will take forever and force you to use a different algo anyway.
... an improvement on basic linked lists would be 16B/32B/128B/512B etc alignment of the nodes memory address and bit packing the Left/Right offset in units of the alignment unit. Hell you could probably beat xor lists for space for a range of workloads.
So your function needs to be passed current and next (or prev, depending on which direction you want to iterate). XOR-lists have lots of issues. This isn't one of them.
No you're not. Your function needs to accept two pointers. Your data structure doesn't need to store two pointers.
Unless you're storing external pointers to every node (in which case you'll actually break even with the traditional implementation in terms of size), you'll still have significant savings. Passing an extra pointer to a function is pretty trivial in terms of size.
its how I use them. theres the list + some other structure/object that points/references the node, usually multiple time and the node is contained in multiple lists - big data + performance optimization
IMHO one of the (few) primary benefits of linked lists is random access to insert/delete/iterate an element without having to traverse the entire list. Something that breaks with xor lists.
Secondly if you have so many nodes that the memory saving of one pointer is significant. Its likely traversing that list will take forever and force you to use a different algo anyway.
... an improvement on basic linked lists would be 16B/32B/128B/512B etc alignment of the nodes memory address and bit packing the Left/Right offset in units of the alignment unit. Hell you could probably beat xor lists for space for a range of workloads.