A doubly linked list that only stores 1 pointer per element [closed]

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

closed as off-topic by user80551, The Guy with The Hat, Peter Taylor, ace_HongKongIndependence, Glenn Randers-PehrsonApr 17 '14 at 0:44

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – user80551, The Guy with The Hat, Peter Taylor, ace_HongKongIndependence, Glenn Randers-Pehrson
If this question can be reworded to fit the rules in the help center, please edit the question.

• the common term for this type of list is "doubly linked list" – ardnew Sep 6 '12 at 14:33
• Indeed, I didn't call it that originally because in the context of the problem its a slight misnomer. – PhonicUK Sep 6 '12 at 14:39
• Is this a code-golf or a code-challenge ? You currently have it tagged as both. – Paul R Sep 6 '12 at 15:13
• -1. That's not an objective winning criterion. (plus, it's so much of a classic) – J B Sep 6 '12 at 21:59
• @PhonicUK: please see the FAQ: All questions on this site, whether a programming puzzle or a code golf, should have … An objective primary winning criterion, so that it is possible to indisputably decide which entry should win. – Paul R Sep 7 '12 at 16:17

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

• but DO NOT use this on a garbage collected system! – Alex Brown Sep 7 '12 at 7:26
• The XOR approach is what I've always considered the 'correct' answer - now I'm interested to see what else people can come up with! – PhonicUK Sep 7 '12 at 8:47

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:

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


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)
{
return 1;
return 0;
}

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

while(!isPtrOdd(Head->next))       // Loop completes when tail is found

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

}

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

while(!isPtrOdd(Head->next))       // Loop completes when tail is found

// Determine number of nodes in List
int count = 1;

• @PhonicUK: Following the added requirement that the nodes not contain any additional meta-data (such as a bool flag denoting the head) I have created a clever - to some, sloppy - workaround using the LSB of the next pointer as a end of list flag – nicholas Sep 7 '12 at 13:25