complexity

Question

1) Time complexity to insert a node in the end of circular linked list, if pointer to first node is given and the number of nodes in the list is N, is

1) O(1)

2)O(log N)

3)O(N)

4)O(N log N)

Comments

O(n) since last node points to first .. We insert new node at first position.. But last node points to old one... We need to change it to new first node..for that we need to traverse till the last node...

---

If we insert new node at last even though we need to traverse till the end point...

---

It takes O(1) only , when rear pointer is given.

If they are giving a head pointer, then deletion / insertion at start/ end takes O(n) only.

Answer 1

1) Add a node after first node, call it NewNode. 

2) Swap the firstNode's and NewNode's data.

3) Now change head pointer to point to head->next.

.

The head node is still 1 and we have just inserted the last node without travelling the entire node... So the time comoplexity is O(1)..

                                                                                 Authors- Vivek14 and Hirak

Answer 2

Since our pointer is pointing at the first node,hence we have to traverse till the end.

hence complexity is O(N).