Skip to main content

Delete all Prime Nodes from a doubly linked list

The given problem involves working with a doubly linked list and deleting all nodes with prime values from the list. A doubly linked list is a data structure where each node contains a value, a reference to the next node, and a reference to the previous node. The problem requires designing a function to delete all nodes with prime values from the doubly linked list.

before delete prime nodes in Doubly Linked List After delete prime nodes in Doubly Linked List

Problem Statement

The problem is to write a program that takes a doubly linked list as input, searches for nodes with prime values, and removes those nodes from the list while maintaining the integrity of the list.

Example

Let's take a sample doubly linked list as an example:

Input: 7 <-> 2 <-> 3 <-> 9 <-> 5 <-> 6 <-> 11

After removing the prime nodes:

Output: 9 <-> 6

Idea to Solve

To solve this problem, we need to implement a function that iterates through the linked list, checks if the value of each node is prime, and if so, removes the node from the list. We'll need to handle different cases, such as removing the head node or an intermediate node, while adjusting the pointers to maintain the connections between nodes.

Pseudocode

Here's a pseudocode representation of the algorithm to delete prime nodes from the doubly linked list:

function deletePrime(dll):
    current = dll.head
    while current is not null:
        if isPrime(current.data):
            if current is dll.head:
                dll.head = current.next
                if dll.head is null:
                    dll.tail = null
                else:
                    dll.head.prev = null
            else:
                current.prev.next = current.next
                if current.next is null:
                    dll.tail = current.prev
                else:
                    current.next.prev = current.prev
            temp = current
            current = current.next
            free(temp)
        else:
            current = current.next

Explanation of Algorithm

  1. Start iterating through the linked list from the head.
  2. Check if the current node's data is prime using the isPrime function.
  3. If the data is prime, handle two cases:
    • If the current node is the head, update the head pointer and adjust pointers accordingly.
    • If the current node is not the head, adjust pointers to remove the node from the list.
  4. Free the memory of the prime node.
  5. Move to the next node.
  6. Repeat steps 2-5 until all nodes are traversed.

Program List

Time Complexity

  • The isPrime function checks whether a number is prime, which takes O(sqrt(n)) time in the worst case.
  • The deletePrime 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 deleting all prime nodes from the linked list is O(n * sqrt(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