A doubly linked list that only stores 1 pointer per element

Question

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 ;)

Answer 1

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->myValue;
      prev, curr = curr, curr->next(prev);
    }
    return sum;
  }
}

Answer 2

EDIT

Problem Definition

• For a given node, find the next node (null if tail)
• For a given node, find the previous node (null if head)
• Return a node at a specified offset from the start of the list (null if out of bounds)
• Return a node at a specified offset from the end of the list (null if out of bounds)

The constraints have been revised by the OP, and include restricting the nodes as well as external structures from storing any metadata. My initial implementation of a Circular Linked List did not meet this criteria since it required knowing the head node with a flag value.

I present now a clever workaround:

A Circular Linked List with Forced Node Address Parity

Note that lately I am a C# programmer, but I will try to do this C-style as possible.

The List Node Structure

Nothing fancy here:

struct ListNode
{
    ListNode *next;
    int value;
};

Adding Nodes with Even Addresses Only

Since this implementation still requires that we be able to find the start of the list, we can use the LSB of the next pointer as a flag. If the last bit of the next pointer is 1, it means we are at the end of the list. A few helper functions:

bool isPtrOdd(void * addr)
{
    if((unsigned int) addr & 1)
        return 1;
    return 0;
}

ListNode * GetNodeAddr(ListNode * node)
{
    if(isPtrOdd(node))
        return node - 1;
    return node;
}

The only special considerations are that we must ensure that nodes are allocated only on even addresses. There are several ways of doing this, but I will show a basic one which allocates an extra byte for each node:

ListNode * NewNode()
{
    void * memBlock = malloc(4 + 4 + 1); // 32 bit address, 32 bit value, 1 padding byte

    if(isPtrOdd(memBlock)) // if the block started on an odd address
        memBlock++;                 // shift over to an even address

    ListNode * newNode = memBlock;

    newNode->value = 0;
    newNode->next = newNode + 1; // a new node circularly points to itself

    return newNode;
}

void AddNode(ListNode * list, ListNode * newNode)
{
    while(!isPtrOdd(list->next))
        list = list->next;         // Get to the end of the list

    newNode->next = list->next;    // Point the new node to the list head + 1
    list->next = newNode;
}

Traversing the List

And using C-style external functions (no classes) we define each of the desired functions:

ListNode * NextNode(ListNode &Node)
{
    if(isPtrOdd(Node->next))
        return 0;
    return &(Node->next);
}

ListNode * PrevNode(ListNode &Node)
{
    ListNode curNode = Node;
    while(&(GetNodeAddr(curNode->next)) != &Node) // We compare addresses instead of values
        curNode = GetNodeAddr(curNode->next);     // since the == operator is not defined for structs

    if(isPtrOdd(curNode->next)) // if the 'previous node' is actually the end of list
        return 0;

    return &curNode;
}

ListNode * NodeFromStart(ListNode &Node, int offset)
{
    // This function returns offset from head node given
    // any node in the list

    ListNode Head = Node;
    while(!isPtrOdd(Head->next))       // Loop completes when tail is found
        Head = GetNodeAddr(Head->next);
    Head = GetNodeAddr(Head->next);    // Move once more and get to head

    for(int n=0; n<offset; n++)
    {
        if(isPtrOdd(Head->next))       // if we reach the end of the list
            return 0;
        Head = Head->next;
    }

    return &Head;
}

ListNode * NodeFromEnd(ListNode &Node, int offset)
{
    // This function returns offset from tail node given
    // any node in the list

    ListNode Head = Node;
    while(!isPtrOdd(Head->next))       // Loop completes when tail is found
        Head = GetNodeAddr(Head->next);
    Head = GetNodeAddr(Head->next);    // Move once more and get to head

    // Determine number of nodes in List
    int count = 1;
    while(!isPtrOdd(Head->next))
    {
        Head = GetNodeAddr(Head->next);
        count++;
    }

    if(count<=offset)
        return 0;

    return NodeFromStart(Head,count - offset);
}