It can be done even better. I read an article about that recently. Nowadays pointers are 64-bit. So the simple xoring already saves 64 bits. But, in most case

It can be done even better. I read an article about that recently. Nowadays pointers are 64-bit. So the simple xoring already saves 64 bits. But, in most cases allocated memory blocks are close together, so that xoring of those 64-bit values gives a 32-bit value. So if you ignore the upper half and store the result in 32-bit, you basically save 96 bits. For the cases where the upper half matters, you can store it in an additional hashmap. But it goes even better, if you allocate blocks and store indices. Like if you allocate blocks of 512 objects each. Then it is likely that the next/prev index is also in that block. Then you can store those indices in 2*8 bits (or just 8 bits if xored again?). In case it is in another block, you use the hashmap again. Then you save up to 120 bits. The question remains, how do you find that hashmap? The article had a really clever solution. You allocate the blocks as 4K-aligned pages, e.g. by using mmap rather than malloc. Then you put a pointer to the hashmap at the beginning of the page, and when you have a pointer inside the block, you can find the hashmap by rounding the pointer down to the previous aligned position.