I
I
iscateli2021-12-27 23:09:53
Java
iscateli, 2021-12-27 23:09:53

How is the link to the previous node in LinkedStack?

Context from Bruce Eckel's "Java Philosophy" (p.507-508):

Instead of using LinkedList, we could also implement our own internal data storage mechanism.


public class LinkedStack<T> { 
 private static class Node<U> {
   U item;
   Node<U> next;
   Node() { item = null; next = null; }
   Node(U item, Node<U> next) { 
     this.item = item; 
     this.next = next;
   }
   boolean end() { return item == null && next == null; }
}
 private Node<T> top = new Node<T>(); // Сторож 
 public void push(T item) { 
   top = new Node<T>(item, top);
}
 public T pop() {
   T result = top.item;
   if(!top.end()) 
     top = top.next; 
   return result;
}
public static void main(String[] args) {
   LinkedStack<String> lss = new LinkedStack<String>(); 
   for(String s : "Phasers on stun!".split(" ")) 
      lss.push(s);
   String s;
   while((s = lss.pop()) != null)
   System.out.println(s));
}
}
 /* Output:
stun!
on
Phasers

This example uses an end sentinel to detect an empty stack.
The watchdog is created when the LinkedStack is constructed, and on each call to push()
a new Node is created and linked to the previous Node .


There are several questions about the code:
1. Why do you need to create a so-called "watchman" if all the same, when calling a method , an object with the same name is created inside it? 2. How the newly created new node is associated with the previous node, if in the methodprivate Node<T> top = new Node<T>();lss.push(s);top = new Node<T>(item, top);

public void push(T item) { 
   top = new Node<T>(item, top);
}

the second parameter topis a reference to itself ? but if you look at the class structure, it should be the following top = new Node<T>(item, top);
Node<U> next

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Vamp, 2021-12-27
@iscateli

1. Just to demonstrate the use of the sentinel value pattern. In this particular example, just null could have been dispensed with.
2. In the assignment, the right part is executed first - a Node object is created, to which item and the current value stored in the top variable are passed as constructor arguments. The top variable is then assigned a reference to this new object.
This is a shorter version of the following code:

Node<T> oldTop = top;
top = new Node<T>(item, oldTop);

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question