Stack Implementation in Java Using Linked List

In this post we’ll see an implementation of Stack in Java using Linked list. Stack can also be implemented using array but that has one drawback that the stack size is fixed in that case.

Refer Stack Implementation in Java Using Array to see how to implement Stack using array in Java.

Stack data structure

A stack is a Last In First Out (LIFO) data structure. In a stack items are both inserted and removed from the top and you have access to a single data item; that is the last item inserted. Once that is retrieved then only you can access the next item.

Following image shows the items in a Stack.

Operations in a Stack

Mainly following three operations are implemented for a Stack-

push- To insert an item on the stack.
pop- To remove an item from the top of the stack.
peek- Read value from the top of the stack without removing it.

Java program for Stack using Linked list

For representing nodes of the linked list a separate class (private class Node in the program) is used which apart from the data also holds a reference to itself.

There is also one reference top which always points to the first node of the Linked list (top of the stack).

For push operation new nodes are inserted in the beginning of the Linked list and the top references the new node.

For pop operation first node in the Linked list is removed and the top starts referencing to the next node.

public class LinkedListStack {
  //Reference for the top of the stack
  Node top;
  public LinkedListStack(){
    top = null;
  }
  //Class representing each node
  private class Node{
    //data
    int i;
    //ref to next node
    Node next;
    Node(int i){
      this.i = i;
    }
    public void displayData(){
      System.out.println("i= " + i);
    }
  }
    
  public void insertNode(int i){
    //Create a new node
    Node newNode = new Node(i);
    // current top is pushed down
    newNode.next = top;
    // newly inserted node is referenced by top
    top = newNode;
  }
    
  public int removeNode(){        
    Node temp = top;
    // Next item in the stack is referenced by top
    top = top.next;
    return temp.i;
  }
    
  public int nodeData(){
    return top.i;
  }

  public boolean isEmpty(){
    return top == null;
  }
    
  public void push(int item){
    insertNode(item);
  }
  public int pop(){
    // If no item is inserted
    if(isEmpty()){
      throw new RuntimeException("Stack is Empty");
    }
    return removeNode();
  }
    
  public int peek(){
    // If no item is inserted
    if(isEmpty()){
      throw new RuntimeException("Stack is Empty");
    }
    return nodeData();
  }
    
  public void displayStack(){
    // start from the top
    Node current = top;
    // traverse the list
    while(current != null){
      current.displayData();
      current = current.next;
    }
  }
  public static void main(String[] args) {
    LinkedListStack stack = new LinkedListStack();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.push(40);
    System.out.println("Item peeked- " + stack.peek());
    System.out.println("Items in stack--");
    stack.displayStack();
    System.out.println("Item popped- " + stack.pop());
    System.out.println("Item popped- " + stack.pop());
    System.out.println("Item peeked- " + stack.peek());
    System.out.println("Items in stack--");
    stack.displayStack();
  }
}

Output

Item peeked- 40
Items in stack--
i= 40
i= 30
i= 20
i= 10
Item popped- 40
Item popped- 30
Item peeked- 20
Items in stack--
i= 20
i= 10

That's all for this topic Stack Implementation in Java Using Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Tuesday, May 10, 2022