Find the union and intersection of linkedlist, given that elements dont repeat in a single linkedlist. 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));
}
}