Posted on by Kalkicode
Code Doubly linked list

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.

Before Delete all the even nodes from a Doubly Linked List After Delete all the even nodes from a Doubly 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):
    node = dll.head
    while node is not null:
        if node.data is even:
            if node is dll.head:
                dll.head = node.next
            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

  1. Start iterating through the linked list from the head.
  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.

Program List

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.

New Comment