Posted on by Kalkicode

# Remove all even parity nodes from a circular doubly linked list

In this problem, we are dealing with a circular doubly linked list that contains integer values. The task is to remove nodes from the circular doubly linked list that have an even parity of set bits in their binary representation.

## Problem Statement and Description

The problem requires us to remove nodes from the circular doubly linked list based on a specific condition. We need to identify the nodes whose binary representation has an even number of set bits (bits with a value of 1) and remove them while maintaining the circular doubly linked structure of the list.

## Example

Let's understand the problem with an example. Consider the following circular doubly linked list:

``````Original Circular Doubly Linked List:
From Front to Tail: 3 -> 12 -> 32 -> 14 -> 27 -> 19 -> 1 -> 18
From Tail to Front: 18 -> 1 -> 19 -> 27 -> 14 -> 32 -> 12 -> 3``````

After removing nodes with even parity of set bits, the circular doubly linked list should look like this:

``````Modified Circular Doubly Linked List:
From Front to Tail: 32 -> 14 -> 19 -> 1
From Tail to Front: 1 -> 19 -> 14 -> 32``````

## Idea to Solve

To solve this problem, we can follow these steps:

1. Traverse the circular doubly linked list using the `temp` pointer.
2. For each node, calculate the number of set bits (bits with a value of 1) in its binary representation using the `coutSetBit` function.
3. Check if the count of set bits is even. If it is, mark the node for removal.
4. Traverse the circular doubly linked list again using the `temp` pointer, this time with the objective of removing the marked nodes.
5. Depending on whether the current node (`auxiliary`) is the front, tail, or an intermediate node, remove the node from the list while maintaining the circular doubly linked structure.

## Pseudocode

``````removeNode():
if front is null:
return
initialize temp as front
initialize auxiliary as front

while temp is not null:
if coutSetBit(temp.data) is even:
auxiliary = temp
temp = temp.next
if auxiliary is front:
// Remove front node
if auxiliary is tail:
// Removing a single node
tail = null
front = null
temp = null
else:
front = temp
front.back = tail
tail.next = temp
else if auxiliary is tail:
// Remove tail node
auxiliary.back.next = front
front.back = auxiliary.back
tail = auxiliary.back
else:
// Remove intermediate node
auxiliary.back.next = auxiliary.next
auxiliary.next.back = auxiliary.back
auxiliary = null
else:
// visit to next node
temp = temp.next
if temp is front:
// Stop the process
temp = null``````

## Algorithm Explanation

1. Traverse the circular doubly linked list using the `temp` pointer.
2. Calculate the number of set bits in the binary representation of the current node's data using the `coutSetBit` function.
3. Check if the count of set bits is even. If it is, mark the current node for removal.
4. Depending on whether the current node (`auxiliary`) is the front, tail, or an intermediate node, remove the node from the list while maintaining the circular doubly linked structure.
5. If the current node's data doesn't have an even number of set bits, move `temp` to the next node.
6. If `temp` has reached back to the front, terminate the loop by setting `temp` to null.

## Time Complexity

1. In the `coutSetBit` function, the number of set bits is counted using bitwise operations. This operation is executed in constant time, regardless of the input value. Thus, the time complexity of the `coutSetBit` function is O(1).

2. In the `removeNode` function, we traverse the circular doubly linked list once to identify nodes with even parity of set bits and then again to remove these nodes. Both traversals have a time complexity of O(N), where N is the number of nodes in the linked list.

## 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.

Categories
Relative Post