How is Ans D ?

Was thinking it should be B or C ..

Was thinking it should be B or C ..

Dark Mode

149 views

1 vote

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

- array implementation of list
- doubly linked list
- singly linked list
- circular doubly linked list

D is correct, read this thread

http://stackoverflow.com/questions/25938499/linked-list-concatenation-in-o1-time

0

1 vote

Best answer

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.

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