Can we implement a doubly-linked list using a single pointer? [duplicate]

Question

I want to use a structure like:

struct node {
   char[10] tag;
   struct node *next;
};

I want to use the above structure to create a doubly-linked list. Is that possible and if yes, then how I can achieve it?

Answer 1

Yes, it's possible, but it's a dirty hack.

It's called XOR linked list. (https://en.wikipedia.org/wiki/XOR_linked_list)

Each node stores a XOR of next and prev as a uintptr_t.

---

Here is an example:

#include <cstddef>
#include <iostream>

struct Node
{
    int num;
    uintptr_t ptr;
};

int main()
{
    Node *arr[4];
    // Here we create a new list.
    int num = 0;
    for (auto &it : arr)
    {
        it = new Node;
        it->num = ++num;
    }
    arr[0]->ptr =                     (uintptr_t)arr[1];
    arr[1]->ptr = (uintptr_t)arr[0] ^ (uintptr_t)arr[2];
    arr[2]->ptr = (uintptr_t)arr[1] ^ (uintptr_t)arr[3];
    arr[3]->ptr = (uintptr_t)arr[2];

    // And here we iterate over it
    Node *cur = arr[0], *prev = 0;
    do
    {
        std::cout << cur->num << ' ';
        prev = (Node *)(cur->ptr ^ (uintptr_t)prev);
        std::swap(cur, prev);
    }
    while (cur);
    return 0;
}

It prints 1 2 3 4 as expected.