Singly linked list methods implementations

Question

I have implemented various single linked-list related operations in C.

The .c file contains the implementation and the .h file contains function prototypes and the following definitions:

// Various types of data
typedef enum {
 CHAR,
 INT,
 UINT,
 FLOAT,
 DOUBLE,
 ARRAY,
 LIST,
 POINTER
} info_t;
// Linked list data type
typedef struct data {
 info_t info_type;
 union {
 char info_char;
 int info_int;
 unsigned info_uint;
 float info_float;
 double info_double;
 struct arr *info_array;
 struct head *info_list;
 void *info_ptr;
 } info;
} data_t;
#define MAX_ARR_LEN 10
// Linked list node type
typedef struct arr {
 data_t data[MAX_ARR_LEN];
 int len;
} array_t;
// Linked list node type
typedef struct node {
 data_t data;
 struct node *next;
} node_t;
// Linked list header type
typedef struct head {
 node_t *first;
 node_t *last;
 size_t len;
} head_t;

The following is the source code. I would appreciate some code review feedback, any kind of comment, coding style improvements, as well as time/space efficiency concerns, etc.

#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include "linked_list.h"
static void get_fmt_str(char *fmt_str, info_t data_type);
// Get a node memory 
node_t *get_node( data_t *d )
{
 node_t *retptr = NULL;
 retptr = (node_t *)malloc( sizeof(node_t) );
 if( retptr == NULL )
 return NULL;
 retptr->data = *d;
 retptr->next = NULL;
 return retptr;
}
// Free a node memory
void free_node( node_t *n )
{
 free( n );
 n = NULL;
}
// Compare two list nodes
int cmp_fn( data_t *d1, data_t *d2)
{
 assert( d1!=NULL && d2!=NULL && d1->info_type==d2->info_type );
 switch( d1->info_type ) {
 case INT:
 return d1->info.info_int - d2->info.info_int;
 break;
 default:
 break;
 }
 return 0;
}
// Init a list
void init_list( head_t *head )
{
 assert(head!=NULL);
 head->first = head->last = NULL;
 head->len = 0;
 //head->free_node = free_node;
 //head->get_node = get_node;
 //head->cmp_fn = cmp_fn;
}
// Free a list, does nto free head as it could be on stack
void free_list( head_t *head )
{
 node_t *tofree = NULL;
 char fmt_str[2] = { 0 };
 while( head!= NULL && head->len > 0 ) {
 tofree = head->first;
 head->first = head->first->next;
 head->len--;
 get_fmt_str( fmt_str, tofree->data.info_type);
 if (fmt_str[0] == 1) {
 free_list(tofree->data.info.info_list);
 free_node(tofree);
 }
 //else if( fmt_str[0] == 2 ) 
 // free_array(temp_ptr->data);
 //else if( fmt_str[0] == 3 ) 
 // free_ptr(temp_ptr->data);
 else {
 free_node(tofree);
 }
 }
}
// Check if list is empty
bool is_empty( head_t *head)
{
 return head->len == 0;
}
#define MAX_LIST_LEN 1000000
// Check if list is full
bool is_full( head_t *head)
{
 return head->len == MAX_LIST_LEN;
}
// Get length of list
size_t get_len( head_t *head )
{
 return head->len;
}
// Push a node = Insert at front
void insert_atfront( head_t *head, node_t *anode )
{
 assert( head != NULL );
 if( anode == NULL )
 return;
 anode->next = head->first;
 head->first = anode;
 head->len++;
 if( head->last == NULL )
 head->last = anode;
}
// Enqueue a node from rear
void insert_atend( head_t *head, node_t *anode )
{
 assert( head != NULL );
 if( anode == NULL )
 return;
 if( head->last == NULL )
 head->first = anode;
 else 
 head->last->next = anode;
 anode->next = NULL;
 head->last = anode;
 head->len++;
}
// Pop a node = Delete from front
// return NULL if list is empty
node_t *remove_fromfront( head_t *head )
{
 node_t *retptr = NULL;
 assert( head != NULL );
 retptr = head->first;
 if( head->first != NULL ) {
 head->first = head->first->next;
 head->len--;
 }
 if( head->first == NULL ) 
 head->last = NULL;
 return retptr;
}
// Dequeue a node = Delete from end
// return NULL if list is empty
node_t *remove_fromend( head_t *head )
{
 node_t *retptr = NULL;
 node_t *prevptr = NULL;
 assert( head != NULL );
 retptr = head->first;
 while( retptr != head->last ) {
 prevptr = retptr;
 retptr = retptr->next;
 }
 head->last = prevptr;
 if( prevptr != NULL ) {
 prevptr->next = NULL;
 head->len--;
 }
 return retptr;
}
// Insert a node at pos p (1-based)
bool insert_at( head_t *head, size_t p, node_t *anode )
{
 node_t *temp = NULL;
 assert( head != NULL );
 if( anode == NULL )
 return true;
 if( p == 0 ) 
 return false;
 else if( p == 1 && head->len == 0 ) {
 // insert at 1st node in an empty list
 head->last = head->first = anode;
 anode->next = NULL;
 head->len++;
 }
 else if( p == head->len ) {
 // insert at the end
 if( head->last == NULL )
 head->first = anode;
 else 
 head->last->next = anode;
 head->last = anode;
 anode->next = NULL;
 head->len++;
 }
 else if( p > head->len ) 
 return false;
 else {
 // insert in the middle
 temp = head->first;
 while( --p ) {
 temp = temp->next;
 }
 // need to insert between temp and temp->next
 anode->next = temp->next;
 temp->next = anode;
 head->len++;
 }
 return true;
}
// Remove a node at pos p (1-based)
node_t *remove_at( head_t *head, size_t p )
{
 node_t *retptr = NULL, *temp_ptr=NULL;
 assert( head != NULL );
 if( p == 0 ) 
 return NULL;
 else if( p == 1 && head->len == 1 ) {
 // remove 1st node of a one node list 
 retptr = head->first;
 head->last = head->first = NULL;
 retptr->next = NULL;
 }
 else if( p == head->len ) {
 // remove the last node
 retptr = head->first;
 while( --p > 1 ) {
 retptr = retptr->next;
 }
 head->last = retptr;
 retptr = retptr->next;
 retptr->next = NULL;
 }
 else if( p > head->len ) 
 return NULL;
 else {
 // remove from the middle
 retptr = head->first;
 while( --p > 1 ) {
 retptr = retptr->next;
 }
 temp_ptr = retptr->next;
 retptr->next = retptr->next->next;
 retptr = temp_ptr;
 temp_ptr->next = NULL;
 }
 head->len--;
 return retptr;
}
// Delete a node at pos p (1-based)
void delete_at( head_t *head, size_t p )
{
 node_t *ret_ptr = NULL;
 ret_ptr = remove_at(head, p);
 if( ret_ptr!= NULL )
 head->len--;
 free_node(ret_ptr);
}
// Find node at pos p (1-based)
node_t *find_at( head_t *head, size_t p )
{
 node_t *retptr = NULL;
 assert( head != NULL );
 if( p == 0 || p > head->len+1 ) 
 return NULL;
 else {
 retptr = head->first;
 while( --p ) {
 retptr = retptr->next;
 }
 }
 return retptr;
}
// Check data of a node at pos p (1-based)
data_t *check_at( head_t *head, size_t p )
{
 node_t *retptr = NULL;
 retptr = find_at( head, p);
 if( retptr == NULL ) 
 return NULL;
 return &retptr->data;
}
// Update data of a node at pos p (1-based)
bool update_at( head_t *head, size_t p, data_t d )
{
 node_t *retptr = NULL;
 retptr = find_at( head, p);
 if( retptr == NULL ) 
 return false;
 retptr->data = d;
 return true;
}
// Find the first position (1-based) of a given data item in list
// search for given node between [start,stop) stop not included
// e.g. to search whole list, pass start=1, and stop=head->len+1
bool find_pos( head_t *head, data_t *data_ptr, size_t *pos, size_t start, size_t stop )
{
 size_t index = 1;
 node_t *temp = NULL;
 int retval = 0;
 assert( head!=NULL && data_ptr!=NULL && pos!=NULL );
 temp = head->first;
 if( start==0 || stop==0 || start > head->len || stop > head->len+1 || start >= stop ) {
 printf("Inconsistent start=%"PRIu64" and stop=%"PRIu64" [list len=%"PRIu64"]",
 (unsigned long long)start,(unsigned long long)stop,(unsigned long long)head->len);
 return false;
 }
 // return false for empty list as well
 if( temp == NULL )
 return false;
 // skip all nodes before start pos
 while( index < start ) {
 temp = temp->next;
 index++;
 }
 // search for given node between [start,stop) stop not included
 while( index <stop ) {
 retval = cmp_fn( &temp->data, data_ptr);
 if( retval == 0 ) {
 *pos = index;
 return true;
 }
 temp = temp->next;
 index++;
 }
 return false;
}
// Find and delete the first occurences of a data item in list
bool find_delete( head_t *head, data_t *data_ptr )
{
 size_t pos = 0;
 bool retval = true;
 retval = find_pos(head, data_ptr, &pos, 0, head->len);
 if( retval )
 delete_at(head, pos);
 return retval;
}
// Find and delete all occurences of a data item in list
size_t find_delete_all( head_t *head, data_t *data_ptr )
{
 size_t pos = 0;
 bool retval = true;
 size_t count = 0;
 while( retval ) {
 retval = find_pos(head, data_ptr, &pos, 0, head->len);
 if( retval ) {
 delete_at(head, pos);
 count++;
 }
 }
 return count;
}
// Count all occurences of a data item in list
size_t count_all( head_t *head, data_t *data_ptr )
{
 node_t *inode = NULL;
 int retval = 0;
 size_t count = 0;
 for( inode = head->first; inode!=NULL; inode=inode->next ) {
 retval = cmp_fn( &inode->data, data_ptr);
 if( retval == 0 )
 count++;
 }
 return count;
}
static void get_fmt_str( char *fmt_str, info_t data_type )
{
 switch( data_type ) {
 case CHAR: fmt_str[0] = 'c';
 break;
 case INT: fmt_str[0] = 'd';
 break; 
 case UINT: fmt_str[0] = 'u';
 break;
 case FLOAT: fmt_str[0] = 'f';
 break;
 case DOUBLE: fmt_str[0] = 'D';
 break;
 case LIST: fmt_str[0] = 1;
 break;
 case ARRAY: fmt_str[0] = 2;
 break;
 case POINTER: fmt_str[0] = 3;
 break;
 }
}
// Print a list
void print_list( head_t *head )
{
 unsigned count = 0;
 node_t *temp_ptr;
 char fmt_str[2] = {0};
 // traverse the list from the list head
 if( head == NULL || head->len == 0 ) {
 printf("Empty list.\n");
 return;
 }
 else {
 temp_ptr = head->first;
 }
 printf("*-- ");
 while( count < head->len ) {
 get_fmt_str( fmt_str, temp_ptr->data.info_type);
 if( fmt_str[0] == 1 ) 
 print_list(temp_ptr->data.info.info_list);
 //else if( fmt_str[0] == 2 ) 
 // print_array(temp_ptr->data);
 //else if( fmt_str[0] == 3 ) 
 // print_ptr(temp_ptr->data);
 else if( fmt_str[0] == 'c')
 printf("%c, ", temp_ptr->data.info.info_char);
 else if( fmt_str[0] == 'd')
 printf("%d, ", temp_ptr->data.info.info_int);
 else if( fmt_str[0] == 'u')
 printf("%u, ", temp_ptr->data.info.info_uint);
 else if( fmt_str[0] == 'f')
 printf("%f, ", temp_ptr->data.info.info_float);
 else if( fmt_str[0] == 'D')
 printf("%f, ", temp_ptr->data.info.info_double);
 temp_ptr = temp_ptr->next;
 count++;
 }
 if( temp_ptr == NULL )
 printf("NULL--*\n");
 else
 printf("@ \n");
}
// Slice a list
void slice_list( head_t *head )
{
 return;
}
// Reverse a linked list using delete and insert
void reverse_list( head_t *head )
{
 head_t temp_head;
 node_t *temp_node = NULL;
 assert( head!= NULL );
 temp_head.first = NULL;
 temp_head.last = NULL;
 temp_head.len = 0;
 while( (temp_node = remove_fromfront( head )) != NULL ) {
 insert_atfront( &temp_head, temp_node );
 }
 head->first = temp_head.first;
 head->last = temp_head.last;
 head->len = temp_head.len;
}
// Reverse a linked list, iteratively
void reverse_list_iter( head_t *head )
{
 node_t *prevNode=NULL, *currNode=NULL, *nextNode=NULL;
 assert(head!=NULL);
 // return if nothing to reverse (list is empty or only one elemeent)
 if( head->first==NULL || head->first == head->last ) return;
 head->last = head->first;
 currNode = head->first;
 nextNode = currNode->next;
 currNode->next = prevNode;
 while(nextNode!=NULL) {
 head->first = nextNode;
 prevNode = currNode;
 currNode = nextNode;
 nextNode = currNode->next;
 currNode->next = prevNode;
 }
}
// Reverse a linked list, recursively
void reverse_list_recur( head_t *head )
{
 node_t *first_node=NULL;
 assert(head!=NULL);
 // return if nothing to reverse (list is empty or only one elemeent)
 if( head->first==NULL || head->first == head->last ) return;
 first_node = head->first;
 head->first = head->first->next;
 reverse_list_recur( head );
 head->last = head->last->next = first_node;
 first_node->next = NULL;
}
// Concatanate two lists: List1 = List1+List2, no separate header for list2 affter concat
void cat_list( head_t *head1, head_t *head2)
{
 assert( head1 != NULL || head2 != NULL );
 if( head2 == NULL || head2->last == NULL )
 return;
 else if( head1 == NULL || head1->last == NULL ) {
 *head1 = *head2;
 return;
 }
 head1->last->next = head2->first;
 head1->last = head2->last;
 head1->len += head2->len;
 init_list( head2 );
}
// Copy a list
head_t *copy_list( head_t *head )
{
 head_t *new_head = NULL;
 node_t *inode = NULL, *new_node = NULL, *prev_node = NULL;
 assert(head!=NULL);
 new_head = (head_t *)malloc(sizeof(head_t));
 if( new_head == NULL ) {
 printf("ERR1:Out of memory\n");
 return NULL;
 }
 memcpy(new_head, head, sizeof(head_t));
 for( inode = head->first; inode != NULL; inode = inode->next ) {
 new_node = (node_t *)malloc(sizeof(node_t));
 if( new_node == NULL ) {
 printf("ERR2:Out of memory\n");
 return NULL;
 }
 if( inode == head->first )
 new_head->first = new_node;
 else
 prev_node->next = new_node;
 memcpy(&new_node->data, &inode->data, sizeof(data_t));
 new_node->next = NULL;
 prev_node = new_node;
 }
 return new_head;
}
// Copy a list, fast
head_t *copy_list_fast( head_t *head )
{
 head_t *new_head = NULL;
 node_t *inode = NULL;
 node_t *bulk_list = NULL;
 int i = 0;
 assert(head!=NULL);
 new_head = (head_t *)malloc(sizeof(head_t));
 if( new_head == NULL ) {
 printf("ERR1:Out of memory\n");
 return NULL;
 }
 memcpy(new_head, head, sizeof(head_t));
 bulk_list = (node_t *)malloc(head->len * sizeof(node_t));
 if( bulk_list == NULL ) {
 printf("ERR2:Out of memory\n");
 return NULL;
 }
 new_head->first = bulk_list;
 i = 0;
 for( inode = head->first; inode != NULL; inode = inode->next ) {
 bulk_list[i] = *inode;
 if( i<head->len-1 ) 
 bulk_list[i].next = &bulk_list[i+1];
 else
 bulk_list[i].next = NULL;
 i++;
 }
 new_head->last = &bulk_list[i-1];
 new_head->len = i;
 return new_head;
}
// Detect a cycle in a list
bool detect_cycle( head_t *head, size_t *start_pos, size_t *cyc_len )
{
 node_t *slow=NULL, *fast=NULL;
 assert( head!= NULL && start_pos !=NULL && cyc_len!=NULL );
 slow = fast = head->first;
 // detect cycle
 do {
 slow = slow->next;
 fast = fast->next;
 if( fast==NULL ) 
 return false;
 else
 fast = fast->next;
 if( fast==NULL ) 
 return false;
 } while( slow!=fast );
 // find start position of cycle node
 *start_pos = 1;
 slow = head->first;
 do {
 slow = slow->next;
 fast = fast->next;
 (*start_pos)++;
 } while( slow!=fast );
 // find cycle len
 *cyc_len = 0;
 do {
 fast = fast->next;
 (*cyc_len)++;
 } while( slow!=fast );
 return true;
}
// Find minimum value in a list
node_t *find_min( head_t *head)
{
 node_t *inode=NULL, *min_node=NULL;
 int retval = 0;
 for( inode=min_node=head->first; inode!=NULL; inode=inode->next ) {
 retval = cmp_fn( &inode->data, &min_node->data);
 if( retval < 0 )
 min_node = inode;
 }
 return min_node;
}
// Find maximum value in a list
node_t *find_max( head_t *head)
{
 node_t *inode=NULL, *max_node=NULL;
 int retval = 0;
 assert( head!= NULL );
 for( inode=max_node=head->first; inode!=NULL; inode=inode->next ) {
 retval = cmp_fn( &inode->data, &max_node->data);
 if( retval > 0 )
 max_node = inode;
 }
 return max_node;
}
// Place a node in a list in sorted order (inc order=0, dec order = 1)
void insert_inorder( head_t *head, node_t *anode, int order )
{
 node_t *inode=NULL, *prevnode=NULL, *temp=NULL;
 int retval = 0;
 bool cmp_result = false;
 assert( head!= NULL );
 if( anode == NULL )
 return;
 for( inode=head->first; inode!=NULL; inode=inode->next ) {
 retval = cmp_fn( &anode->data, &inode->data );
 cmp_result = (order==0)? (retval<0): (retval>0);
 if( cmp_result )
 break;
 prevnode = inode;
 }
 // insert at front (including into an empty list)
 if( prevnode == NULL ) {
 if( head->first == NULL ) 
 head->last = anode;
 temp = head->first;
 head->first = anode;
 anode->next = temp;
 }
 // insert after prevnode (including at end)
 else {
 prevnode->next = anode;
 anode->next = inode;
 if( inode == NULL )
 head->last = anode;
 }
 head->len++;
}
// Sort a list using insertion sort
void insert_sort_list( head_t *head, int order )
{
 // pop items from given list and insert in order in a new list
 head_t new_head;
 node_t *temp_node = NULL;
 assert(head!=NULL);
 if( head->first == NULL || head->first->next == NULL ) 
 return;
 init_list( &new_head );
 while( (temp_node=remove_fromfront(head)) != NULL ) {
 insert_inorder( &new_head, temp_node, order);
 }
 head->first = new_head.first;
 head->last = new_head.last;
 head->len = new_head.len;
}
// Split an input list into two sublists with odd and even pos nodes
void split_alternate( head_t *head_in, head_t *head_o, head_t *head_e) 
{
 node_t *move_ptr = NULL;
 head_t *head_to = NULL;
 assert(head_in!=NULL && head_o!=NULL && head_e!=NULL);
 head_to = head_o;
 while( (move_ptr = remove_fromfront( head_in )) != NULL ) {
 insert_atend( head_to, move_ptr );
 if( head_to == head_o )
 head_to = head_e;
 else
 head_to = head_o;
 }
}
// Break an input list into two sublists with first half and second half
void split_list_half( head_t *head_in, head_t *head_f, head_t *head_b) 
{
 node_t *slow=NULL, *fast=NULL;
 assert(head_in!=NULL && head_f!=NULL && head_b!=NULL);
 init_list(head_f);
 init_list(head_b);
 slow = head_in->first;
 if( slow==NULL ) { // empty list
 return;
 }
 else if( slow->next == NULL ) { // one element list
 head_f->first = head_f->last = slow;
 head_f->len = 1;
 return;
 }
 fast = slow->next;
 head_f->len = 1;
 do {
 fast = fast->next;
 head_b->len = head_f->len;
 if( fast==NULL ) {
 break; // even number of nodes
 }
 else { 
 slow = slow->next;
 head_f->len++;
 fast = fast->next; 
 }
 } while( fast!=NULL );
 // slow points to the last node of the front half
 if( slow!=NULL ) {
 head_b->first = slow->next;
 slow->next = NULL;
 }
 head_b->last = head_in->last;
 head_f->first = head_in->first;
 head_f->last = slow;
 init_list(head_in);
}
// Merge two lists into one list by taking nodes from eahc list alternatively
void merge_list_alternate( head_t *head1, head_t *head2, head_t *head_out)
{
 node_t *move_ptr = NULL;
 head_t *head_from = NULL;
 assert(head_out!=NULL && head1!=NULL && head2!=NULL);
 head_from = head1;
 while( (move_ptr = remove_fromfront( head_from )) != NULL ) {
 insert_atend( head_out, move_ptr );
 if( head_from == head1 )
 head_from = head2;
 else
 head_from = head1;
 }
 if( head_from == head1 )
 head_from = head2;
 else
 head_from = head1;
 while( (move_ptr = remove_fromfront( head_from )) != NULL ) {
 insert_atend( head_out, move_ptr );
 }
}
// Compare first node of list1 with the first node of list 2 and return ptr to lesser/bigger node
node_t *compare_node( head_t *head1, head_t *head2, int order) 
{
 data_t *data1=NULL, *data2=NULL;
 int retval = 0;
 bool cmp_result = false;
 node_t *retnode = NULL;
 head_t *head_from=NULL;
 assert(head1!=NULL && head2!=NULL);
 data1 = check_at( head1, 1 );
 data2 = check_at( head2, 1 );
 if( data1!=NULL && data2!=NULL ) {
 retval = cmp_fn( data1, data2 );
 cmp_result = (order==0)? (retval<=0) : (retval>=0);
 head_from = cmp_result? head1: head2;
 }
 else if( data1==NULL ) 
 head_from = head2;
 else
 head_from = head1;
 retnode = remove_fromfront( head_from );
 return retnode;
}
// Merge two ordered list into one ordered list
void merge_list_inorder( head_t *head1, head_t *head2, head_t *head_out, int order)
{
 node_t *move_ptr = NULL;
 assert(head1!=NULL && head2!=NULL);
 init_list( head_out );
 while( head1->first!=NULL && head2->first!=NULL ) {
 move_ptr = compare_node( head1, head2, order );
 insert_atend( head_out, move_ptr );
 }
 if( head1->first==NULL )
 cat_list( head_out, head2 );
 else
 cat_list( head_out, head1 );
}
// Sort a list using merge sort, using recursion
void merge_sort_list( head_t *head, int order )
{
 head_t head_left, head_right;
 assert( head!=NULL );
 if( head->first == NULL )
 return;
 if( head->first == head->last )
 return;
 init_list( &head_left );
 init_list( &head_right );
 split_list_half( head, &head_left, &head_right );
 merge_sort_list( &head_left, order );
 merge_sort_list( &head_right, order );
 merge_list_inorder( &head_left, &head_right, head, order );
}
// Check if given list is sorted or not
bool is_list_sorted( head_t *head, int order ) 
{
 node_t *inode=NULL, *prevnode=NULL;
 int retval = 0;
 bool cmp_result = false;
 assert( head!=NULL );
 if( head->first == NULL || head->first == head->last )
 return true;
 prevnode = head->first;
 for( inode=prevnode->next; inode!=NULL; inode=inode->next ) {
 retval = cmp_fn( &prevnode->data, &inode->data );
 cmp_result = (order==0)? (retval>0):(retval<0);
 if( cmp_result ) 
 return false;
 prevnode = inode;
 }
 return true;
}
// Remove duplicate nodes in a sorted list
void unique_list( head_t *head, head_t *head_dup )
{
 node_t *prev_node=NULL, *inode=NULL, *dup_node=NULL;
 size_t pos=0;
 int retval = 0;
 assert( head!=NULL && head_dup!=NULL );
 if( head->first == NULL )
 return;
 if( head->first == head->last )
 return;
 init_list( head_dup );
 prev_node = head->first;
 inode = prev_node->next; 
 pos = 2;
 while( inode!=NULL ) {
 retval = cmp_fn( &inode->data, &prev_node->data );
 if( retval==0 ) { //inode same as prev_node
 dup_node = remove_at( head, pos);
 insert_atend( head_dup, dup_node );
 inode = prev_node->next;
 }
 else {
 prev_node = inode;
 inode = inode->next;
 pos++;
 }
 }
}
// Union and Intersection of two sorted lists, results are sorted & unique as well
size_t union_intersect_list( head_t *head1, head_t *head2, head_t *head_u, head_t *head_i, int order )
{
 size_t com_count = 0; // number of common nodes
 head_t *head1_copy=NULL, *head2_copy=NULL, *head1_dup=NULL, *head2_dup=NULL;
 node_t *move_ptr=NULL, *prev_move_ptr=NULL;
 bool match = false;
 int retval = 0;
 assert( head1!=NULL && head2!=NULL && head_u!=NULL && head_i!=NULL );
 // create a copy of the two lists so that they are not modifies
 head1_copy = (head_t *)malloc(sizeof(head_t));
 head1_dup = (head_t *)malloc(sizeof(head_t));
 head2_copy = (head_t *)malloc(sizeof(head_t));
 head2_dup = (head_t *)malloc(sizeof(head_t));
 // init all list headers for a clean start
 init_list( head1_copy );
 init_list( head1_dup );
 init_list( head2_copy );
 init_list( head2_dup );
 init_list( head_u );
 init_list( head_i );
 // remove duplicates as they would not be there in union or intersect outputs
 head1_copy = copy_list( head1 );
 head2_copy = copy_list( head2 );
 unique_list( head1_copy, head1_dup );
 unique_list( head2_copy, head2_dup );
 // free memory not needed anymore
 free_list(head1_dup);
 free_list(head2_dup);
 free(head1_dup);
 free(head2_dup);
 // take care of empty lists as inputs
 if( head1_copy->first==NULL && head2_copy->first==NULL ) {
 free( head1_copy );
 free( head2_copy );
 return com_count;
 }
 // compare the front nodes of two lists and insert them in 
 // union list if they are not matching with prev inserted node
 // else insert it to the intersection list
 move_ptr = compare_node( head1_copy, head2_copy, order );
 insert_atend( head_u, move_ptr );
 prev_move_ptr = move_ptr;
 while( head1_copy->first!=NULL || head2_copy->first!=NULL ) {
 move_ptr = compare_node( head1_copy, head2_copy, order );
 retval = cmp_fn( &move_ptr->data, &prev_move_ptr->data);
 if( retval == 0 ) {
 if( match == false ) {
 insert_atend( head_i, move_ptr );
 match = true;
 }
 com_count++;
 }
 else if( retval != 0 ) {
 insert_atend( head_u, move_ptr );
 match = false;
 prev_move_ptr = move_ptr;
 }
 }
 free( head1_copy );
 free( head2_copy );
 return com_count;
}

Answer 1

1. Broken code &max_node->data is &NULL->data. Undefined behavior to compute the address of members from a invalid pointer.

   node_t *inode=NULL, *max_node=NULL;
   for( inode=max_node=head->first; inode!=NULL; inode=inode->next ) {
    retval = cmp_fn( &inode->data, &max_node->data);
   

2. Heavy pollution of name space. CHAR, INT, etc. can very well collide with other code. Consider names less likely to collide.

   // typedef enum {
   // CHAR,
   // INT,
   /// UINT,
   typedef enum {
    VYLL_CHAR,
    VYLL_INT,
    VYLL_UINT,
   

3. Array sizing and indexing are best handled with type size_t. int may be insufficient for large applications. Code did use size_t in head_t

   typedef struct arr {
    data_t data[MAX_ARR_LEN];
    // int len;
    size_t len;
   } array_t;
   

4. As the header files used size_t, #include <stddef.h>, and maybe others, should be in that header file. Usage of a header file should not oblige .c code to do the including for it.

5. The .c file should your "linked_list.h" first to insure it does not require prior includes.

   #include "linked_list.h" 
   #include <stdio.h>
   #include <string.h>
   #include <inttypes.h>
   //#include "linked_list.h"
   

6. No need to assign twice in a row. Once is enoough

   // node_t *retptr = NULL;
   // retptr = (node_t *)malloc( sizeof(node_t) );
   node_t *retptr = (node_t *)malloc( sizeof(node_t) );
   

7. Cast not needed.

   node_t *retptr = malloc( sizeof(node_t) );
   

8. Better to determine size by the referenced variable than the type. Easier to code correctly, review and maintain.

   node_t *retptr = malloc(sizeof *retptr);
   head1_copy = malloc(sizeof *head1_copy);
   

9. Compare of int unnecessarily risks int overflow which is undefined behavior and limits useful range. Instead return 0,1,-1

   return d1->info.info_int - d2->info.info_int;
   return (d1->info.info_int > d2->info.info_int) - 
    (d1->info.info_int < d2->info.info_int);
   

10. With functions that do not alter referenced data, use const. This conveys functions intentions, allows for wider use and allows for some optimizations.

    // int cmp_fn( data_t *d1, data_t *d2)
    int cmp_fn(const data_t *d1, const data_t *d2)
    

11. bool used with prior #include <stdbool.h>. This (and other code) hints OP might be using a C++ compiler and not a C one.

12. get_fmt_str() is amiss in that it does not insure a null character at the end of the fmt[]. Add fmt_str[1] = '0円';

13. Rather than populate fmt_str[], better to return the format string.

    // static void get_fmt_str( char *fmt_str, info_t data_type ) static const char *get_fmt_str(info_t data_type) { switch( data_type ) { case CHAR: return "c"; case INT: return "d"; ...

14. Loose use of function names and types. In a large program, these names are not distinctive nor do they imply a commonality of use. is_empty(), array_t, cmp_fn(). Instead I'd expect a naming convention like vyll_is_empty(), vyll_array_t, vyll_cmp_fn().

14 Missing #include <assert.h>

15. Unclear why MAX_LIST_LEN is in the .C file and not the .h. No need to keep secret from other users.

16. Recommend to keep variable closer to their use

    // int retval = 0;
    ...
    for( inode=prevnode->next; inode!=NULL; inode=inode->next ) {
     // retval = cmp_fn( &prevnode->data, &inode->data );
     int retval = cmp_fn( &prevnode->data, &inode->data );
    

---

20. Advanced: first and last are not needed - so save space. last is enough. Could use last only and have it point to the first node. End of list then detected when n->next = last->next. This re-structures much of code. This is very useful when an application may have many empty lists.

• Vikas Yadav: Thanks a ton! #1: yes, need to make sure head->first is not NULL #2, #3. agree, i will change them. #4. stddef was included via linked_list.h that is why it is not in .c #5, #6, #7, #8, #9, #10. make sense, will update the code #11. using C compiler, stdbool.h is included in linked_list.h #12. agree.
• Vikas Yadav: contd. #13. get_fmt_str also returns non-standard values if data type is list or array or a pointer, so returning standard format string will not work. #14. ok #14. in linked_list.h i have '#ifdef DEBUGOK #define assert(CONDITION) \ if (CONDITION) { } else { \ printf ("Assertion `%s' failed.", #CONDITION); \ exit(-1); \ } #else #define assert(CONDITION) #endif'
• Vikas Yadav: #20. agree. one is used most of the time. i think last is only used to help in inserting at end and in concat two list.
• Vikas Yadav: #15. moved #define to header file #16. ok got it.. will try to optimize as much as possible.

Answer 2

node_t *retptr = NULL;
retptr = (node_t *)malloc( sizeof(node_t) );

Why not just node_t retptr = malloc( sizeof(node_t) );

In free_node() setting n = NULL does nothing because n is just local to the function. Whatever calls it still has a pointer to memory that has just been freed. In fact as a reviewer it "pricks my senses" and makes me wonder if you understand pointers - so I'd spend more time deeply reviewing because I'm now suspicious.

int cmp_fn() is using assert to check things that really don't belong in an assert. It should return "not match" in most of those conditions.

free_list() Why on earth would you make this recursive?

Nothing stops me inserting even after the list is full. Therefore return head->len == MAX_LIST_LEN; should really be return head->len >= MAX_LIST_LEN; otherwise it is misleading.

If you really want to remove from the front and the end, consider a doubly linked list? (Otherwise what is the real reason of keeping the end pointer at all?)

insert_at, remove_at etc can all be simplified by using find_at to locate the correct node (which may be the one before the one you need to play with. Why isn't insert_atfront just a call to insert_at(head, 0, anode)? I'm sure there are other similar cases.

I stopped here - in general my worst complain is too much assert - if you compile not in DEBUG mode behavior will be different (e.g. no checking for NULLs)

• John3136: If you found them useful an upvote is the traditional way to say thanks.
• Vikas Yadav: 1. The reason I had n=NULL in free_node is to let the program crash if it accesses freed memory without reallocation, isnt that safer than letting wrong memory used and corrupted due to developers mistake? 2. The recursive call is only needed for the case when list is a list of lists, in this case each node is of type list and I would need to call free_list instead of just free. Am I still missing something?
• Vikas Yadav: i did upvote but it does now show up.
• John3136: n is local to the function so as i said, it does nothing.
• Vikas Yadav: oh i see :) i missed that part (n is local).. what i want to do is the main var which is pointing to that mem in main code should be set to null. Thanks!