Stack implementation using linked list in Java

Stack implementation using linked list in Java with out using arrays

We have seen implementing the stack using arrays in java in the previous post which has certain drawbacks like inserting / deleting an element from the desired or particular location.

So in a linked list there is a connection for each node / cell (it contains one object to hold desired value and link to the next node / cell).

So when user pushed an element to the stack first element goes to the end, and the recently pushed item will have connection to the last recent item.

so when a new node is pushed, existing top becomes old and new one becomes top similarly for each pop operation in stack takes out top element and his next becomes present top.

below example code helps to understand linked list creation using Cell class an StackUsing LinkedList class helps will do actual push and pop operations

Cell Class : (Linked list) :

package com.krish.datastructures.common;

public class Cell {
	Object val; // value in the cell
	public Cell next; // the address of the next cell in the list

	/**
	 * Constructor Cell builds a new cell
	 * 
	 * @param value
	 *            - the value inserted in the cell
	 * @param link
	 *            - the cell that is chained to this new cell
	 */
	public Cell(Object value, Cell link) {
		val = value;
		next = link;
	}

	/** getVal returns the value held in the cell */
	public Object getVal() {
		return val;
	}

	/** getNext returns the address of the cell chained to this one */
	public Cell getNext() {
		return next;
	}

	/**
	 * setNext resets the address of the cell chained to this one
	 * 
	 * @param link
	 *            - the address of the Cell that is chained to this one
	 */
	public void setNext(Cell link) {
		next = link;
	}
}

Stack using Linked list :

package com.krish.stack;

import com.krish.datastructures.common.Cell;

public class StackUsingLinkedLists {
	public static Cell top;

	/** Constructor Stack creates an empty stack */
	public StackUsingLinkedLists() {
		top = null;
	}

	/**
	 * push inserts a new element onto the stack
	 * 
	 * @param ob
	 *            - the element to be added
	 */
	public void push(Object ob) {
		System.out.println("PUSH : Inserted the element:" + ob);
		top = new Cell(ob, top);
		printStack();
	}

	/**
	 * pop removes the most recently added element prints error if stack is
	 * empty
	 */
	public void pop() {
		if (top == null) {
			System.out.println("POP: Stack error: stack empty");
		} else {
			Object answer = top.getVal();
			top = top.getNext();
			System.out.println("POP: popped the element:" + answer);
			printStack();
		}

	}

	/**
	 * top returns the identity of the most recently added element
	 * 
	 * @return the element
	 * @exception RuntimeException
	 *                if stack is empty
	 */
	public Object top() {
		if (top == null) {
			throw new RuntimeException("Stack error: stack empty");
		}
		return top.getVal();
	}

	/**
	 * isEmpty states whether the stack has 0 elements.
	 * 
	 * @return whether the stack has no elements
	 */
	public boolean isEmpty() {
		return (top == null);
	}

	// Print the stack elements by using top and next
	public void printStack() {
		if (top == null) {
			System.out.println("PRINT: Stack error: stack empty");
		} else {
			System.out.println("PRINT:These are the stack elements now!");
			Cell temp = top;
			while (temp != null) {
				System.out.println(temp.getVal());
				temp = temp.next;
			}
		}
	}

	public static void main(String[] args) {
		StackUsingLinkedLists stack = new StackUsingLinkedLists();
		stack.pop();
		stack.push(23);
		stack.push(267);
		stack.push(500);
		stack.pop();
		stack.pop();
		stack.pop();
	}
}

Output :

POP: Stack error: stack empty
PUSH : Inserted the element:23
PRINT:These are the stack elements now!
23
PUSH : Inserted the element:267
PRINT:These are the stack elements now!
267
23
PUSH : Inserted the element:500
PRINT:These are the stack elements now!
500
267
23
POP: popped the element:500
PRINT:These are the stack elements now!
267
23
POP: popped the element:267
PRINT:These are the stack elements now!
23
POP: popped the element:23
PRINT: Stack error: stack empty

Reference : [1] [2]