Java snippet implementing `bottomUp` for a linked stack

Question

I found this code example from a courseware that implements bottomUp for a linked stack class:

public class LinkedStack<E> implements Stack<E> {
    private int size;
    private Node<E> top;

    static class Node<E> {
        E elem;
        Node<E> next;

        Node(E elem, Node<E> node) {
            this.elem = elem;
            this.next = node;
        }
    }
 // omitted methods such as top()

    public void bottomsUp() {
        if (this.size < 2){
            return;}
        // move to the second last node in the stack
        Node<E> n = this.top;
        for (int i = 0; i < this.size - 2; i++){
            n = n.next;}
        // n.next is the current bottom node
        // attach it to the top node and make it the new top node
        Node<E> newTop = n.next;
        newTop.next = this.top;
        this.top = newTop;
        // n is the new bottom node; sever its next link
        n.next = null;
    }
}

My question:

The for loop basically sets n to the second last node of this.
For example, for the linked stack 1->2->3->4->null, the initial value of n is 3. But the snippet that follows confuses me:

It creates a new top 4->1, with value 4 and linked to the current top. So now the stack is

4     top 
1
2
3   the second last node, which is also the equal to `n` at this point
4   bottom
null

Then, it sets the n.next, in this case the bottom node, which has value 4, as null. So now the stack is

4     top 
1
2
3   the second last node, which is also the equal to `n` at this point
null   bottom
null

So the bottom becomes null, not 3. And this is the end of the method bottomUp.

• Why does this method leave two nulls in the bottom?
• Practically, how do i "find" a node which I can start from when using this Stack class?

I will really appreciate if anyone can this explain this snippet.

Answer 1

It creates a new top 4->1, with value 4 and linked to the current top.

That is where you went wrong. It doesn't create a new top. The assignment Node<E> newTop = n.next; doesn't call the Node constructor; it merely assigns a reference to newTop, so that now both newTop and n.next are references to the same node. The number of nodes doesn't increase:

 top                              n             newTop
  ↓                               ↓               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ elem: 1   │   │ elem: 2   │   │ elem: 3   │   │ elem: 4   │
│ next: ──────► │ next: ──────► │ next: ──────► │ next: null│
└───────────┘   └───────────┘   └───────────┘   └───────────┘

The next statement newTop.next = this.top; will replace the last null with a reference to the current top, temporarily creating a circular list (without any null):

     top                              n             newTop
      ↓                               ↓               ↓
    ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
    │ elem: 1   │   │ elem: 2   │   │ elem: 3   │   │ elem: 4   │
┌─► │ next: ──────► │ next: ──────► │ next: ──────► │ next: ─┐  │
│   └───────────┘   └───────────┘   └───────────┘   └────────│──┘
└────────────────────────────────────────────────────────────┘

The next assignment sets the top to what the newTop references, i.e. this.top = newTop;:

                                      n              top newTop
                                      ↓               ↓   ↓
    ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
    │ elem: 1   │   │ elem: 2   │   │ elem: 3   │   │ elem: 4   │
┌─► │ next: ──────► │ next: ──────► │ next: ──────► │ next: ─┐  │
│   └───────────┘   └───────────┘   └───────────┘   └────────│──┘
└────────────────────────────────────────────────────────────┘

We now need to break the circle again, by placing a null somewhere, which is what n.next = null; achieves. To quote what you wrote:

Then, it sets the n.next, in this case the bottom node, which has value 4, as null.

In other words, it sets the next field of the n node to null, and we get this:

                                      n              top newTop
                                      ↓               ↓   ↓
    ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
    │ elem: 1   │   │ elem: 2   │   │ elem: 3   │   │ elem: 4   │
┌─► │ next: ──────► │ next: ──────► │ next: null│   │ next: ─┐  │
│   └───────────┘   └───────────┘   └───────────┘   └────────│──┘
└────────────────────────────────────────────────────────────┘

And all is done now. At the end of the function the local variables newTop and n are discarded, and the above figure is then really the same as this one:

 top
  ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ elem: 4   │   │ elem: 1   │   │ elem: 2   │   │ elem: 3   │
│ next: ──────► │ next: ──────► │ next: ──────► │ next: null│
└───────────┘   └───────────┘   └───────────┘   └───────────┘

Now to your questions:

Why does this method leave two nulls in the bottom?

I hope the above illustrates that it doesn't do that.

Practically, how do i "find" a node which I can start from when using this Stack class?

This is done by the for loop. For instance, if instead of finding the one-but-last node, you need to find a node by its value, then make that a condition to break out of the loop.