Stack - Link List Java Implementation ...

Stack:  Stack is the data structure which works on the concept of LIFO (Last In First Out). Consider one real time example of stack ... lets assume there is a box in which i keep books one over another. So if i want to take book out of the box then the book which enters last in the box gets out first from the box. Stack data structure can be implemented with two ideas one using Array and another using Link List. Now lets discuss concept of Stack implementation using Link List. Implementation using link list will have an edge over Array implementation, we don't need to worry about the size of the stack as far as we have memory available in the machine we can create node to push the element. You will never face Stack Full Exception.

Here we have got some frequently used methods. Now here we go ...

push(): Pushes data into the stack.

pop():  Removes data from the stack. 

top(): Method delivers top element of the stack.

isEmpty(): This method returns true id stack is empty and false if not.

length(): This method returns integer value as the no of elements of the stack.


other method implementation is available in the Stack implementation in below class definition which violates the concept of stack. This method is sort().

Implementation: 
                  We have got a class called Node which act as a memory box which contains value and address of the next node. Once a node is created for the first time that node is being referred as Head Node and this node will be node till it gets deleted by other method. when other node is being created and ready to push further and head node keeps address of its node. This process goes on till we want to stop push process. Please check the code. Same process need to be addressed for pop method. Last but not the least length, to find the no of node in the list we need to iterate through the list till next node becomes null and counter variable will store the each iteration count. For getting top node we need to iterate again to get the top node of the stack. There is very thin line between Link List and Stack.

Challenges:

• We will never get Stack Full Exception as node is getting created at run time and there is no size specification available. So there is no chance to get this exception.

• We will get another type of Exception, i.e. Stack Empty Exception, if we get pop() method call again and again. Once the stack is empty i.e no more element to remove then we can display Stack Empty Exception.

package com.ds.stack;

import com.ds.common.Node;

public class StackList
{
 Node head;

 public StackList() {
head = null;
 }

 public void push(int value) throws Exception
 {
head = add(value, head);
 }

         public Node add(int val, Node head)

         {

                Node tmpNode = head;

                 if (head == null) {

                         tmpNode = head = new Node(val);

                 } else {

                         while (tmpNode.next != null) {

                                  tmpNode = tmpNode.next;

                         }

                         tmpNode.next = new Node(val);

                 }

                 return head;

         }

 public void top() throws Exception
  {
   if (head == null) {
     System.out.println("Stack is empty");
   } else {
    Node tmpNode = head;
    Node topNode = null;

    while (tmpNode != null) {
       topNode = tmpNode;
      tmpNode = tmpNode.next;
    }
    System.out.println(topNode.data);
   }
 }

public void pop() throws Exception
{
Node tmpNode = head;
Node prevNode = null;
Node nxtNode = head.next;

while (nxtNode != null) {
prevNode = tmpNode;
nxtNode = nxtNode.next;
tmpNode = tmpNode.next;
}

if (prevNode != null) {
prevNode.next = null;
} else {
head = null;
}
}

/**
* Prints all the nodes value in the list
*/
public void print() throws Exception
{
if (head != null) {
Node tmpNode = head;

        while (tmpNode != null) {

            System.out.print(tmpNode.data + " -> ");

            tmpNode = tmpNode.next;

        }

        System.out.println("");

} else {
System.out.println("Stack is empty");
}
}

/**
* Gets the length of the stack i.e. no of node in this list
*/
public int length() throws Exception
{
int len = 0;

                Node currentNode = head;

                while (currentNode != null) {

                        currentNode = currentNode.next;

                        len++;

                }

return len;
}

public static void main(String[] args) throws Exception
{
StackList stack = new StackList();

stack.push(2);
stack.push(5);
stack.push(8);
stack.push(3);
stack.push(7);

stack.top();

System.out.println("link list size is     " + stack.length());

stack.print();

stack.pop();
stack.pop();
stack.pop();

stack.print();
stack.top();

stack.pop();
stack.pop();

stack.print();

stack.top();
System.out.println("link list size is   " + stack.length());
}
}

//  Node class needs to be created separately

// Node Class specification is below

package com.ds.common;

public class Node

{

        public Integer data;

        public Node next;

        public Node(int val)

        {

                data = val;

                next = null;

        }

}

Comparison:  We got to compare both the implementation i.e. Array implementation and Link List implementation. Lets discuss both the implementation then you will be in better position to decide which implementation is better. 

Array: Array implementation takes constant time for push(), pop(), top(), length() as we have got top variable which gives us the exact location of the element for pop(), push() and other described methods. The only problem with this concept is when we have to use dynamic array we need n time to copy the elements in new array which has been created to eliminate Stack Full Exception. 

      If we have the scenario where the total no of element count is fixed then array implementation of stack is preferable over Link List implementation of Stack.

Link List: Link list implementation need n time for every push(), pop() and other operation as we need to iterate form the first node to the last node where element needs to be push(), pop() or other operations. So here we have got the idea of both the concepts and based on the scenario we need to use for better performance.