The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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

asked in DS by Veteran (59.6k points)
edited by | 3.9k views

5 Answers

+16 votes
Best answer

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-> next ;

tmp -> next = p1

Option A&B of linked list are  not possible in $O(1)$. Bcz they cant find out rear element without doing linear  traversal.

For Option  D. Array implementation it requires $O(n1+n2)$ Copy operation where $n1$ represents size of List1.

answered by Boss (23k points)
edited by
Circular doubly linked list  not doubly linked list
Thanks. That was a typo. Now Corrected.
in 4th line of the code there should be

p1--->prev = temp;

is it correct?
why is p1->prev = temp -> next?

isn't temp->next pointing to p2?

so won't it be p1-> prev = temp?

(I think temp points to the last node of the second list )
+33 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 !
answered by Boss (43k points)
+9 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.
answered by Junior (513 points)
+5 votes

Image result for circular doubly linked list

Simply Option C is right

answered by Loyal (7.1k points)
+3 votes
answered by Loyal (5.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,599 answers
63,729 users