stack class with a singly linked list

[logistic_guy]

Efficiently implement a stack class using a singly linked list, with no header or tail nodes.

 

[khansaheb]

Efficiently implement a stack class using a singly linked list, with no header or tail nodes.

show us your effort/s to solve this problem.

 

[logistic_guy]

The idea of this stack class is simple, but implementing the idea is very difficult.

Imagine that we have an empty box and we have three colorful papers, Red, Blue, and Green. If we put them in the box, usually, each one will be stacked on top of the other. This is called stacking.

Our box is initially: Empty

Now imagine that we want to fill the empty (\(\displaystyle \text{null}\)) box. If we put (\(\displaystyle \text{push}\)) first the red paper inside the box,

the box now contains: Red

If we put the blue paper,

the box now contains: Blue Red (the blue paper is now on the top)

if we put the green paper,

the box now contains: Green Blue Red (the green paper is now on the top)

In programming, you can think of Empty as part of the box, so the box will contain:

Green Blue Red Empty (the green paper is on the top)

Now we will implement the same idea but with numbers using the method (or the function), \(\displaystyle \text{push}\).

Initially: null

push(3): 3 null

push(8): 8 3 null

push(15): 15 8 3 null

push(20): 20 15 8 3 null

Now we will improve our push method. We know that \(\displaystyle \text{null}\) is an essential part of the stack, but we don't want it to be seen in the output.

Our improved version:

push(3)
Output: 3

push(8)
Output: 8 3

push(15)
Output: 15 8 3

push(20)
Output: 20 15 8 3 (20 is on the top of the stack)

This is the main idea of the program and I will talk more on how to code push method in \(\displaystyle \text{Java}\) in the next post.

 

[logistic_guy]

Let us crack the stack class by coding the \(\displaystyle \text{push}\) method.



The main purpose of the \(\displaystyle \text{push}\) method is to put numbers inside our box and to make sure that the last number is on the top. In other words, we are creating a new \(\displaystyle \text{Node}\) each time we push a number inside the box. Each new \(\displaystyle \text{Node}\) created has two important pieces of information, a new number and a reference to \(\displaystyle \text{null}\).

Let us call the new number \(\displaystyle \text{data}\) and the reference \(\displaystyle \text{next}\).

Then our Node class is:

class \(\displaystyle \text{Node}\)(){
int data;
Node next;
public Node(int data){
this.data = data;
this.next = null;
}
}

Since our box is initially empty (\(\displaystyle \text{null}\)), the top number inside the box is:
Node top = null;

And our \(\displaystyle \text{push}\) method is:

public void \(\displaystyle \text{push}\)(int data){
Node newNode = new Node(data);
if(top == null){
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}

What does this code basically do, if you put the number, say \(\displaystyle 3\), inside the box?
push(3) means New Node was created:
\(\displaystyle 3 \rightarrow \ \text{null}\)
it contains the number \(\displaystyle 3\) and its \(\displaystyle \text{next}\) has a reference to \(\displaystyle \text{null}\). (The reference is always pointing to the previous information that was there.)

\(\displaystyle \text{push}\) method is basically doing this:
\(\displaystyle \text{newNode}\) contains: \(\displaystyle 3 \rightarrow \ \text{null}\)
top contains: \(\displaystyle 3 \rightarrow \ \text{null}\)

This makes sure that \(\displaystyle 3\) is the top value inside the box.

Let us add another number inside the box, say \(\displaystyle 7\).
push(7)
\(\displaystyle \text{newNode}\) contains: \(\displaystyle 7 \rightarrow 3 \rightarrow \ \text{null}\)

The \(\displaystyle \text{push}\) method creates a new Node that contains the number \(\displaystyle 7\) and a reference to \(\displaystyle \text{null}\). Then it changes its reference from \(\displaystyle \text{null}\) to \(\displaystyle 3 \rightarrow \text{null}\) (the previous value). And it makes sure that the top value is now \(\displaystyle 7\).

We have coded the \(\displaystyle \text{push}\) method and explained how it did things. To make the \(\displaystyle \text{push}\) method work, we need to stick it inside a class and that's what we'll do in the next post. We will create the class \(\displaystyle \text{Stack}\).

 

[logistic_guy]

Let us create the \(\displaystyle \text{Stack}\) class and put inside it our \(\displaystyle \text{push}\) method.

Our \(\displaystyle \text{Stack}\) class is:

class \(\displaystyle \text{Stack}\){
}

We just need to put the \(\displaystyle \text{push}\) method inside the \(\displaystyle \text{Stack}\) class.

class \(\displaystyle \text{Stack}\){
Node top = null;
public void push(int data){
Node newNode = new Node(data);
if (top == null){
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}
}

Why do we need to put the \(\displaystyle \text{push}\) method inside a class? Because it gives us the ability to create many objects of that class, each one of them can use the \(\displaystyle \text{push}\) method with a different value anywhere in our code. This helps us fill our box with different numbers each time we call the \(\displaystyle \text{push}\) method.

Our code is almost ready. All remains is to figure out a way to display on the screen what we have inside our box. That will be the job of creating a new method and place it inside the \(\displaystyle \text{Stack}\) class.

Let us call that new method \(\displaystyle \text{display}\).

Coding the \(\displaystyle \text{display}\) method is the easiest part of our program because we are just displaying information on the screen. Then, let us code it.



public void display(){
Node topNode = top;
System.out.println("Put "+topNode.data+" inside the box.");
System.out.print("Our box contains: ");
while (topNode != null){
System.out.print (topNode.data+" ");
topNode = topNode.next;
}
System.out.println("\n");
}

What does this code exactly do? It simply references the top \(\displaystyle \text{Node}\) to topNode. We know that the top \(\displaystyle \text{Node}\) has two important pieces of information, the top number and a reference to the previous \(\displaystyle \text{Node}\) which also contains a number and another reference.

Let us assume that our box has these numbers:
\(\displaystyle 19 \ 7 \ 3\)

which can be written with visualization as:
\(\displaystyle 19 \rightarrow 7 \rightarrow 3 \rightarrow \text{null}\)

This means that the top \(\displaystyle \text{Node}\) contains the number \(\displaystyle \text{data} = 19\) and a reference \(\displaystyle \text{next} = 7 \rightarrow 3 \rightarrow \text{null}\).

We use topNode.data to display \(\displaystyle 19\) on the screen.

Then, we enter a loop, the loop says:

If \(\displaystyle 19 \neq \text{null}\) which is true, then print \(\displaystyle 19\) on the screen and set the previous \(\displaystyle \text{Node}\) as the top \(\displaystyle \text{Node}\).

This will make the top \(\displaystyle \text{Node}\) now contains \(\displaystyle \text{data} = 7\) with a reference \(\displaystyle \text{next} = 3 \rightarrow \text{null}\).

The process will repeat until all numbers are printed on the screen like this:
\(\displaystyle 19 \ 7 \ 3\)

And the condition will become \(\displaystyle \text{null} = \text{null}\) which will terminate the loop which in turn will terminate the program successfully.

Our \(\displaystyle \text{Stack}\) class now becomes:

class \(\displaystyle \text{Stack}\){
Node top = null;
public void push(int data){
Node newNode = new Node(data);
if (top == null){
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}
public void display(){
Node topNode = top;
System.out.println("Put "+topNode.data+" inside the box.");
System.out.print("Our box contains: ");
while (topNode != null){
System.out.print (topNode.data+" ");
topNode = topNode.next;
}
System.out.println("\n");
}
}

In the next post, we will put our code in the test and we will display a screenshot to see the result.

 

[logistic_guy]

We will create an object from class [imath] \text{Stack} [/imath] and we will use it to call the methods \(\displaystyle \text{push}\) and \(\displaystyle \text{display}\).

Stack stack = new Stack();
stack.push(2);
stack.display();
stack.push(5);
stack.display();
stack.push(13);
stack.display();
stack.push(8);
stack.display();

We're expecting our code will end with displaying:
\(\displaystyle 8 \ 13 \ 5 \ 2\)

Now I have to put this chunk of code inside the main function. This is because every \(\displaystyle \text{Java}\) program must have a main function.

public static void main(String[] args) {
Stack stack = new Stack();
stack.push(2);
stack.display();
stack.push(5);
stack.display();
stack.push(13 );
stack.display();
stack.push(8);
stack.display();
}

When I created the classes \(\displaystyle \text{Node}\) and \(\displaystyle \text{Stack}\), I put them inside the main class which I called \(\displaystyle \text{Boor}\). Therefore, making an object from the class \(\displaystyle \text{Stack}\) will depend on the class \(\displaystyle \text{Boor}\), so I have also to make an object from the class \(\displaystyle \text{Boor}\) and link them together.

My edited code of the main function is:

public static void main(String[] args) {
Boor boor = new Boor();
Boor.Stack stack = boor.new Stack();
stack.push(2);
stack.display();
stack.push(5);
stack.display();
stack.push(13 );
stack.display();
stack.push(8);
stack.display();
}

My code is now readyall we have to do is just to collect it all together in one place and run it.

The full code:

class Boor {

class Node {
int data;
Node next;
public Node (int data){
this.data = data;
this.next = null;
}
}

class Stack{
Node top = null;
public void push(int data){
Node newNode = new Node(data);
if (top == null){
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}
public void display(){
Node topNode = top;
System.out.println("Put "+topNode.data+" inside the box.");
System.out.print("Our box contains: ");
while (topNode!=null){
System.out.print (topNode.data+" ");
topNode = topNode.next;
}
System.out.println("\n");
}
}
public static void main(String[] args) {
Boor boor = new Boor();
Boor.Stack stack = boor.new Stack();
stack.push(2);
stack.display();
stack.push(5);
stack.display();
stack.push(13);
stack.display();
stack.push(8);
stack.display();
}
}



We have coded what we have been asked for, but for the sake of completeness, we have to improve our code so it can remove numbers from the box. Basically, we want to be able to remove the last number that was put in the box. And that what we'll do in the next post. We will create the \(\displaystyle \text{pop}\) function.

 

[logistic_guy]

Let us crack the final touches of our code and leave it there in peace for good.



As promised, we will invent the method \(\displaystyle \text{pop}\) to remove numbers from our box. Forgive me if I called methods, functions. Technically, they are the same, but in \(\displaystyle \text{Java}\), they are called methods. It is just because I also program in other languages, I interchangeably use both names.

This is how I coded the method \(\displaystyle \text{pop}\):

public void pop(){
skip = 1;
int data = top.data;
Node topNode = top;
top = topNode.next;
System.out.println("Remove "+data+" from the box.");
}
Very simple ha?

What does this method do exactly? It will first save the top number in a variable, then it will simply reference the top \(\displaystyle \text{Node}\) to topNode, then it will reference back to top the previous \(\displaystyle \text{Node}\) as the top \(\displaystyle \text{Node}\). Confused? Here is an example with numbers.

Let us assume that our box has these numbers:
\(\displaystyle 7 \ 1 \ 15 \ 4\)

The \(\displaystyle \text{pop}\) method will save the number \(\displaystyle 7\) in the variable \(\displaystyle \text{data}\), then it will reference the following:
initially top \(\displaystyle = 7 \rightarrow 1 \rightarrow 15 \rightarrow 4 \rightarrow \text{null}\)
then top will share its reference with topNode like this:
topNode \(\displaystyle = 7 \rightarrow 1 \rightarrow 15 \rightarrow 4 \rightarrow \text{null}\)
then topNode will share back its \(\displaystyle \text{next}\) reference (which is the previous Node) with top
top \(\displaystyle = 1 \rightarrow 15 \rightarrow 4 \rightarrow \text{null}\)

By doing this process, we have removed \(\displaystyle 7\) (which was the top number) from our box. We are still keeping a copy of \(\displaystyle 7\) because we want to display a message on the screen to say: Remove \(\displaystyle 7\) from the box. After the message gets displayed, we don't care about \(\displaystyle 7\) anymore. Let it get lost, die, or whatever!

I also added a \(\displaystyle \text{skip}\) variable in the \(\displaystyle \text{pop}\) method to make sure that after deleting a number from the box and calling \(\displaystyle \text{display}\) method to update the current numbers in the box, we don't want the message (Put [imath]\text{\#}[/imath] inside the box to be displayed). In our previous code, any time we call the method \(\displaystyle \text{display}\), the message (Put [imath]\text{\#}[/imath] inside the box.) will always get displayed on the screen.

I also updated our \(\displaystyle \text{display}\) method so that when our box is Empty, a message will tell us that Our box contains: Nothing!.

Here is the complete code with a screenshot:

class Boor {
int skip = 0;

class Node {
int data;
Node next;
public Node (int data){
this.data = data;
this.next = null;
}
}

class Stack{
Node top = null;
public void push(int data){
Node newNode = new Node(data);
if (top == null){
top = newNode;
}
else{
newNode.next = top;
top = newNode;
}
}
public void display(){
Node topNode = top;
if(skip == 0){
System.out.println("Put "+topNode.data+" inside the box.");
} else {skip = 0;}
if (topNode==null){
System.out.print("Our box contains: Nothing!\n");
} else {
System.out.print("Our box contains: ");
while (topNode!=null){
System.out.print (topNode.data+" ");
topNode = topNode.next;
}
System.out.println("\n");
}
}

public void pop(){
skip = 1;
int data = top.data;
Node topNode = top;
top = topNode.next;
System.out.println("Remove "+data+" from the box.");
}
}

public static void main(String[] args) {
Boor boor = new Boor();
Boor.Stack stack = boor.new Stack();
stack.push(2);
stack.display();
stack.push(5);
stack.display();
stack.push(13);
stack.display();
stack.push(8);
stack.display();
stack.pop();
stack.display();
stack.push(103);
stack.display();
stack.pop();
stack.pop();
stack.display();
stack.push(444);
stack.display();
stack.push(444);
stack.display();
stack.push(333);
stack.display();
stack.pop();
stack.display();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.display();
System.out.println();
stack.push(2025);
stack.display();
}
}