The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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 (52k points)
edited by | 4.5k views
the biggest advantage of the circular doubly linked list is that to reach to the last element we need not have to traverse the whole linked list, we can reach to the last element by using the prev pointer of the head in O(1) time, as it's circular.
Is it possible to concatenate using Circular Single Linked List in O(1) time?

@Harshada No, because in a circular single linked list, the last node points to the first node, but the first node does not point to the last node, so we have to traverse the entire linked list to reach the last node in O(n) time.

5 Answers

+21 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 (23.4k points) 1 flag:
✌ Edit necessary (chauhansunil20th “p1-> prev = tmp-> next ; is not correct, it should be p1-> prev = tmp;”)

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 )
+37 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 (41k points)
Your answers are always easy to understand and to the point! Thanks :)
+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 (417 points)
+6 votes

Image result for circular doubly linked list

Simply Option C is right

answered by Boss (10.5k points)
+4 votes
answered by Loyal (5.6k 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
49,540 questions
54,099 answers
71,006 users