Java Program to Implement Stack using Linked List

Stacks and Queues are ADTs (Abstract Data Types). We have already seen how Stacks and Queues can be implemented using arrays. In this tutorial we will see how to implement stack using linked list.

What is ADT ?

ADT (Abstract Data Types) in data structures terminology we can say it is a way of looking at a data structure, focusing on what the data structure does instead of how it does. Stacks and Queues are examples of ADTs.

Stack using Linked List: Example

package com.sneppets.dsalgo;

/**
 * Link
 * 
 */
class Link
{
	//data
	public int intData;
	//next link in the list
	public Link next;
	//constructor
	public Link(int iData)
	{
		intData = iData;
	}
	//display link
	public void displayLink()
	{
		System.out.print(intData + " ");
	}
}

/**
 * Linked List
 *
 */
class LinkedList
{
	private Link first;
	
	public LinkedList()
	{
		first = null;
	}
	
	public boolean isEmpty()
	{
		return (first == null);
	}
	
	public void insertFirst(int iData)
	{
		//create a new link
		Link newLink = new Link(iData);
		//new link --> old first
		newLink.next = first;
		//first --> new link
		first = newLink;	
	}
	
	public int deleteFirst()
	{
		//save reference to link
		Link temp = first;
		//delete first --> old next
		first = first.next;
		//return deleted link
		return temp.intData;
	}
	
	public void displayList()
	{
		//start from beginning of the list
		Link current = first;
		//until end of list is reached
		while (current != null)
		{
			//print link details
			current.displayLink();
			//move to next link
			current = current.next;
		}
		System.out.println(" ");
	}
}

/**
 * Linked List Stack
 */
class LinkedListStack
{
	private LinkedList llist;
	
	public LinkedListStack()
	{
		llist = new LinkedList();
	}
	
	//insert item on top of the stack
	public void push(int i)
	{
		llist.insertFirst(i);
	}
	
	//remove item from top of the stack
	public int pop()
	{
		return llist.deleteFirst();
	}
	
	//return true if stack is empty
	public boolean isEmpty()
	{
		return (llist.isEmpty());
	}
	
	//display stack that is implemented using linked list
	public void displayLinkedListStack()
	{
		System.out.println("Linked List Stack from first to last: ");
		llist.displayList();		
	}
}

/**
 * 
 * @author sneppets.com
 *
 */
public class LinkedListStackExample {
	
	public static void main (String[] args)
	{
		//create stack
		LinkedListStack llstack = new LinkedListStack();
		//push items
		llstack.push(3);
		llstack.push(5);
		llstack.push(7);
		llstack.push(9);
		//display stack
		llstack.displayLinkedListStack();
		//pop items
		llstack.pop();
		llstack.pop();
		//display stack
		llstack.displayLinkedListStack();
		
	}

}

Output

Linked List Stack from first to last: 
9 7 5 3  
Linked List Stack from first to last: 
5 3

Note:

Similar to push() and pop() operations of Stack, using linked list we could carry out operations like llist.insertFirst(data) and llist.deleteFirst().

Recommended Posts

• Simple Linked List Example
• Array Vs Linked List Efficiency
• Double-Ended Lists Example
• Find and delete specified ‘Link’ from Linked List
• Priority Queue: Array Based Example
• Deque: Double-ended queue is a versatile data structure
• Queue No-count approach and Implementation
• Circular Queue using Array (Wrapping Around)
• Reverse a string or word using Stack
• Delimiter Matching using Stack

References

• Oracle API Documentation