Introduction

Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it. There are two basic ways to implement stack data structure :

• Array based Implementation
  • Using Array or Static Array (Array size is fixed and has to be given during initialization)
  • Using Dynamic Arrays or Resizable Arrays (Arrays can grow or shrink based on requirement)
• Linked List Based Implementation

In this post we are going to discuss about linked list based implementation of stack data structure. Before proceeding with this post, it is highly recommended to understand what is linked list and how stack operations are performed.

Prerequisite

• Stack Data Structure
• Linked List Data Structure

In a linked list, whenever we want to add/delete an element we either add/delete at the beginning or at random position or at the end of the linked list. Whereas in case of stack we do restrict add/delete at only one endpoint which is at the end as it follows Last In First Out ordering. So the last node is always the key element for stack operations.

Algorithm

Stack algorithm is defined in terms of adding an element which is called Push and deleting an element from the stack which is called Pop.

Initialization : Add variable last which points to the last node of the linked list. If there are no elements in the stack, it points to null.

Push Operation

1. Create a new node for the data given. Let us assume newly created node as newNode
2. If stack is empty (no elements left in the stack)
   • initialize last to newNode
3. Else
   • in this case newNode will be the last element and the current last element will be the oldLast element.
   • update newNode as the last element.
   • the last element next points to the oldLast element.

1void push(int data) : 
2      Node newNode = new Node(data)  
3
4      if(last == null) : 
5        last = newNode   
6
7      else : 
8        // store oldLast pointer 
9        Node oldLast = last 
10
11         // update newNode as the last element
12        last = newNode 
13
14        // add connection to oldLast element 
15        last.next = oldLast 

Pop Operation

1. If stack is empty (last == null)
   • throw exception
2. Else
   • remove the last element
   • It means second last element will be the last element which is last.next

1int pop() : 
2    if(last == null) :   
3      throw exception 
4
5    else :   
6      Node top = last 
7
8      // remove last element by updating last to next element  
9      last = last.next 
10    
11    return top.data  

Dry Run

To understand push and pop operations clearly, let us perform below operations. Let us consider we have few balls and we want to place them or delete them on request basis in a container (stack)

Java Implementation

1public class StackUsingLinkedList {
2  private Node last ;
3
4  public void push(int data){
5    // create new node for the given data
6    Node newNode = new Node(data);
7
8    //check stack is empty or not
9    if(isEmpty()){
10      // initialize last to newly created node
11      last = newNode;
12    }
13    // if stack is not empty
14    else {
15      Node oldLast = last;
16
17      // newNode will be always on top
18      // and is obviously last element
19      last = newNode;
20
21      // add link to oldLast element
22      // as last node next element
23      last.next = oldLast;
24    }
25  }
26
27  public int pop(){
28    // if stack is empty throw exception
29    if(isEmpty()){
30      throw new RuntimeException("Stack is Empty");
31    }
32    // take data of the last element
33    int data = last.data;
34
35    // remove last element by
36    // updating last to it's next element
37    last = last.next;
38
39    //return data
40    return data;
41  }
42
43  // to check which element is on top
44  public int peek(){
45    if(isEmpty()){
46      throw new RuntimeException("Stack is Empty");
47    }
48    // as stack is not empty
49    // last element is always on top of stack
50    return last.data;
51  }
52
53  // code to check the stack is empty or not
54  public boolean isEmpty(){
55    return last == null;
56  }
57
58  // node class
59  private static class Node{
60    Node next;
61    int data;
62
63    Node(int data){
64      this.data = data;
65    }
66  }
67
68  public static void main(String[] args) {
69    StackUsingLinkedList obj = new StackUsingLinkedList();
70
71    int data = 20;
72    obj.push(data);
73    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());
74
75    data = 30;
76    obj.push(data);
77    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());
78
79    data = 45;
80    obj.push(data);
81    System.out.println("Top Element After pushing "+data+" >>>>  "+obj.peek());
82
83    // As last element is 45, obj.pop should remove 45
84    // and top element should be at 30
85    System.out.println("POP >> "+obj.pop());
86    System.out.println("Top Element After pop is "+obj.peek());
87  }
88}