Cormen Edition 3 Exercise 10.2 Question 6 (Page No. 241)

Question

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.

Answer 1

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

Comments

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)