149 views

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

How is Ans D ?

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

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.
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.