in Programming edited by
149 views
1 vote
1 vote

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
in Programming edited by
by
149 views

4 Comments

How is Ans D ?

Was thinking it should be B or C ..
0
0
0
0
ok ..
so traversal till the end of a SLL or a DLL will take time .. that y its D ..
1
1
yes :)
0
0

1 Answer

1 vote
1 vote
Best answer
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

1 comment

problems with array implementation

 

See if you have 5 elemnts lying in one array and say 10 in another then in order to put those 5 in the array of 10 elemnts (optimal decision), you need to traverse the array of 5 elemnts completely and put them one by one in 2nd array starting from 10th to 14th position--->O(m) time m<n.
0
0
Answer:

Related questions