Skip to main content

Delete all even parity nodes from circular linked list in c

C program for Delete all even parity nodes from circular linked list. Here problem description and explanation.

// Include header file
#include <stdio.h>
#include <stdlib.h>

// C program for
// Remove all even parity nodes from a circular single linked list
typedef struct LinkNode
{
	// Define useful field of LinkNode
	int data;
	struct LinkNode * next;
}LinkNode;

LinkNode * getLinkNode(int data)
{
	// Create dynamic memory of LinkNode
	LinkNode * ref = (LinkNode * ) malloc(sizeof(LinkNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->data = data;
	ref->next = NULL;
	return ref;
}
typedef struct CircularLinkedList
{
	// Define useful field of CircularLinkedList
	struct LinkNode * head;
	struct LinkNode * tail;
}CircularLinkedList;

CircularLinkedList * getCircularLinkedList()
{
	// Create dynamic memory of CircularLinkedList
	CircularLinkedList * ref = 
      (CircularLinkedList * ) malloc(sizeof(CircularLinkedList));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set initial value
	ref->head = NULL;
	ref->tail = NULL;
	return ref;
}
void insert(CircularLinkedList * ref, int value)
{
	LinkNode * node = getLinkNode(value);
	if (ref->head == NULL)
	{
		ref->head = node;
	}
	else
	{
		ref->tail->next = node;
	}
	node->next = ref->head;
	ref->tail = node;
}
// Display node element of circular linked list
void display(CircularLinkedList * ref)
{
	if (ref->head == NULL)
	{
		printf("\n Empty Linked List");
	}
	else
	{
		printf("\n Linked List Element \n");
		// First node of linked list
		printf(" %d ", ref->head->data);
		LinkNode * temp = ref->head->next;
		// Display linked list node
		while (temp != NULL && temp != ref->head)
		{
			// Display node value
			printf(" %d ", temp->data);
			// Visit to next node
			temp = temp->next;
		}
	}
}
// Handles the request to find set bits in given integer
int coutSetBit(int num)
{
	int result = num;
	result = result - ((result >> 1) & 1431655765);
	result = (result & 858993459) + ((result >> 2) & 858993459);
	result = (result + (result >> 4)) & 252645135;
	result = result + (result >> 8);
	result = result + (result >> 16);
	result = result & 63;
	return result;
}
void removeNode(CircularLinkedList * ref)
{
	if (ref->head == NULL)
	{
		return;
	}
	LinkNode * temp = ref->head;
	LinkNode * auxiliary = ref->head;
	LinkNode * point = NULL;
	while (temp != NULL)
	{
		if (coutSetBit(temp->data) % 2 == 0)
		{
			auxiliary = temp;
			// Visit to next node
			temp = temp->next;
			if (auxiliary == ref->head)
			{
				// Remove head node
				if (auxiliary == ref->tail)
				{
					// Removing a single node
					ref->tail = NULL;
					ref->head = NULL;
					temp = NULL;
				}
				else
				{
					ref->head = temp;
					ref->tail->next = temp;
				}
			}
			else if (auxiliary == ref->tail)
			{
				if (point != NULL)
				{
					// When Remove last node
					point->next = ref->head;
				}
				ref->tail = point;
			}
			else
			{
				if (point != NULL)
				{
					// When Remove last node
					point->next = temp;
				}
			}
          	free (auxiliary);
			auxiliary = NULL;
		}
		else
		{
			point = temp;
			// Visit to next node
			temp = temp->next;
			if (temp == ref->head)
			{
				// Stop the process
				temp = NULL;
			}
		}
	}
}
int main()
{
	CircularLinkedList * cll = getCircularLinkedList();
	// Insert node
	insert(cll, 3);
	insert(cll, 12);
	insert(cll, 32);
	insert(cll, 14);
	insert(cll, 27);
	insert(cll, 19);
	insert(cll, 1);
	insert(cll, 18);
	printf("\n Before Remove ");
	display(cll);
	/*
	    Node  Binary     Even Parity
	     3     (11)         Yes
	    12     (1100)       Yes
	    32     (100000)     No
	    14     (1110)       No
	    27     (11011)      Yes
	    19     (10011)      No
	    1         (1)       No        
	    18     (10010)      Yes
	*/
	removeNode(cll);
	printf("\n\n After Remove");
	display(cll);
}

Output

 Before Remove
 Linked List Element
 3  12  32  14  27  19  1  18

 After Remove
 Linked List Element
 32  14  19  1




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment