Posted on by Kalkicode

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

``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:

``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):
while node is not null:
if node.data is divisible by key:
if node is the head node:
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

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.

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

Categories
Relative Post