circular linked list_doubt

Question

Given a head pointer what is the time complexity:

1. To insert the element at front

2.To delete the element at front

3.To insert the element at end

4.To delete the element at front

5.To insert the element at the middle

To delete the element at the middle

Answer 1

Given that circular single linked list

a) To insert element at front  =  O(1)   [  Just involves head pointer ]

b) To delete element at the front  =  O(1)  [ Just involves head pointer ]

c) To insert the element at the end = O(n) [ Since we are given only head pointer only ]

d) To delete element at the end  =  O(n) [ Same as in c) ]

e) To insert element at the middle  = O(n) [ As we need to go to middle hence O(n) ]

f) To delete element at the middle = O(n) [ Same as in e) ]

Comments

thanks habib...but how can we access the 1st node using the left of 1st node..it's not a double LL ,It is single LL in circular form

I think it will be O(n) to insert and delete at the end in case of circular linear linked list

and to delete at the front we can use copy to do in O(1)...ryt?

can u plz write logic for insert and delete at front

---

Ok I assumed it for circular double linked list..Correcting it..

---

it will be O(1) for 

To insert the element at the end

and

To delete element at the end  

See here https://gateoverflow.in/104775/ds-cll