Skip to main content

Delete all nodes which are divisible by X in doubly linked list

The problem involves deleting all nodes from a doubly linked list that are divisible by a given key. A doubly linked list is a data structure in which each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. The task is to remove all occurrences of nodes whose data values are divisible by a specified key.

Problem Statement

Given a doubly linked list, the goal is to remove all nodes whose data values are divisible by a given key. After performing the deletion, the updated doubly linked list should be displayed.

Example

Consider the following doubly linked list:

Before delete  nodes which are divisible by X
6 <-> 1 <-> 4 <-> 9 <-> 5 <-> 3 <-> 12

Let's say the given key is 3. After removing all nodes whose data values are divisible by 3, the resulting doubly linked list should be:

After delete  nodes which are divisible by X
1 <-> 4 <-> 5

Idea to Solve

To solve this problem, we can iterate through the doubly linked list while checking each node's data value. If the data value is divisible by the given key, we remove that node from the list. To do this, we update the pointers of the previous and next nodes to bypass the current node.

Pseudocode

function deleteDivisibleByKey(key):
    node = head
    while node is not null:
        if node.data is divisible by key:
            if node is the head node:
                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
            temp = node
            node = node.next
            temp.next = null
            temp.prev = null
        else:
            node = node.next

Algorithm Explanation

  1. Start with the head node.
  2. Traverse through the linked list:
    • If the data value of the current node is divisible by the key:
      • Update the pointers of the previous and next nodes to skip the current node.
      • Delete the current node by updating its next and prev pointers and setting them to null.
    • Move to the next node.
  3. Repeat this process until you have checked all nodes in the linked list.

Code Solution

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. This is because in the worst case, we iterate through all the nodes once to check their data values and perform the deletion operation.





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