2
\$\begingroup\$

The full question description is found http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/. Looking for code review, optimization, clean code etc.

public class CopyArbit<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    public CopyArbit() {}

    private static class Node<T> {
        T item;
        Node<T> next;
        Node<T> arbit;

        Node(T item, Node<T> next, Node<T> arbit) {
             this.item = item;
             this.next = next;
             this.arbit = arbit;
        }
    }

    public void add(T item) {
        final Node<T> l = last;
        final Node<T> newNode = new Node<T>(item, null, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    public void makeArbitrary (int srcPos, int destPos) {
        if (first == null) throw new NoSuchElementException("Linkedlist is empty.");

        if (srcPos > size || srcPos < 1) {
            throw new IllegalArgumentException("The srcPos  " + srcPos + " is out of bound");
        }

        if (destPos > size || destPos < 1) {
            throw new IllegalArgumentException("The destPos  " + destPos + " is out of bound");
        }

        Node<T> source =  getNodeAtPos(srcPos); 
        Node<T> destination =  getNodeAtPos(destPos);

        source.arbit = destination;
    }

    private Node<T> getNodeAtPos(int posFromStart) {
        assert posFromStart > 0 && posFromStart <= size;

        /*
         * We need (posFromStart - 1) hops to reach the node at that pos.
         */
        int hops = posFromStart - 1;
        int counter = 0;

        Node<T> temp = first;

        while (counter < hops) {
            temp = temp.next;
            counter++;
        }

        return temp;
    }

    public CopyArbit<T> getCopy() {
        Node<T> temp = first;

        // interject nodes in between each other.
        // ie convert A->B->C->D into A->A->B->B->C->C->D->D
        while (temp != null) {
            Node<T> tempAux = new Node<T>(temp.item, temp.next, null);
            temp.next = tempAux;
            temp =  temp.next.next;
        }

        // fill in the arbit pointer
        temp = first;
        while (temp != null) {
            Node<T> tempAux = temp.next;
            tempAux.arbit = temp.arbit.next;
            temp = temp.next.next;
        }

        return split();
    }

    private CopyArbit<T> split () {
        Node<T> temp = first;

        Node<T> first = null;
        Node<T> firstHead = null;
        Node<T> second = null;
        Node<T> secondHead = null;

        int counter = 0;

        while (temp != null) {
            if (counter % 2 == 0) {
                if (firstHead == null) {
                    firstHead = temp;
                } else {
                    first.next = temp;
                }
                first = temp;
            } else {
                if (secondHead == null) {
                    secondHead = temp;
                } else {
                    second.next = temp;
                }
                second = temp;
            }
            temp = temp.next;
            counter++;
        }
        first.next = null; // note this step.

        CopyArbit<T> copyArbit = new CopyArbit<T>();
        copyArbit.first = secondHead;
        copyArbit.last = second;
        copyArbit.size = size;

        return copyArbit;
    }

    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<T> {
        int currentSize;
        Node<T> node;

        LinkedListIterator() {
            currentSize = 0;
            node = first;
        }

        public boolean hasNext() {
            return currentSize < size;
        }

        public T next() {
            T item = node.item;
            node = node.next;
            currentSize++;
            return item;
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub
        }
    }

    public Iterator<T> arbitIterator() {
        return new LinkedListArbitIterator();
    }

    private class LinkedListArbitIterator implements Iterator<T> {
        int currentSize;
        Node<T> node;

        LinkedListArbitIterator() {
            currentSize = 0;
            node = first;
        }

        public boolean hasNext() {
            return currentSize < size;
        }

        public T next() {
            T item = node.arbit.item;
            node = node.next;
            currentSize++;
            return item;
        }

        @Override
        public void remove() {
            // TODO Auto-generated method stub
        }
    }

    public static void main(String[] args) {

        CopyArbit<Integer> source = new CopyArbit<Integer>();
        source.add(10);
        source.add(20);
        source.add(30);
        source.add(40);

        source.makeArbitrary(1, 4);
        source.makeArbitrary(2, 1);
        source.makeArbitrary(3, 4);
        source.makeArbitrary(4, 2);

        CopyArbit<Integer> target = source.getCopy();

        System.out.println("Expected: 40 10 40 20");
        System.out.print("Actual: ");

        Iterator<Integer> iterator = target.arbitIterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$
  1. I'd move the main method to a separate class. (For example, CopyArbitMain.) It's usually a good idea to separate a class from its clients.

  2. Iterator.remove() should throw UnsupportedOperationException if remove is not supported (according to the javadoc). Anyway, // TODO Auto-generated method stub comments usually a bad smell, don't leave them in the code.

  3. Instead of

    if (srcPos > size || srcPos < 1) {
        throw new IllegalArgumentException("The srcPos  " + srcPos + " is out of bound");
    }
    

    you could use Guava's checkArgument (or just create a similar method, if you don't want to include an external library):

    checkArgument(srcPos > size || srcPos < 1, "The srcPos %s is out of bound", srcPos);
    

    It's a little bit simpler and easier to read.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.