Stack Implementation using single linked list in java

Stack is a data structure or collection that works on LIFO (Last In First Out) principle.


It is ordered list and order in which the data arrives is important. This means that the last thing we added (pushed) is the first thing that gets pulled (popped) off.

To understand how a stack works, think of a deck of playing cards that is face down. We can only easily access the card that is on top. When we want to look at the top card, there are two things we can do: we can peek at it, but leave it on the stack, or we can pop it off. When we pop off the top object, we are taking it off the stack. If we want to add another card to the top of the stack, we push.

Another example of stack is pile of plates of a cafeteria is a good example of stack. When a plate is required it is taken from the top of the stack. First plate placed on the stack is the last one to be used.

Stack ADT:
Following operations make a stack ADT.

Main Operations

• void push(Object data):Insert data onto stack in O(1) time complexity
• Object pop() Removes and returns the last inserted element from the stack in O(1) time complexity.

 Auxiliary Operations

• Object top():Returns the last inserted element without removing it.
• int size(): Returns the number of elements stored in stack.
• boolean isEmpty(): Indicates whether any elements are stored in stack or not.
• isStackFull(): Indicates whether stack is full or not.(Only when stack is bounded)

Stack can be implemented using array/linked list/queue.

Stack Example 

•  Recursive function internally usages stack to maintain the call stack.
• Even Java usages stack to maintain the method call hierarchy.

Stack Implementation Using Single Linked List:

Below is my Single Link List:

public class LinkList<T> {
    public LinkList() {
    }
    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
}




Class LinkList has 2 members, one is data and other is reference to next node.

Stack Class:
public class StackUsingLinkedList<T> {
    LinkList<T> top = null;

    public void push(T data) {
        if (top == null) {
            top = new LinkList<T>(data);
        } else {
            LinkList<T> newNode = new LinkList<T>(data);
            newNode.setNext(top);
            top = newNode;
        }
    }

    public T pop() {
        T data = null;;
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        } else {
            LinkList<T> temp=top;
            data = top.getData();
            top=top.getNext();
            temp.setNext(null);
        }
        return data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public T top() {
        T data = null;;
        if (isEmpty()) {
            System.out.println("Stack is Empty");
        } else {
            data = top.getData();
        }
        return data;
    }
}

Explanation: Here if you noticed, we are adding new element at beginning of the linked list because to maintain the LIFO Principle and PUSH/POP both operation should be in O(1).


If we insert element at the last then we have to traversal through complete list. We can achieve this using two pointer but again we have to maintain 2 pointers.

PUSH Operation:
First, It checks whether Stack is empty or not. If yes then create a node and assign it to top, otherwise create a new node and new node's next will point to top and new node becomes top.

POP Operation: 
It also checks whether Stack is empty or not. If yes then Print stack is empty and return null, Otherwise take the top node and top becomes next node of the top.