XOR linked list implementation - Follow Up

Question

This question is a follow up question to the XOR linked list implementation.

I am posting a new code here with taking into consideration the suggestions of Toby Speight and Deduplicator. Please advise how the code efficiency can be improved.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
struct StNode {
 int value;
 uintptr_t both;
}; 
typedef struct StNode StHexNode;
StHexNode *add(StHexNode *lastNode, int value)
{
 StHexNode *newNode = malloc(sizeof(struct StNode));
 newNode->value = value;
 
 //latest node's [both]=pointer value pointing previous node:
 newNode->both = (uintptr_t)lastNode; 
 //calculating previous node [both]:
 lastNode->both = (uintptr_t)newNode ^ lastNode->both;
 return newNode;
}
StHexNode *get(StHexNode *headNode, unsigned int index)
{
 
 StHexNode *prevNode;
 StHexNode *currNode;
 uintptr_t tmp;
 
 //cur=1, prev=0
 currNode = (struct StNode *) ((headNode->both) ^ 0);
 prevNode = headNode;
 
 for(int i=2; i<=index; i++)
 {
 tmp = (uintptr_t)prevNode;
 prevNode = currNode;
 currNode = (struct StNode *) (currNode->both ^ tmp);
 }
 return currNode;
}
int free_list(StHexNode *headNode)
{
 StHexNode *prevNode;
 StHexNode *currNode;
 uintptr_t tmp;
 int ctr=0;
 
 //case: there is a only head node in the list
 if(headNode->both == 0) 
 {
 free(headNode);
 return ++ctr;
 }
 
 //prev=head, curr=second_node
 currNode = (struct StNode *) ((headNode->both) ^ 0);
 prevNode = headNode;
 
 while(currNode->both != (uintptr_t)prevNode)
 {
 tmp = (uintptr_t)prevNode;
 free(prevNode);
 ctr++;
 prevNode = currNode;
 currNode = (struct StNode *) (currNode->both ^ tmp);
 }
 //last node
 free(currNode);
 ctr++;
 
 return ctr;
}
int main(void) 
{
 unsigned int i;
 
 //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
 StHexNode *headNode = malloc(sizeof(struct StNode));
 StHexNode *tailNode = headNode; //last node pointer in the list
 
 //lets add 100 nodes after head
 //special handling of both value at head node
 for(headNode->both = 0, i=100; i<200; i++)
 {
 tailNode = add(tailNode, i);
 //printf("last node value:%d\n", tailNode->value);
 }
 //get index=50 node value
 StHexNode *iNode = get(headNode, 50);
 printf( "result: %d\n", iNode->value);
 //free memory
 printf("we released %d list\n", free_list(headNode));
 
 }

• Toby Speight: Any reason you didn't take Deduplicator's advice to use sizeof *newNode as argument to malloc()?
• Toby Speight: I still see no function to release the resources.

Answer 1

Don't use a different name for a struct and its typedef

Why is struct StNode typedef'ed to StHexNode? What does the Hex mean here, I don't see anything hexadecimal or hexagonal in the rest of the code? You can use exactly the same name for a struct as for its typedef, so I would just use that:

typedef struct StNode StNode;

You can also combine the typedef with the struct definition:

typedef struct StNode {
 ...
} StNode;

Use typedefs consistently

I see you use StHexNode in some places, and struct StNode in others. Be consistent and only use the typedef'ed variant.

Avoid repeating type names if possible

In this line:

StHexNode *newNode = malloc(sizeof(struct StNode));

Besides the inconstent use of the typedef, you repeat the type twice. That makes this error prone (if you make a mistake on the right side it will compile without errors but it will probably be wrong), and if you ever have to change the type of the variable newNode, you would have to do it in at least two places. It is better to avoid repeating the type name, but instead repeat the variable name:

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

Prefer using compound assignment operators to avoid repetition

Use compound assignment operators if possible to save some typing, and also avoiding possible mistakes. For example, instead of:

lastNode->both = (uintptr_t)newNode ^ lastNode->both;

Prefer:

lastNode->both ^= (uintptr_t)newNode;

Simplifying get()

You can simplify the function get() somewhat. In particular, when looping over the elements of a list, try to start at index 0, and avoid making the start and end special cases. You can do this here like so:

StNode *get(StNode *headNode, unsigned int index)
{ 
 StNode *currNode = headNode;
 uintptr_t prev = 0;
 
 for (int i = 0; i < index; i++)
 {
 uintptr_t next = currNode->both ^ prev;
 prev = (uintptr_t)currNode;
 currNode = (StNode *)(next);
 }
 return currNode;
}

Note that you could even avoid the declaration of currNode if you change the name of headNode to currNode, but I would personally keep it as it is above, as it makes the role of the parameter and the local variable more clear.

Simplifying free_list()

The same goes for free_list(): you should not need to make a list of one element a special case. Also, why is free_list() calculating the number of elements of a list that will have been deleted by the time it returns?

void free_list(StNode *headNode)
{
 StNode *currNode = headNode;
 uintptr_t prev = 0;
 
 while (currNode)
 {
 uintptr_t next = currNode->both ^ prev;
 prev = (uintptr_t)currNode;
 free(currNode);
 currNode = (StNode *)(next);
 }
}

Use a unique and consistent naming scheme

If you want to use your XOR linked list in a real program, consider that names like StNode and get() are very generic and will likely conflict with other parts of a larger project. Maybe you need a binary tree implementation as well for example, and how are you going to name its function to retrieve an element at a given index? To solve this issue in C, come up with a unique prefix that you can use for all the struct and function names. For example, prefix everything with xllist_:

typedef struct xllist_node {
 ...
} xllist_node;
xllist_node *xllist_add(xllist_node *lastNode, int value);
xllist_node *xllist_get(xllist_node *headNode, usigned int index);
void xllist_free(xllist_node *headNode);

Of course you can argue about what the prefix should be exactly. I find something like xor_linked_list or XorLinkedList a bit too verbose, so xllist is a compromise: it still has list clearly in the name, and if you don't know what xl is you can look it up, and once you have seen what it means it is easy to remember that xl stands for XOR linked I hope.

Create a struct representing the whole list

You have a struct for a node, but not one for the whole list. That means the caller of your functions has to manually allocate the first list element, and it needs to keep track of both the head and tail node. It is much better if you create a struct representing the list:

typedef struct xllist {
 xllist_node *head;
 xllist_node *tail;
} xllist;

And then pass a pointer to this struct to functions like xllist_get(), xllist_add() and xllist_free(), like so:

xllist_node *xllist_add(xllist *list, int value) {
 xllist_node *newNode = malloc(sizeof(*newNode));
 newNode->both = (uintptr_t)xllist->tail;
 newNode->value = value;
 if (xllist->tail) {
 // Append it to the existing tail node
 xllist->tail->both ^= (uintptr_t)newNode;
 xllist->tail = newNode;
 } else {
 // The list was empty
 xllist->head = newNode;
 xllist->tail = newNode;
 }
 return newNode;
}

And you use it like so in main():

xllist myList = {NULL, NULL}; // declare an empty list
for (int i = 100; i < 200; i++)
{
 xllist_add(&myList, i);
}

Answer 2

Updated version after applying advice from G. Sliepen.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef struct StNode {
 int value;
 uintptr_t both;
} StNode; 
//keep track of linked list head and tail
typedef struct xllist {
 //I named first node as headNode, and last node as tailNode
 StNode *head;
 StNode *tail;
} xllist;
StNode *xllist_add(xllist *list, int value)
{
 StNode *newNode = malloc(sizeof *newNode); 
 newNode->value = value;
 if(list->head == NULL)
 {
 //very first node
 list->head = newNode;
 list->tail = newNode;
 list->head->both = 0;
 return newNode;
 }
 
 list->tail->both ^= (uintptr_t)newNode;
 newNode->both = (uintptr_t)list->tail;
 list->tail = newNode;
 
 return newNode;
}
StNode *xllist_get(xllist *list, unsigned int index)
{ 
 StNode *currNode = list->head;
 uintptr_t prev=0;
 
 for(int i=0; i<index; i++)
 {
 uintptr_t next = currNode->both ^ prev;
 prev = (uintptr_t)currNode;
 currNode = (StNode *)next;
 }
 return currNode;
}
void xllist_free(xllist *list)
{
 StNode *currNode=list->head;
 uintptr_t prev=0, next;
 
 while(currNode)
 {
 next = prev ^ (uintptr_t)currNode->both;
 prev = (uintptr_t)currNode;
 free(currNode);
 currNode = (StNode *)next;
 
 }
 
}
int main(void) 
{
 unsigned int i; 
 xllist myList = {NULL, NULL};
 
 //lets xllist_add 100 nodes after head
 //special handling of both value at head node
 for(i=100; i<200; i++)
 {
 xllist_add(&myList, i);
 }
 
 //xllist_get index=50 node value
 StNode *iNode = xllist_get(&myList, 50);
 printf( "result: %d\n", iNode->value);
 
 //free memory
 xllist_free(&myList);
 
}

• G. Sliepen: I would still rename StNode to xllist_node, again to have a consistent prefix and to avoid possible conflicts with other data structures that have nodes.
• Erdenebat Ulziisaikhan: got it. Important thing is I got the concept. will very appreciated if you review my codes in the future.
• G. Sliepen: Sure, just post new questions here on CodeReview and I and others will have a look at it :)