Question

Write an algorithm that doubles ALL the prime values of a linked lists, and then output the whole new list.

Answer 1

Algorithm:-

I).Run a loop until next part of linked list node becomes NULL. in each pass of this loop check if the node in inspection is prime or not . If it is then just double it's value and replace the that Node's data with this doubled value.

Ii).After that prints the whole new list obtained in step I).

C-style pseudoCode:-

Let the algorithm is called doubledPrime( ) which takes address of linked list as input.

Linked list's node has two fields one for data and one for pointer which holds address of next node called next.

doubledPrime ( struct node *head)

{

if(head == NULL)// means linked list is empty

return

struct node *p //make another pointer just to store head so that it remains undisturbed.

p = head

While( p-> next ! = NULL)

{

if(prime(p->data )== 1)// means Node's data is prime

p-> data = 2*(p-> data)

p = p-> next

}

//Now , new list is obtained so we just need to print it.

p = head

while (p->next != NULL)

{

printf( p->data )

if(p->next != NULL)

Printf (" ->")

p = p->next

}

}

prime(n)

{

for (I = 2 to n/2)

{

if( n% I == 0)

return 1

}

return 0

}

Time complexity of above algorithm:-

The while loop runs for 'n' number of times where n is number of elements in linked list.in each pass of this loop it runs prime() algorithm which takes O( Node's data) in worst case.

So, in worst case all the node's in Linked list are prime then for each node in linked list we have to run prime algorithm fully which will takes O(node's data) time.

Suppose linked list contain d1 ,d2 , d3 ,....dn as data.

So, Time complexity = O(d1 ) + O(d2) + O(d3) + O(d4) +....O(dn) = O(d1 + d2 + d3 +....+dn)