edited by
364 views
1 votes
1 votes

The concatenation of $2$ lists is to be performed in $O(1)$ time. Which of the following implementations should be used?

  1. array implementation of list
  2. doubly linked list
  3. singly linked list
  4. circular doubly linked list
edited by

1 Answer

Best answer
1 votes
1 votes
To concatenate u should have have both the head and tail pointer,u have it in circularly doubly linked list.

For Singly,Doubly LL,Array implementation of LL we need O(min(m,n)) time as we need to get hold of tail one of the lists in order to concatenate it with another.
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,641 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
3
0 votes
0 votes
0 answers
4