0 votes 0 votes What is the time complexity to insert a new Node in a singly circular linked list at Starting ? (Number of nodes in list = N) A. O(1) B. O(N) Programming in C ace-test-series linked-list data-structures + – Mr_22B asked Dec 10, 2017 • edited Mar 7, 2019 by Rishi yadav Mr_22B 2.3k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Ashwani Kumar 2 commented Dec 10, 2017 reply Follow Share An efficient implementation will take O(1) time. 0 votes 0 votes Ashwin Kulkarni commented Dec 10, 2017 reply Follow Share This will take O(1) time. add node to next of head. copy head data to new node add new data to old head 2 votes 2 votes Mr_22B commented Dec 10, 2017 reply Follow Share Yes, I have also selected O(1) but ACE test says ans is O(N). 0 votes 0 votes Ashwin Kulkarni commented Dec 10, 2017 reply Follow Share Nop they have given it wrong. you are correct. 1 votes 1 votes hs_yadav commented Dec 10, 2017 reply Follow Share O(1) is correct...bcoz pointer for initial node is already known ....no need to traverse..... 1 votes 1 votes Deepak Kumar 12 commented Dec 12, 2017 reply Follow Share Answer-O(n) bcz in question only say about insert at starting of list (http://vle.du.ac.in/mod/book/view.php?id=5704&chapterid=2629) 0 votes 0 votes prudhvi86 commented Jan 3, 2018 reply Follow Share if the head pointer is known we can add a node after that head pointer but not before it.So we need to traverse it till the tail...keep a pointer to it and and it after tail and make the new node as head :) Hope this helps. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes O(N) is the answer because it is single circular linked list so adding a node at star will take constant time but last node point to new node which is inserted so for this linked we should go to last node which take N time Nitesh Choudhary answered Dec 11, 2017 Nitesh Choudhary comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments hs_yadav commented Dec 12, 2017 reply Follow Share @Nitesh Choudhary as last node will hold the address of first node means point to the head pointer.... now during the insertion of new node we will change head pointer to the new one ...as a result head will point to the new node as well as last node will also point to head node....... i think her no need to...traverse cahnge the last node->next address.....????? 0 votes 0 votes Mr_22B commented Dec 13, 2017 reply Follow Share @saxena what if it contains $2^{N}$ elements. 0 votes 0 votes ajay10 commented Dec 17, 2018 reply Follow Share @Nitesh Chaudhary Is the answer is 0(n) or thetha(n)? because i had marked ans as 0(n) but in the key its wrong and the actual answer is thetha(n). if the anwer is thetha(n) then how we will come to know this we have to mark thetha(n) not the 0(n)? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes If you have pointer to the first node Insertion at beginning: O(n) Insertion at the end: O(n) // As you have to traverse till the end. If you have pointer to the last node Insertion at beginning: O(1) Insertion at end: O(1) Check this: https://gateoverflow.in/1033/gate2004-36 smsubham answered Feb 12, 2018 • edited Apr 30, 2018 by smsubham smsubham comment Share Follow See 1 comment See all 1 1 comment reply Shivam Patidar commented Dec 20, 2018 reply Follow Share I think complexity depends on the position of pointers given. But here no specification about any front or rear pointer so we will consider the worst case i.e pointer is pointing to first node.Then T.C - 1) For insertion at beginning O(n) 2) insertion at the end O(n). And if you will consider the pointer which is pointing to last node .Then T.C - 1) For insertion at beginning O(1) 2) insertion at the end O(1). I Hope you got my point.. 0 votes 0 votes Please log in or register to add a comment.