Linked List Implementation using dummy nodes

Question

I am working on a project where i have to union and intersect two sets. I am using Linked list for each set with dummy nodes. This is how i initialize my Sets LL class

public Set() {
 top = new Node(Integer.MIN_VALUE, new Node(Integer.MAX_VALUE, null) );
} //end Set

And this is how i insert items.

public void insert(int item) {
 Node prev = top;
 Node curr = top.next;

 while( curr.item < item ) {
  prev = curr;
  curr = curr.next;
 }
 prev.next = new Node( item, curr);
 size++;
} // insert

Now i am finding it hard to get a union or intersection of two sets. This is what i have in mind for intersection.

public Set intersection( Set setB ) {
 Set setC = new Set ();
 //loop over both sets and if both have same value add it otherwise 
 // get to the next node in both sets.

My question is, am i logically correct with the intersection pseudocode? My union pseudocode is laughable though. Can anyone please guide me though this problem?

Answer 1

Your idea will fail for this simple input:

1  2
2  3

Your idea:

//loop over both sets and if both have same value add it otherwise 
// get to the next node in both sets.

• First iteration - we have 1 and 2, not same value, so we get to the next in both sets
• Second iteration - we have 2 and 3, not same value, so get to next
• End

What you actually need is:

• On mismatch, advance only the list with lower element
• On match, add to result and advance both (or to remove duplicates, keep advancing both as long as the same value is repeating)

---

For union, the idea is very similar:

• On mismatch, add the lower one and advance the list that contained the lower element
• On match, add and advance both (or keep advancing both as long as the same value is repeating)