Stack Implementation in Java Using Linked List

Stack in Java Using Linked List

This article demonstrates a linked list implementation of generic stack. Linked list implementation of stack is efficient than array implementation because it does not reserve memory in advance. A stack is a container to which objects are added and removed by following last-in-first-out strategy. To insert objects into and remove from stack a pointer usually called top is maintained that points to last inserted item. However, in linked implementation of stack we don't exactly require the top pointer because we will add an item at the beginning of the list and remove it from the beginning of the list.

A stack by definition supports two methods, one is push for adding objects to the stack, and second, pop for removing the latest added object from the stack. The following methods we plan to implement as part of our stack implementation in Java using linked list.

push(): Adds an item to the stack

pop(): Return the top object from the stack, and remove as well.

In addition to push() and pop() methods we can also define a few supporting but optional methods, such as,

size(): Return the number of objects the stack contains right now.

isEmpty(): Returns true if stack is empty, false otherwise.

Stack Interface

As Java is an object oriented programming language so we will harness object oriented features of the language during our linked implementation of stack in Java. In order to make end user independent from implementation details of the stack implementation whether it is implemented using linked list or array, we define an interface Stack as follows. The following Stack interface can be assigned any object that implements this interface no matter the underlying implementation uses linked list or array based implementation of stack in Java. Create a text file Stack.java, insert the following code in that and save it. 

/* Stack.java */
 
public interface Stack <Item>
{
  Item pop(); // return the top item and removes it from stack
  void push(Item item); // adds an item to the stack
  boolean isEmpty(); // returns true if stack is empty, false otherwise
  int size();  // returns the number of items in stack right now
}

If you look at the above definition of Stack interface, you will see that the interface is passed a parameter Item enclosed in angular brackets. This feature facilitates the generic use of Stack data structure. It allows programmers to pass the object type the stack will store at run time. A special feature of Java called generics brings us this capability.

LinkedStack Class Implementing Stack

Now create a file LinkedStack.java and insert the following code for class LinkedStack that implements Stack interface as follows: 

/* LinkedStack.java */
class LinkedStack <Item> implements Stack <Item>
{
  private Node head; //the first node
  private int size; // number of items
 
  //nested class to define node
  private class Node
  { 
    Item item;
    Node next;
  }
 
  //Zero argument constructor
  public LinkedStack()
  {
    head = null;
    size = 0;
  }
 
  public boolean isEmpty()
  {
    return (size == 0);
  }
 
  //Remove item from the beginning of the list.
  public Item pop()
  {
    Item item = head.item;
    head = head.next;
    size--;
    return item;
  }
 
  //Add item to the beginning of the list.
  public void push(Item item)
  {
    Node oldHead = head;
    head = new Node();
    head.item = item;
    head.next = oldHead;
    size++;
  }
 
  public int size()
  {
    return size;
  }
}

The above implementation of LinkedStack class takes a type parameter Item which would be replaced with concrete type by the client code when the LinkedStack object will be created as follows, for an example: 

Stack <Integer> s = new LinkedStack <Integer>();

The above code completes the stack implementation using linked list but we definitely will be further interested in implementing iterator for the newly created LinkedStack type, so that we can iterate through the items currently stored in the data structure. Following section implements iterator for LinkedStack class and a driver to run LinkedStack class code.

Iterating through Stack Items - Stack Iterator

By definition of stack data structure you would use it as a container where items are added to and removed from one end. But, if you like to make the Stack a usual collection where you can iterate through the stack items, you should implement Iterable and Iterator interfaces as part of your LinkedStack implementation.

Java provides a special syntax of for loop (also called for-each loop) to process arrays and iterable collections. Any iterable collection has to implement an iterator() method that returns an Iterator object. And the class implements Iterator has to implement two methods: hasNext() (returns true if there are more items to process, false otherwise) and next() (returns an item from the collection).

To make our Stack data structure iterable, we first extends the Stack<Item> interface by Iterable<Item>. Interface Iterable is already defined as part of java.lang.Iterable. As soon as we extend Stack<Item> interface by Iterable<Item> we have to add a new method iterator() to class LinkedStack that will return an object of type Iterator<Item>

Generally, an iterator is an object of a class that implements hasNext(), and next() as they are declared in Iterator interface. The Iterator interface also declares a remove() method but we will not specify anything in its body.

The interface Iterator<Item> we will implement by an inner class LinkedStackIterator to LinkedStack. To complete the code first modify the existing signature of interface Stack in Stack.java as follows, no change required in interface's body. 

public interface Stack <Item> extends Iterable <Item>

Thereafter modifying Stack interface, we need to modify LinkedStack class as follows: 

/* LinkedStack.java */
import java.lang.Iterable;
import java.util.*;
 
class LinkedStack <Item> implements Stack <Item>
{
  private Node head; //the first node
  private int size; // number of items
 
  //Nested class to define node
  private class Node
  {
    Item item;
    Node next;
  }
 
  //Zero argument constructor
  public LinkedStack()
  {
    head = null;
    size = 0;
  }
 
  //Check if stack is empty	
  public boolean isEmpty()
  {
    return (size == 0);
  }
 
  //Remove item from the beginning of the list.
  public Item pop()
  {
    Item item = head.item;
    head = head.next;
    size--;
    return item;
  }
 
  //Add item to the beginning of the list.
  public void push(Item item)
  {
    Node oldHead = head;
    head = new Node();
    head.item = item;
    head.next = oldHead;
    size++;
  }
 
  //Return number of items present in the stack
  public int size()
  {
    return size;
  }
 
  //Iterator for traversing stack items
  public Iterator<Item> iterator()
  {
    return new LinkedStackIterator();
  }
 
  //inner class to implement iterator interface
  private class LinkedStackIterator implements Iterator <Item>
  {
    private int i = size;
    private Node first = head; //the first node
 
    public boolean hasNext()
    {
      return (i > 0);
    }
 
    public Item next()
    {
      Item item = first.item;
      first = first.next;
      i--;
      return item;
    }
 
    public void remove()
    {
      // not needed
    }
  }
}

To test the above implementation, define a driver class as follows: 

/* LinkedStackDemo.java */
 
public class LinkedStackDemo
{
  public static void main (String a[])
  {
    Stack <Integer> s = new LinkedStack<Integer>();
    s.push(20);
    s.push(30);
    s.push(40);
    s.push(50);
    s.push(60);
    s.push(70);
 
    System.out.println("Size of the stack: " + s.size());
 
    // iterate through stack
    System.out.println("Stack contains following items till this moment:");
    for (Integer i : s)
      System.out.println(i);  
  }
}
 
OUTPUT
======
D:\JavaPrograms>javac LinkedStackDemo.java
 
D:\JavaPrograms>java  LinkedStackDemo
Size of the stack: 6
Stack contains following items till this moment:
70
60
50
40
30
20

If you observe the output generated by LinkedStackDemo class, you will find that stack items are processed in reverse order of their insertion. It is because items pushed at last are popped first.

Last Word

In this tutorial we talked of implementation of stack in Java using linked list. We implemented generic stack in Java using linked list to create a stack of any user defined type. In implementation of stack using linked list memory is used efficiently and no resize operations are required as they are required in array implementation. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References

  1. Algorithm Design [Foundations, Analysis, and Internet Examples]
  2. Algorithms, 4th Edition
  3. Handbook of Data Structures and Applications


Share this page on WhatsApp

Get Free Tutorials by Email

About the Author

is the founder and main contributor for cs-fundamentals.com. He is a software professional (post graduated from BITS-Pilani) and loves writing technical articles on programming and data structures.