CODEWITHSUNDEEP
algorithmdata-structuresdiscriminated-union
Daket
Daket

Reputation: 29

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?

Upvotes: 2

Views: 2563

Answers (4)

Nouman Mughal
Nouman Mughal

Reputation: 1

Here is the code given below to the following problem. I uses this approach to tackle this problem class Node: def init(self, data): self.data = data self.next = None

class LinkedList: def init(self): self.head = None self.tail = None

def is_empty(self):
    return self.head is None

def append(self, data):
    new_node = Node(data)
    if self.is_empty():
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node

def union(set1, set2): # Create a new linked list to store the union of set1 and set2 union_set = LinkedList()

# If set1 is not empty, append its elements to the union_set
if not set1.is_empty():
    union_set.head = set1.head
    union_set.tail = set1.tail

# If set2 is not empty, append its elements to the union_set
if not set2.is_empty():
    if union_set.is_empty():
        union_set.head = set2.head
        union_set.tail = set2.tail
    else:
        union_set.tail.next = set2.head
        union_set.tail = set2.tail

# Destroy the input sets by setting their head pointers to None
set1.head = None
set2.head = None

return union_set

Example usage

set1 = LinkedList() set1.append(1) set1.append(2)

set2 = LinkedList() set2.append(3) set2.append(4)

union_set = union(set1, set2)

Print the elements in the union set

current = union_set.head while current: print(current.data) current = current.next

Upvotes: 0

Ashish Chawla
Ashish Chawla

Reputation: 1

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;

Upvotes: 0

Qiyu Wu
Qiyu Wu

Reputation: 11

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

Upvotes: 1

Justin
Justin

Reputation: 4216

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

Upvotes: 0

Related Questions