These are neat tricks, but they are now completely different data structures to the original one (and, IMO, maybe not all that great a data structure, in that i

These are neat tricks, but they are now completely different data structures to the original one (and, IMO, maybe not all that great a data structure, in that it seems to be a festival of special cases and clever hacks). Once you're willing to allocate large blocks of objects, all sorts of things are possible, but you have to be ready for radically different performance properties (not always bad, just... different). The XOR-trick is curious (if weird) because it preserves most* of the properties of the list structure. Traversal is almost identical to that of the original list in machine terms. Maybe an additional cycle on the critical path; probably not the worst thing in pointer chasing code. * you do need to double the size of your iterator, so if you were needing to stash large numbers of iterators relative to the number of linked list elements, this wouldn't be a particularly nice trick.