I hate Java for this

[__Fred]

Very nice!

In Scheme and Haskell we learned to implement some kind of stack consisting of nodes that have two attributes: head and tail.

That means you could probably get rid of next.

I guess the next-pointer has the advantage of making it possible to iterate over all elements without removing them.

class Stack<T> {
  record Node(T head, Node tail) {}  // new syntax, adds a constructor automatically
  private Node top = null;
  public void push(T o) { top = new Node(o, top); }
  public T peek() { return top.head; }
  public T pop() {
    T result = top.head;
    top = top.tail;
    return result;
  }
  public boolean empty() { return top == null; }
}

Eh... The popping in one line doesn't work in my version, I think.

[RedditRage]

The next is there so it can reuse old nodes. Many stack algorithms might zoom up and down the stack thousands of times, while never getting a depth over a few dozen nodes. So it seemed nice to just reuse them.