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.


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
- Start iterating through the linked list from the head.
- Check if the current node's data is prime using the
isPrime
function. - 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.
- Free the memory of the prime node.
- Move to the next node.
- Repeat steps 2-5 until all nodes are traversed.
Program List
-
1) Delete all prime nodes in doubly linked list in c
2) Delete all prime nodes in doubly linked list in java
3) Delete all prime nodes in doubly linked list in c++
4) Delete all prime nodes in doubly linked list in golang
5) Delete all prime nodes in doubly linked list in c#
6) Delete all prime nodes in doubly linked list in vb.net
7) Delete all prime nodes in doubly linked list in php
8) Delete all prime nodes in doubly linked list in node js
9) Delete all prime nodes in doubly linked list in typescript
10) Delete all prime nodes in doubly linked list in python
11) Delete all prime nodes in doubly linked list in ruby
12) Delete all prime nodes in doubly linked list in scala
13) Delete all prime nodes in doubly linked list in swift
14) Delete all prime nodes in doubly linked list in kotlin
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.
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