Is it possible to implement XOR LinkedList in Java(DLL with single pointer) [duplicate]

Question

XOR linked lists are basically efficient version of linked list which store addresses of previous and next nodes to implement Doubly Linked List using only single pointer. I was wondering if it's possible to implement the in Java, since it doesn't have pointers. In C this could be done by

 /* Insert a node at the begining of the XORed linked list and makes the
    newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node));
    new_node->data = data;

    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);

    /* If linked list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }

    // Change head
    *head_ref = new_node;
}

Tokoloshe

Performing arithmetic on pointers is not generally possible in Java because they are always treated as references to objects, not as numbers. – Ninetta

I'm curious as to what the implementation of any doubly linked list might be in Java, and could it already be doing something like the OP under the hood? – Mitzi

This question was asked to me in Microsoft interview, I was like shocked that it's possible to implement doubly linked list using single pointer – Tokoloshe

Read here: web.archive.org/web/20160301084747/www.params.me/2011/06/… – Eulogium

Are you OK with using indexes into an array instead of actual pointers? The difference isn't that big anyway.. – Do

@harold I don't get your point? Are you trying to make linked list using arrays? – Tokoloshe

Yes. You can use pairs of elements as data and index of next item (or use the XOR trick). – Do

@harold That's a nice trick, I guess that'll be the only way of doing it then :-) – Tokoloshe

Haha funny, but your DLL(Doubly Linked List) abbreviation gave me an idea about DLL(Dynamic Link Library) which could be created using C/C++ and can consumed in a Java environment using Java Native interface(JNI) and some stub class configuration to accommodate the bridge. But to put it simply, Java uses reference types which garbage collector depends on and hence pointers are not supported and also reference XOR is not possible instead when references are XOR'd the underlying objects are XOR'd. – Agrimony

Answer 1

No, you can't do this in Java at all -- you cannot get the address of an object or compute a reference to an object from other values. This allows the garbage collector to move objects around without interfering with the program.

It's also a really bad idea in C++.

If you're worried about the memory overhead in a linked list, you can store multiple items per node. If a node has prev, next, and items[16] references, and you always make sure your nodes are at least half full, then it will use less memory than an XOR list on average.

Beet

Can you please elaborate, if you store multiple items per node, won't that create an overhead itself? I don't get the point – Tokoloshe

Normally, a linked list node in Java has 3 references (prev, next, item) and and object header, so it's 4 references big. That's an overhead of 4 words for every item you add. An xor list has 3 words for every item you add. A list with 16 items per node, with all the nodes at least half full (8 items present), has 21 words per node, but you divide by at least 8 items to get 21/8 (less than 3) words per item of overhead – Beet

Oh, I forgot the word to store the count and/or start in each node, so 22/8. Still smaller – Beet