Getting rid of those casts

Getting rid of the casts...the basic trick is getting the Iterator to provide Nodes instead of Ts.

I don't really like creating the HasList interface, and someone out there could do better.  I did try to remove it...and nothing fun happened.

Given the time I tried banging my head on this, I'd say the conclusion that this sucks stands.

I want to write the three line tail recursive version; the Java devil is making me do it.

self.jump(shark);

head = new Reverser<Node<T>>(head).reverse();

public class Reverser<T extends HasList<T>> implements Iterable<T>{
 T curr;
 Reverser(T head) {this.curr = head;}
 @Override public Iterator<T> iterator() {return new RIterator<T>(this);}
 public T reverse() {
  return StreamSupport.stream(spliterator(), false)
    .reduce(null, (reversed, item) -> {return curr.attachToFrontOf(reversed);} );
 }
}

class RIterator<T extends HasList<T>> implements Iterator<T> {
 private Reverser<T> curr;
 private T rest;
 RIterator(Reverser<T> reverser) {
  this.curr = reverser;
  rest = reverser.curr;
 }
 @Override public boolean hasNext() {return rest != null;}
 @Override public  T next() {
  curr.curr = rest;
  return rest = rest.getRest();
 }
}

interface  HasList<T> {
    T attachToFrontOf(T n);
    T getRest();
}

class Node<T> implements HasList<Node<T>>{
 T val;
 Node<T> list;
 
 @Override public Node<T> attachToFrontOf(Node<T> n) {
  list = n;
  return this;
 }
 @Override public Node<T> getRest() {return list;}
 
}

The Ultimate Java 8 Linked List Reversal

Reversing a linked list...ah, the memories.  Losing that lucrative job offer because after 20 years someone thought I should have that on the tip of my tongue.  Whatever.

Well, indeed I can reverse a linked list, and it sucks.  In Java at least.

Here's what a Java 8 linked list reversal could look like:

class Node<T> {

    public Node<T> reverse () {return r(null);} 

    private Node<T> r(Node<T> reversed) {

        Node<T> rest = list;

        list = reversed;

        return rest == null ? this : rest.r(this);

    }

    T val;

    Node<T> list;

}

With the tail call optimization, that code takes O(1) space.

Since apparently no one wanted the tail call optimization, after adding an unhealthy dose of OOP, Java 8, Refactoring, and Patterns...what we have instead is:

public class Reverser<T> implements Iterable<T>{

    Node<T> n;

    Reverser(Node<T> n) {this.n = n;}

    @Override public Iterator<T> iterator() {return new RIterator<T>(this);}

    Node<T> setList(Node<T> reversed) {

        n.list = reversed;

        return n;

    }

    @SuppressWarnings("unchecked") public Node<T> reverse() {

        return (Node<T>) StreamSupport.stream(spliterator(), false)

            .reduce(null, (reversed, item) ->                                         (T)setList((Node<T>)reversed) );

    }

}

class RIterator<T> implements Iterator<T> {

    private Reverser<T> r;

    private Node<T> next;

    RIterator(Reverser<T> r) {

        this.r = r;

        next = r.n;

    }

    @Override public boolean hasNext() {return next != null;}

    @Override public  T next() {

        r.n = next;

        next = next.list;

        return null;

    }

}

I wish I was kidding.  And yes, the tests do pass.

Please no one else waste their time doing this.

Just write out the iterative algorithm in one method and forget about OOP.

Which I fear is pretty good advice in general.  Kingdom of the nouns indeed.

Next post...getting rid of those casts.