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.
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.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.
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.
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!
Share this page on WhatsApp