A doubly linked list that only stores 1 pointer per element A favorite puzzle of mine. Not massively difficult but a tad interesting.

The Objective

Using a low level language (C/C++/similar level) - create a doubly linked list of elements that only stores a single pointer instead of storing both a previous and next element pointer as you normally would.

You must be able to find each element in your linked list, starting from either the first element you created, or the most recently created element.

You must use malloc(sizeof(*node)) or similar to store each element (the addresses are likely to be non-sequential as a result)

The Restrictions


The data type you use to store your value must be the length of a function pointer (No using long values to store 2 pointer addresses one after another)
You may not use any external libraries (only the standard libc methods are permitted if you're using C/C++, apply the spirit of this rule to other languages)
You may not store any additional metadata elsewhere (or in the list elements themselves) to solve this. The list element may only contain two fields - the 'data' value and the value you will use to find the previous and next elements. It may look something like:



    struct node
    {
       int myValue;
       struct node* prevAndNextNode;
    }


Golf or Challenge?

You can either find the most elegant/interesting solution, or the shortest. Take your pick!

Have fun ;)
This is an xor linked list:

struct node {
  int myValue;
  uintptr_t xor_prev_and_next;
  node *next(node *prev) {
    return (node*)((uintptr_t)prev ^ xor_prev_and_next);
  }
  node *prev(node *next) {
    return (node*)((uintptr_t)next ^ xor_prev_and_next);
  }
}

struct list {
  node *first;
  node *last;
  int sum_forwards() {
    int sum = 0;
    node *prev = NULL;
    node *curr = first;
    while (curr) {
      sum += curr-&gt;myValue;
      prev, curr = curr, curr-&gt;next(prev);
    }
    return sum;
  }
}