Ace Test Series: Data Structures - Circular Linked List

Question

 

Comments

Big oh means in worst case it takes n but it can takes constant also , But Theata(n) means always takes n .

I try to explain in terms of number of comparision :

Theata(n) = Number of comaparision can be n-4,n-1, n-2, etc i.e. n assmptotically n.

O(n) means   Number of comaparision can be 1, ,2,3,4,4,5,5,6....n etc not garunteed n but we are sure it cannot go beyond n.

---

We can do it in O(1) also.

---

u will get turing award if u do it  even in logn

Answer 1

inserting new node  1st check node  rear node -->next is  front

it will take o(n)

Answer 2

Algorithm: we will add the new node in the second position, then swap the value of the first and second node.

Code:

Let k is a pointer to the new node which we going to insert. k->next = head->next., head->next = k. now swap(k->data, head->data).

{code for swap : temp = head->data; head->data = k->data; k->data =temp;}

Time complexity: O(1)

Comments

This is not worth in real practice.

let's assume,  A -> B -> C -> A

Somewhere in the program there's a reference to A.

Now if you insert D in that list as per your method, then that reference changed to D instead of A. This is the drawback of this method.

 

I don't know whether for exam purpose, this method can be used or not. But in real practice, using this method is not recommendable.

---

Thanks sir. You are right