In this Data structures tutorial we will learn how to Implement stack using Linked List by creating program in java.
Stack is Collection of entities or items. In this post we will implement stack using Linked List in java.
Adding item in Stack is called PUSH.
Removing item from stack is called POP.
Push and pop operations happen at Top of stack.
Stack follows LIFO (Last in first out) - means last added element is removed first from stack.
Let’s see a stack of book, here the book added last in stack will be picked first.
Logic explanation with diagrams on how to Implement Stack using Linked List in java>
For implementing stack using using LinkedList- This StackImplementationUsingLinkedListExample class internally maintains LinkedList reference in java.
StackLinkedList ‘s push method internally calls linkedList’s insertFirst() method
public void push(int value){
linkedList.insertFirst(value);
}
StackLinkedList’s method internally calls linkedList’s deleteFirst() method
public void pop() throws StackEmptyException {
try{
linkedList.deleteFirst();
}catch(LinkedListEmptyException llee){
throw new StackEmptyException();
}
}
|
Pushing node on Stack Implemented using Linked List in java>
Popping node from Stack Implemented using Linked List in java>
Full Program/SourceCode/Example to how to Implement Stack using Linked List in java >
/**
*Exception to indicate that LinkedList is empty.
*/
class LinkedListEmptyException extends RuntimeException{
public LinkedListEmptyException(){
super();
}
public LinkedListEmptyException(String message){
super(message);
}
}
/**
*Exception to indicate that Stack is empty.
*/
class StackEmptyException extends RuntimeException {
public StackEmptyException(){
super();
}
public StackEmptyException(String message){
super(message);
}
}
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* LinkedList class
*/
class LinkedList {
private Node first; // ref to first link on list
/**
* LinkedList constructor
*/
public LinkedList(){
first = null;
}
/**
* Insert New Node at first position
*/
public void insertFirst(int data) {
Node newNode = new Node(data); //Creation of New Node.
newNode.next = first; //newLink ---> old first
first = newNode; //first ---> newNode
}
/**
* Deletes first Node
*/
public Node deleteFirst()
{
if(first==null){ //means LinkedList in empty, throw exception.
throw new LinkedListEmptyException("LinkedList doesn't contain any Nodes.");
}
Node tempNode = first; // save reference to first Node in tempNode- so that we could return saved reference.
first = first.next; // delete first Node (make first point to second node)
return tempNode; // return tempNode (i.e. deleted Node)
}
/**
* Display LinkedList
*/
public void displayLinkedList() {
Node tempDisplay = first; // start at the beginning of linkedList
while (tempDisplay != null){ // Executes until we don't find end of list.
tempDisplay.displayNode();
tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();
}
}
/**
* For implementing stack using using LinkedList- This StackLinkedList
* class internally maintains LinkedList reference in java.
*/
class StackLinkedList{
LinkedList linkedList = new LinkedList(); // creation of Linked List
/**
* Push items in stack, it will put items on top of Stack.
*/
public void push(int value){
linkedList.insertFirst(value);
}
/**
* Pop items in stack, it will remove items from top of Stack.
*/
public void pop() throws StackEmptyException {
try{
linkedList.deleteFirst();
}catch(LinkedListEmptyException llee){
throw new StackEmptyException();
}
}
/**
* Display stack.
*/
public void displayStack() {
System.out.print("Displaying Stack > Top to Bottom : ");
linkedList.displayLinkedList();
}
}
/**
* Main class - To test Stack Implementation Using LinkedList in java
*/
public class StackImplementationUsingLinkedListExample {
public static void main(String[] args) {
StackLinkedList stackLinkedList=new StackLinkedList();
System.out.println("INSERTING AT FIRST (TOP) IN STACK IMPLEMENTED USING LINKED LIST ");
stackLinkedList.push(39); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(71); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(11); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.push(76); //push node.
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
System.out.println("\nDELETING FROM FIRST (TOP) FROM STACK IMPLEMENTED USING LINKED LIST ");
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
stackLinkedList.pop(); //pop Node
stackLinkedList.displayStack(); // display STACK IMPLEMENTED USING LINKED LIST in java
}
}
/*OUTPUT
INSERTING AT FIRST (TOP) IN STACK IMPLEMENTED USING LINKED LIST
Displaying Stack > Top to Bottom : 39
Displaying Stack > Top to Bottom : 71 39
Displaying Stack > Top to Bottom : 11 71 39
Displaying Stack > Top to Bottom : 76 11 71 39
DELETING FROM FIRST (TOP) FROM STACK IMPLEMENTED USING LINKED LIST
Displaying Stack > Top to Bottom : 11 71 39
Displaying Stack > Top to Bottom : 71 39
Displaying Stack > Top to Bottom : 39
Displaying Stack > Top to Bottom :
*/
|
If we analyze output, we will find that node which was pushed last have been popped first.
Complexity of above example on how to Implement Stack using Linked List in java >
Push - O(1) [as we push element at Top in java]
Pop - O(1) [as popping is done at Top too in java]
Summary >
So in this Data structures tutorial we learn how to Implement your own Stack using custom Linked List in java with program and example.
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS in java>
1) Stacks, Queues in Data Structures in java
2) Single LinkedList implementations in Data Structures in java:-
>
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList
