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

in DS by Veteran (52.1k points)
edited by | 4.7k 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.

Why doubly linked list is not the answer?
In doubly linked list how can u go to the last node of 1st list in O(1) time.

5 Answers

+23 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;

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.

by Boss (23.6k 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 )
Circular doubly linked list can do in O(1) time. right?? but not circular singly linked list. And it is because of head pointer can point even first element of list, while we r putting middle node in it. right??

But what about if it is a middle node of circular doubly linked list?? Can it be done in O(1) time?? Because it's distance from head can be n/2. So how it can be O(1)??
+39 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 !
by Boss (41.3k 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.
by (417 points)
+6 votes

Image result for circular doubly linked list

Simply Option C is right

by Boss (11.2k points)
+4 votes
by Loyal (5.7k 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
50,376 questions
55,811 answers
91,175 users