ISourceCode

Make the frequent cases fast and the rare case correct

Implementation of Stack using Linked List

A stack is a First in Last out data structure. Hence we can use two methods of a linked list that is inserting node at beginning of a list and then deleting node at the beginning of a list to develop a stack ADT with push and pop operations.

As the elements get inserted they move further away from the first node of the list. So the element inserted first will end up being the last node if there is a sequence of push operations.

Class Stack abstracts the underlying functioning of a linked list. We need to just call methods of the Stack class.

import java.io.*;
class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
}
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("Elements from top to bottom");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	
}
class Stack
{
	private LinkedList listObj;
	public Stack()	
	{	
		listObj = new LinkedList();
	}
	public void push(int num)
	{
		listObj.insert(num);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
	public void displayStack()
	{
		System.out.print("Stack : ");
		listObj.display();
	}
} 
class StackLinkedListBlog
{
	public static void main(String[] args) throws IOException
	{
		Stack demo = new Stack(); 
		demo.push(10); 
		demo.push(20); 
		demo.displayStack(); 
		demo.push(30); 
		demo.push(40); 
		demo.displayStack(); 
		demo.pop(); 
		demo.pop(); 
		System.out.println("Two elements are popped");
		demo.displayStack(); 
	} 
}

OUTPUT:

labuser@ubuntu:~/Stack$ java StackLinkedListBlog
Stack : Elements from top to bottom
[20]
[10]

Stack : Elements from top to bottom
[40]
[30]
[20]
[10]

Two elements are popped
Stack : Elements from top to bottom
[20]
[10]

labuser@ubuntu:~/Stack$

4 responses to “Implementation of Stack using Linked List

  1. Pingback: Stack Using Linked List | dheeraj9823

  2. Mike June 26, 2015 at 8:37 pm

    could you please explain the Stack class once?What is the need for that?

    • chinmaylokesh June 26, 2015 at 8:43 pm

      Stack class is the wrapper around linked list. It is exposing the methods that simulate the behavior of stack. Note you can implement the stack using any other contingous data structure such as an array.

  3. Ankita November 4, 2016 at 9:58 am

    what is space and time complexity of this? and why?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: