retagged by
2,962 views
6 votes
6 votes
Time complexity to insert a node in the end of circular linked list, if the pointer to the 1st node is given and number of nodes in list is N

is

A)O(1)

B)O(log N)

C)O(N)

D)O(N log N)
retagged by

2 Answers

Best answer
12 votes
12 votes

Logic for the given procedure is 1st node of circular linked list.

That is not sure, because any node can be the head node. After all, If a middle node is head node, then again its a circular linked list. In memory, a $CLL$ is stored like a circular queue.


  • Let the $CLL$ with head node as a node having element $5$ be :


  • Add a New node $N$ as follows in $O(1)$ time :


  • Swap the Data $N$ and $5$ in O(1) time as :


  • Now, again make Node having $5$ as head node in O(1) time as :


  • Now, the new CLL is as follows :


  • All the steps are in total done in $O(1)$ time.
selected by
1 votes
1 votes
It can be done in O(N) because we have to traverse till the last node.

Answer will be : O( N ) 


// Pseudo_code

node* addAtEnd(node *head , node *n) {
  //If list is empty
  if(head == NULL) {
    //making the new Node as Head
    head = n;
    //making the next pointer of the new Node as Null
    n->next = NULL;
  }
  else {
    //getting the last node
    node *last = getLastNode();   // assume this function  return the pointer to the last node
     last->next = n;
    //making the next pointer of new node point to head
    n->next = head;
  } 
return head;
}

Related questions

0 votes
0 votes
0 answers
4
Rahul Jain25 asked Nov 5, 2016
480 views
I am not getting how unsigned is used and how is it working???