4.7k views

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

4. Array implementation of list

in DS
edited | 4.7k views
0
+4
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.
0
Is it possible to concatenate using Circular Single Linked List in O(1) time?
+1

@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.

0
0
In doubly linked list how can u go to the last node of 1st list in O(1) time.

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
+1
0
Thanks. That was a typo. Now Corrected.
+3
in 4th line of the code there should be

p1--->prev = temp;

is it correct?
0
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 )
0
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)??
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)
0
Your answers are always easy to understand and to the point! Thanks :)
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)

Simply Option C is right

by Boss (11.2k points)
by Loyal (5.7k points)

1
2