edited by
19,306 views
44 votes
44 votes

The concatenation of two lists is to be performed on $O(1)$ time. Which of the following implementations of a list should be used?

  1. Singly linked list

  2. Doubly linked list

  3. Circular doubly linked list

  4. Array implementation of list

edited by

5 Answers

Best answer
38 votes
38 votes

Option C ( Circular Doubly linked List)

Analyze below Code which is $O(1)$

Suppose List1's first element is pointed by pointer $p1$ 

And List2's first element is pointed by $p2$

And tmp is a temporary pointer of node type.

p1->prev->next = p2 ;

tmp= p2-> prev ;

p2-> prev= p1-> prev ;

p1-> prev = tmp;

tmp -> next = p1;

Options A&B of linked list are not possible in $O(1)$. Because they cannot find out rear element without doing a linear traversal.

For Option  D. Array implementation requires $O(n_1+n_2)$ copy operations where $n_1$ and $n_2$ represent the sizes of List1 and List2 respectively.

edited by
51 votes
51 votes
A) & B) Here it is not possble to do it in O(1) , unless we have pointer to end of one list. As we have not given that pointer, A & B are not option.

D) It is not possible to do here in O(1), because we will need to allocate memory for bigger array to hold both list & Copy it.

C) It is possible in O(1) as we can break list at any location & connect it anywhere. We don't need to traverse to end of anything here !
10 votes
10 votes
Answer is C. Since in all other options except the circular doubly linked list, we need to traverse the list to reach its end to attach the second list.
Answer:

Related questions

48 votes
48 votes
7 answers
3