Find union and intersection of linked list

Question

Find the union and intersection of linked list, given that elements don't repeat in a single linked list.

This question is attributed to GeeksForGeeks. Looking for code-review, optimizations and best practices.

public class IntersectionAndUnionLinkedList<T> {
 private Node<T> first;
 private Node<T> last;
 private int size;
 public IntersectionAndUnionLinkedList() {}
 public IntersectionAndUnionLinkedList(List<T> items ) {
 for (T item : items) {
 add (item);
 }
 }
 public void add(T item) { 
 Node<T> node = new Node<T>(item);
 if (first == null) {
 first = last = node;
 } else {
 last.next = node;
 last = last.next;
 }
 size++;
 }
 private static class Node<T> {
 private T item;
 private Node<T> next;
 Node (T item) {
 this.item = item;
 }
 }
 public IntersectionAndUnionLinkedList<T> intersection(IntersectionAndUnionLinkedList<T> list) {
 final Set<T> items = new HashSet<>();
 Node<T> smallerListNode;
 Node<T> largerListNode;
 if (list.size < size) {
 smallerListNode = list.first;
 largerListNode = first;
 } else {
 smallerListNode = first;
 largerListNode = list.first;
 }
 while (smallerListNode != null) {
 items.add(smallerListNode.item); 
 smallerListNode = smallerListNode.next;
 } 
 IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
 while (largerListNode != null && items.size() > 0) { 
 if (items.contains(largerListNode.item)) {
 intersectionlist.add(largerListNode.item);
 items.remove(largerListNode.item);
 } 
 largerListNode = largerListNode.next;
 }
 return intersectionlist;
 }
 public IntersectionAndUnionLinkedList<T> union(IntersectionAndUnionLinkedList<T> list) {
 final Set<T> items = new HashSet<>();
 Node<T> smallerListNode;
 Node<T> largerListNode;
 if (list.size < size) {
 smallerListNode = list.first;
 largerListNode = first;
 } else {
 smallerListNode = first;
 largerListNode = list.first;
 }
 IntersectionAndUnionLinkedList<T> intersectionlist = new IntersectionAndUnionLinkedList<>();
 while (smallerListNode != null) {
 items.add(smallerListNode.item); 
 intersectionlist.add(smallerListNode.item);
 smallerListNode = smallerListNode.next;
 }
 while (largerListNode != null) { 
 if (!items.contains(largerListNode.item)) {
 intersectionlist.add(largerListNode.item);
 } 
 largerListNode = largerListNode.next;
 }
 return intersectionlist;
 }
 // size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
 public List<T> toList() {
 List<T> list = new ArrayList<>();
 if (first == null) return list;
 for (Node<T> x = first; x != null; x = x.next) {
 list.add(x.item);
 }
 return list;
 }
 @Override
 public int hashCode() {
 int hashCode = 1;
 for (Node x = first; x != null; x = x.next)
 hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
 return hashCode;
 }
 @Override
 public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 IntersectionAndUnionLinkedList<T> other = (IntersectionAndUnionLinkedList) obj;
 Node<T> currentListNode = first; 
 Node<T> otherListNode = other.first;
 while (currentListNode != null && otherListNode != null) {
 if (currentListNode.item != otherListNode.item) return false;
 currentListNode = currentListNode.next;
 otherListNode = otherListNode.next;
 }
 return currentListNode == null && otherListNode == null;
 }
}
public class IntersectionAndUnionLLTest {
 @Test
 public void intersection() {
 IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
 IntersectionAndUnionLinkedList<Integer> ll2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5, 6, 7));
 IntersectionAndUnionLinkedList<Integer> llExpected1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5));
 assertEquals(llExpected1, ll1.intersection(ll2));
 }
 @Test
 public void union() {
 IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
 IntersectionAndUnionLinkedList<Integer> ll2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(3, 4, 5, 6, 7));
 IntersectionAndUnionLinkedList<Integer> llExpected2 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
 assertEquals(llExpected2, ll1.union(ll2));
 }
 @Test
 public void intersectionNull() {
 IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
 IntersectionAndUnionLinkedList<Integer> ll3 = new IntersectionAndUnionLinkedList<>();
 IntersectionAndUnionLinkedList<Integer> llExpected3 = new IntersectionAndUnionLinkedList<>();
 assertEquals(llExpected3, ll1.intersection(ll3));
 }
 @Test
 public void unionNull() {
 IntersectionAndUnionLinkedList<Integer> ll1 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
 IntersectionAndUnionLinkedList<Integer> ll4 = new IntersectionAndUnionLinkedList<>();
 IntersectionAndUnionLinkedList<Integer> llExpected4 = new IntersectionAndUnionLinkedList<>(Arrays.asList(1, 2, 3, 4, 5));
 assertEquals(llExpected4, ll1.union(ll4));
 }
}

Answer 1

Intersection

it seems a little like cheating to me to use a HashSet here. I would probably write my own contains method for the linked list (which is bad for performance, but performance is not really the point here).

Other than that:

largerListNode != null

This check seems unnecessary. It's the larger list, after all. items.size() > 0 should always catch this.

Union

The return value should probably not be named intersectionlist :) It also does not do union. The code should look something like this:

 public IntersectionAndUnionLinkedList<T> union(IntersectionAndUnionLinkedList<T> list) {
 // ... in case this list should not be changed, copy it first. Otherwise, this list will be result of the union
 // traverse through the input list. add nodes from input list to beginning of this list
 Node listCurrentNode = list.first;
 while (listCurrentNode != null) {
 // ... if you do not want duplicate elements, check for them. or remove them at the end
 Node listNextNode = listCurrentNode.next;
 Node thisPreviousFirstNode = this.first;
 listCurrentNode.next = thisPreviousFirstNode;
 this.first = listCurrentNode;
 listCurrentNode = listNextNode;
 }
 return this;
}

Another (slower) approach would be to create a new list (the output list), and traverse both input lists one at a time, adding their elements to the new list (if it does not already contain the item).

General

The diamond operator is only supported since Java 7. So I would still use this:

Node<T> node = new Node<T>(item);

instead of this

Node<T> node = new Node<>(item);

if possible.

see also my answer here