Posted on by Kalkicode

# Delete all the even nodes from a Doubly Linked List

The problem revolves around working with a doubly linked list and eliminating nodes that contain even values. A doubly linked list is a data structure where each node holds a value, a reference to the next node, and a reference to the previous node. The goal is to create a program that identifies nodes with even values and removes them from the linked list.

## Problem Statement

This task entails developing a program that accepts a doubly linked list as input, scans through each node's value, and removes nodes that contain even values. The challenge involves managing the adjustments in the linked list to maintain the connection after removal.

## Example

Given an example of a doubly linked list:

``Input: 8 <-> 1 <-> 4 <-> 9 <-> 5 <-> 3 <-> 12``

After removing nodes with even values (8, 4, 12), the updated linked list becomes:

``Output: 1 <-> 9 <-> 5 <-> 3``

## Idea to Solve

To solve this problem, a function should be implemented that iterates through the doubly linked list, checks if each node's value is even, and removes nodes that satisfy this condition. The algorithm should consider different cases such as removing the head node, adjusting pointers, and maintaining the list's integrity.

## Pseudocode

Below is the pseudocode representation of the algorithm to delete nodes with even values from the doubly linked list:

``````function deleteEvenNodes(dll):
while node is not null:
if node.data is even:
if node.next is not null:
node.next.prev = node.prev
if node.prev is not null:
node.prev.next = node.next
hold = node
node = node.next
hold.next = null
hold.prev = null
hold = null
else:
node = node.next``````

## Explanation of Algorithm

2. Check if the current node's value is even.
3. If the value is even, handle several cases:
• Remove the current node.
• Update pointers to maintain connectivity in the linked list.
• Free the memory of the removed node.
4. Move to the next node.
5. Repeat steps 2-4 until all nodes are traversed.

## Time Complexity

• The `deleteEvenNodes` function iterates through the entire linked list, and for each node, it performs constant time operations to adjust pointers and free memory.
• Overall, the time complexity of removing nodes with even values from the linked list is 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