XOR linked list implementation

Question

I am trying to resolve below question in order to prepare for an interview xD

An XOR linked list is a more memory efficient doubly linked list. Instead of each node holding next and prev fields, it holds a field named both, which is an XOR of the next node and the previous node. Implement an XOR linked list; it has an add(element) which adds the element to the end, and a get(index) which returns the node at index.

Please suggest how this implementation can be improved. Thank you in prior.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int value;
    long both;
    
} StNode; 
typedef StNode *pStNode;

pStNode add(pStNode lastNode, int value)
{
    pStNode newNode = (StNode *) malloc(sizeof(StNode));
    newNode->value = value;
    
    //[both]=value of previous node pointer if it is last node
    newNode->both = (long)lastNode; 
    
    //calculating previous node [both] value
    lastNode->both = (long)newNode ^ lastNode->both;
    
    return newNode;
}

pStNode get(pStNode headNode, int index)
{    
    pStNode prevNode;
    pStNode currNode;
    long tmp;
    
    //special handling
    //case: cur=1, prev=0
    //we have set previous node of head node value to be 0 manually
    currNode = (StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;
    
    //skim through linked list
    for(int i=2; i<=index; i++)
    {
        tmp = (long)prevNode;
        prevNode = currNode;
        currNode = (StNode *)(currNode->both ^ tmp);
    }
    
    return currNode;
}


int main() {  
    
    //I named first node as headNode, and last node as tailNode
    //create head node with both=0 since there is no previous node to it
    pStNode headNode = (StNode *) malloc(sizeof(StNode));
    headNode->both = 0; 
    headNode->value = 2;
    
    //assign pointers
    pStNode tailNode = headNode;
    
    //lets add 10 nodes after head, and assign values
    for(int i=3; i<13; i++)
    {
        tailNode = add(tailNode, i);
    }
    
    //get node value where index=3
    pStNode iNode = get(headNode, 3);
    printf( "result: %d\n",  iNode->value);
    
    return 0;
}

Answer 1

long isn't necessarily a good choice of integer type for storing pointers - luckily <stdint.h> provides us with uintptr_t which is guaranteed to be wide enough for this purpose (always prefer an unsigned type when working with bitwise operations).

I dislike hiding pointer types behind typedefs such as pStNode. I think it's clearer to use the pointer type directly - or a pointer to const StNode where appropriate. For example, get() should take a pointer to const.

It's unnecessary (and generally considered unwise) to cast the result of malloc(). void* can be assigned to any kind of pointer in C.

There's quite a lot missing from the code that I would expect from something claiming to be an implementation of the list. There's no function for removing elements, and the only accessor provided is the poorly-performing random-access getter.

In particular, you haven't provided next() and prev() functions, which I'd expect to see if you want to demonstrate that both directions of traversal work correctly.

Why does get() accept a signed integer for the index? It appears that negative values are all equivalent to 0; we should either make those work or accept an unsigned type instead. Also, we can safely reduce the scope of tmp to within the loop.

It's best to write main() as a function prototype int main(void) (i.e. taking no arguments, rather than an unspecified number of arguments). And unlike other functions, main() doesn't need to return a value for success, so that line can be omitted.

Answer 2

long both;

1. Using a long for storing a cast pointer can be both wasteful and too little. Just use the dedicated uintptr_t. Even if your implementation might not be fully up to C99 (MS greets), it probably has <stdint.h> and the typedef.

pStNode newNode = (StNode *) malloc(sizeof(StNode));

The above line demonstrates three bad ideas:

2. More pieces to keep track of means more complexity, which is bad. Thus hiding pointers behind typedefs is a bad idea, unless that pointer-type is never dereferenced, and is thus the one true type used.

3. Casting a void* is superfluous and error-prone.
   See "Do I cast the result of malloc? ".

4. Don't use sizeof(TYPE) unless unavoidable. Getting it right even if the types aren't obscured is error-prone. Just use sizeof *pointer.

pStNode get(pStNode headNode, int index)

5. There is a type uniquely suited as an index: size_t. Alternatively, if you want something signed, you might be interested in ptrdiff_t. Though yes, if your use-case guarantees few enough nodes, int might work.

6. You really should encapsulate your list somehow. Currently, you are creating a one-off in main().
   Also, cleanup should be possible without terminating the program.

7. If you use at least C99, main() has an implicit return 0;.