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

Question

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?

Answer 1

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

Answer 2

Just in case we don't have the tail pointer at hand (actually a common case for linked lists...), we cannot UNION the two lists in O(1), since we have to traverse one of the list to get its tail pointer, which takes O(n).

In this case, with only two head pointers at hand, the "suitable list data structure" has to be a doubly circular linked list. We disconnect the link between the head element of LIST_1 and its next element, and disconnect the link between the head element of LIST_2 and its prev element. Then we connect the two head elements and connect the other two elements. Thus, we get another doubly circular linked list, and the "pointer flow" is kept (which is why we shouldn't disconnect the head element of LIST_2 with its next element).

Answer 3

In the question that you mentioned it's written that we can use any suitable list data structure ( the answer that you have given considers a pointer to tail as well, which is not necessary unless you want to do it using a singly linked list in O(1) and generally we consider only the concept of head node when we talk about linked lists ) thus we will use doubly circular linked list. Now we have to join the 2 sets so we can do the following operations to achieve it in O(1)

(headS1->prev)->next = headS2;
temp = headS1->prev;
(headS2->prev)->next = headS1 ;
headS1->prev = headS2->prev ;
headS2->prev = temp;