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() + " ");
}
}
}