Implementing stack using linked lists

27,942

Solution 1

Assuming you genuinely want to do this from scratch rather than using one of the perfectly good existing stack implementations then I would recommend:

Create a "MyStack< T >" class which implements any interfaces you want (perhaps List < T >?)
Within MyStack create a "private static final class Node< T >" inner class for each linked list item. Each node contains a reference to an object of type T and a reference to a "next" Node.
Add a "topOfStack" Node reference to MyStack.
The push and pop operations just need to operate on this topOfStack Node. If it is null, the Stack is empty. I'd suggest using the same method signatures and semantics as the standard Java stack, to avoid later confusion.....
Finally implement any other methods you need. For bonus points, implement "Iterable< T >" in such a way that it remembers the immutable state of the stack at the moment the iterator is created without any extra storage allocations (this is possible :-) )

Solution 2

Why don't you just use the Stack implementation already there?

Or better (because it really a linked list, its fast, and its thread safe): LinkedBlockingDeque

Solution 3

For implementing stack using using LinkedList- This StackLinkedList class internally maintains LinkedList reference.

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();
    }
}

Full Program

/**
 *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.
 */

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 LinkedList.
 */
public class StackLinkedListApp {
    public static void main(String[] args) {

        StackLinkedList stackLinkedList=new StackLinkedList();
        stackLinkedList.push(39);  //push node.
        stackLinkedList.push(71);  //push node.
        stackLinkedList.push(11);  //push node.
        stackLinkedList.push(76);  //push node.

        stackLinkedList.displayStack(); // display LinkedList
                    
        stackLinkedList.pop();  //pop Node
        stackLinkedList.pop();  //pop Node
        
        stackLinkedList.displayStack(); //Again display LinkedList
    }
}

OUTPUT

Displaying Stack > Top to Bottom : 76 11 71 39

Displaying Stack > Top to Bottom : 71 39

Courtesy : http://www.javamadesoeasy.com/2015/02/implement-stack-using-linked-list.html

Solution 4

If you're talking about a single linked list (a node has a reference to the next object, but not the previous one), then the class would look something like this :

public class LinkedListStack {

    private LinkedListNode first = null;
    private LinkedListNode last = null;
    private int length = 0;

    public LinkedListStack() {}

    public LinkedListStack(LinkedListNode firstAndOnlyNode) {
        this.first = firstAndOnlyNode;
        this.last = firstAndOnlyNode;
        this.length++;
    }

    public int getLength() {
        return this.length;
    }

    public void addFirst(LinkedListNode aNode) {
        aNode.setNext(this.first);
        this.first = aNode;
    }

}

public class LinkedListNode {

    private Object content = null;
    private LinkedListNote next = null;

    public LinkedListNode(Object content) {
        this.content = content;
    }

    public void setNext(LinkedListNode next) {
        this.next = next;
    }

    public LinkedListNode getNext() {
        return this.next;
    }

    public void setContent(Object content) {
        this.content = content;
    }

    public Object getContent() {
        return this.content;
    }

}

Of course you will need to code the rest of the methods for it to work properly and effectively, but you've got the basics. Hope this helps!

View more solutions

27,942

user559142

Updated on July 01, 2022

Comments

user559142 almost 2 years

What's the best way to implement a stack using linked lists in Java?

EDIT: I would define best as most efficient using clean code. I have already used an array to implement a stack, but am not familiar with link lists so was wondering if anyone could help me implement something similar to below:

public class StackArray{

    private Object [] objArray;
    private int stackSize;

    public StackArray(){
        objArray = new Object[50];
        stackSize = 0;
    }

    public StackArray(int size){
        objArray = new Object[size];
        stackSize = 0;
    }

    //public interface methods - push, pop, top, empty & clear
    public void push(Object o)throws StackArrayException{
        if(stackSize < objArray.length){
            objArray[stackSize] = o;
            stackSize ++;
        }else{
            throw new StackArrayException("Stack Overflow");
        }
    }

    public Object pop()throws StackArrayException{
        if(stackSize != 0){
            stackSize--;
            return(objArray[stackSize]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public void top() throws StackArrayException{
        if(stackSize != 0){
            return(objArray[stackSize-1]);
        }else{
            throw new StackArrayException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (stackSize == 0):
    }

    public void clear(){
        stackSize = 0;
    }
}

EDIT: Here is the linked list implementation if anyone is interested..

public class StackList{
    private Node listHead;

    protected class Node{
    protected Object datum;
    protected Node next;

    public Node(Object o, Node n){
        datum = o;
        next = n;
    }

    public StackList(){
        listHead = null;
    }

    //public interface methods - push pop top empty clear
    public void push(Object o){
        listHead = new Node(o, listHead);
    }

    public Object pop() throws StackListException{
        if(listHead!=null){
            Object top = listHead.datum;
            listHead = listHead.next;
            return top;
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public Object top()throws StackListException{
        if(listHead != null){
            return(listHead.datum);
        }else{
            throw new StackListException("Stack Underflow");
        }
    }

    public boolean empty(){
        return (listHead == null);
    }

    public void clear(){
        listHead = null;
    }
}

Joachim Sauer about 13 years

Define "best"! What quality do you measure? Developing time? Clean code? Runtime performance? Memory usage? "Grade I get when I turn it in as Homework"? Elegance? Characters per line?

Paŭlo Ebermann about 13 years

Since this is not a linked list implementation, but array-based, maybe?
user559142 about 13 years

thanks i got it working, but i created my own node class instead.