in Algorithms
579 views
1 vote
1 vote
The dynamic-set operation $UNION$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S=S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2$.The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support  $UNION$ in $O(1)$ time using a suitable list data structure.
in Algorithms
579 views

1 Answer

0 votes
0 votes

we should follow this type of approach  like

S1:
A1->A2->A3

S2:
B1->B2->B3

Tail node of S1 (A3) linked to head node of S2 (B1)

S1US2:
A1->A2->A3*->*B1->B2->B3

1 comment

Take two 2-way linked lists. one representing S1 and another S2. Both the lists having FORW and PREV pointers. Since its given that the sets are disjoint so simply concatenate the two lists. Time taken will be  O(1)
0
0

Related questions