[SOLVED] dynamic-set operation UNION takes two disjoint sets S1 and S2 as input

dynamic-set operation UNION takes two disjoint sets S1 and S2 as input

This is my homework question i have tried to solve it just need someone to look and tell me if i am doing it right or worng..

The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns a set S = S1 U S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usually destroyed by the operation. Show how to support UNION in O(1) time using a suitable list data structure

I am thinking of having two linked lists which can be done in constant time but for that we need to remember a pointer to both first(head) and last(tail) element of list. struct node{ char* word; struct node* next; } struct Set{ struct node* head; struct node* tail; } For every list beside with the head pointer we'll also keep a tail pointer. Supporting union operation in O(1) time: Suppose we've two Sets S1 and S2.

   PSEUDO-CODE:
            node* Union(Set S1,Set S2){
                  S1.tail->next = S2.head;
                  S1.tail = S2.tail;
                  Remove S2 from the list of sets;
                  return S1;
            }

is my approach going in right direction?

Solution

Yea, that's the same approach I'd take.

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