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