Find minimum in a stack

Question: Design a data structure where it supports LIFO and a function min which gives min of the elements present at the moment in that structure.

Solution: To implement LIFO we can use Stack data structure, but to maintain current minimum we can use auxiliary space, here I am implementing it using another auxiliary stack. Initialize auxiliary stack with first element pushed in the stack as it would be the minimum at present. Now whenever a new element is pushed we check whether it is less than top element in auxiliary stack?if this condition satisfies then push it to auxiliary stack too. While popping through the stack, again check whether top of auxiliary is same as popped element, then pop from auxiliary also. At any time top of auxiliary will give min of the elements present in the stack.

Following program implements above logic.

/**
 * @author vikky.agrawal
 * Min should return minimum of elements present at the moment in stack.
 * 
 */

public class StackImpl {

 Node top =null; 
 
 public static void main(String[] arg){ 
   
  //Find min implementation
  
  StackImpl stack1=new StackImpl();
  StackImpl auxiliary=new StackImpl();
  
  for (int i = 1; i < 10; i++) {
   int data=(int) (Math.random() * 100);
   stack1.push(data);
   
   if(auxiliary.top==null){
    auxiliary.push(data);
   }else{
    int temp=auxiliary.peek();
    if(temp>0 && temp>data){
     auxiliary.push(data);
    }
   }
   
  }
  System.out.println("Original stack :");
  stack1.printStack();
  
  System.out.println("Auxiliary stack : ");
  auxiliary.printStack();
  
  //System.out.println("Min element right now is :"+auxiliary.peek());
  
  for (int i = 1; i < 5; i++) {
   
   int popped=stack1.pop();
   
   System.out.println("Popped element is :"+popped);
   
   if(auxiliary.peek()== popped){
    auxiliary.pop();
   }   
            System.out.println("Next Min element right now is :"+auxiliary.peek()); 
  }
 }
  
 /**
  * Helper functions for stack operations
  */
 
 public void push(int data){
  if(top==null){
   top=new Node(data);
  }else{
   Node temp=new Node(data);
   temp.setLink(top);
   top=temp;
  }
 }
 
 public int pop(){
  if(top==null){
   return -1;
  }else{
   Node temp=top;
   top=top.getLink();
   return temp.getData();
  }
 }
 
 public int peek(){
  if(top!=null){
   return top.getData();
  }else{
   return -1;
  }
 }
 
 
 public boolean isEmpty(){
  if(top==null)
   return true;
  return false;
 }
 
 
 public int size(){
  int size=0;
  Node temp=top;
  
  while(temp!=null){
   size++;
   temp=temp.getLink();
  }
  return size;
 }
 
 public void printStack(){
  Node temp=top;
  System.out.print("Top->\n");
  while(temp!=null){
   System.out.println(temp.getData()+"\n|");
   temp=temp.getLink();
  }
  System.out.println("/null");
 }
 
 /**
  * static inner class to be used for Stack Data Structure
  */
  static class Node{
   private int data;
   private Node link;    
      
      Node(){
            
      }
      
      Node(int data){
       //mergedList=new Node();
          this.setData(data);
          this.setLink(null);       
      }
      
      public int getData(){
          return this.data;
      }
        
      public Node getLink(){
          return this.link;
      }
      
      public void setData(int data){
          this.data=data;
      }       
      
      public void setLink(Node link){
          this.link=link;
      }  
 }
 
 
}

Rotate a linked list anti clock wise for given number of nodes

Java program to rotate a given Linked list anti clockwise for given no of nodes.

/**
 * @author vikky.agrawal
  */

public class LinkedList {

	Node node = null;	

	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.operations();

	}

	public void operations() {

		this.node = new Node(10);

		for (int i = 1; i < 6; i++) {
			add(node, (int) (Math.random() * 100));
		}
		this.rotateACW(node, 8);
	}
	
	/**
	 * Rotate a linked list Anti clock wise for given number of nodes
	 */

	public void rotateACW(Node root, int n) {

		if (root == null || n<=0) {
			return;
		}

		int size=size(root);
		if(n==size){
			//no need to rotate, as it will be the same
			System.out.println("List after rotating");
			print(root);
			return;			
		}
		
		if (n > size) {
			n=n%size;
		}

		System.out.println("List Before rotating");
		print(root);

		Node ptr = root;
		Node ptr1 = null;

		while (n-- > 0) {
			ptr1 = ptr;
			ptr = ptr.getLink();
		}

		Node temp = ptr;

		while (temp.getLink() != null) {
			temp = temp.getLink();
		}

		temp.setLink(root);
		ptr1.setLink(null);
		root = ptr;

		System.out.println("List after rotating");
		print(root);

	}
	
	
	/**
	 * Helper functions for LinkedList
	 */
	public void add(Node ptr, int data) {
		if (ptr == null) {
			System.out.println("Always null ?");
			ptr = new Node(data);
		} else {
			Node newptr = ptr;
			while (newptr.getLink() != null) {
				newptr = newptr.getLink();
			}
			newptr.setLink(new Node(data));
			newptr.getLink().setLink(null);
		}
	}

	public void print(Node ptr) {

		if (ptr == null) {
			return;
		}
		Node ptr1 = ptr;
		System.out.print(ptr1.getData() + "->");
		while ((ptr1 = ptr1.getLink()) != null) {
			System.out.print(ptr1.getData() + "->");
		}
		System.out.println("/n");

	}

	public int size(Node ptr) {

		if (ptr == null) {
			return -1;
		}
		Node ptr1 = ptr;
		int i = 1;
		while ((ptr1 = ptr1.getLink()) != null) {
			i++;
		}
		return i;
	}
	
	/**
	 * static inner class for LinkedList Data Structure
	 */
	private static class Node{
		 private int data;
		 private Node link; 		 
		    
		    Node(){
		    	    	
		    }
		    
		    Node(int data){
		    	//mergedList=new Node();
		        this.setData(data);
		        this.setLink(null);       
		    }
		    
		    public int getData(){
		        return this.data;
		    }
		      
		    public Node getLink(){
		        return this.link;
		    }
		    
		    public void setData(int data){
		        this.data=data;
		    }       
		    
		    public void setLink(Node link){
		        this.link=link;
		    }  
	}
	
}

Given a singly linked list swap every two nodes

Java program to swap every two nodes in a LinkedList e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5

/**
 * @author vikky.agrawal
 */

public class LinkedList {

	Node node = null;
	

	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.operations();

	}

	public void operations() {

		this.node = new Node(10);

		for (int i = 1; i < 6; i++) {
			add(node, (int) (Math.random() * 100));
		}
		this.swap(node);
	}
	
	/**
	 * Given a singly linked list, swap every two nodes
	 * e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5
	 */
	
	public void swap(Node root){
		
		if(root == null){
			return;
		}
		
		System.out.println("before swap : ");
		print(root);
		
		
		Node temp=root;
		while(temp!=null && temp.getLink()!=null){
			int data=temp.getData();
			temp.setData(temp.getLink().getData());
			temp.getLink().setData(data);
			temp=temp.getLink().getLink();
		}
		System.out.println("After swap");
		print(root);
		
	}
	
	
	/**
	 * Helper functions for LinkedList
	 */
	public void add(Node ptr, int data) {
		if (ptr == null) {
			System.out.println("Always null ?");
			ptr = new Node(data);
		} else {
			Node newptr = ptr;
			while (newptr.getLink() != null) {
				newptr = newptr.getLink();
			}
			newptr.setLink(new Node(data));
			newptr.getLink().setLink(null);
		}
	}

	public void print(Node ptr) {

		if (ptr == null) {
			return;
		}
		Node ptr1 = ptr;
		System.out.print(ptr1.getData() + "->");
		while ((ptr1 = ptr1.getLink()) != null) {
			System.out.print(ptr1.getData() + "->");
		}
		System.out.println("/n");

	}

	public int size(Node ptr) {

		if (ptr == null) {
			return -1;
		}
		Node ptr1 = ptr;
		int i = 1;
		while ((ptr1 = ptr1.getLink()) != null) {
			i++;
		}
		return i;
	}
	
	/**
	 * static inner class for LinkedList Data Structure
	 */
	private static class Node{
		 private int data;
		 private Node link; 		 
		    
		    Node(){
		    	    	
		    }
		    
		    Node(int data){
		    	//mergedList=new Node();
		        this.setData(data);
		        this.setLink(null);       
		    }
		    
		    public int getData(){
		        return this.data;
		    }
		      
		    public Node getLink(){
		        return this.link;
		    }
		    
		    public void setData(int data){
		        this.data=data;
		    }       
		    
		    public void setLink(Node link){
		        this.link=link;
		    }  
	}
	
}

LinkedList : print middle element and print nth element from last

Java program having functions to print middle element of linked list(using slow and fast pointers) and printing nth element from last of linked list.

/**
 * @author vikky.agrawal
 * Link List print middle element | print nth element from last
 */

public class LinkedList {

	Node node = null;
	

	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.operations();

	}

	public void operations() {

		this.node = new Node(10);

		for (int i = 1; i < 6; i++) {
			add(node, (int) (Math.random() * 100));
		}
		System.out.println("Middle in case of even no of elements:");		
		printMiddle(node);
		add(node, 65);
		System.out.println("Middle in case of odd no of elements:");
		printMiddle(node);
		printNthFromLast(node, 5);
	}
	
	
	//Print Nth element from last for given value of N	
	
	
	public void printNthFromLast(Node root, int n) {

		int i = n;
		if (root == null) {
			return;
		}

		if (i > size(root)) {
			System.out.println("Not enough elements");
			return;
		}

		Node node = root;
		Node nodeback = root;

		while ((node.getLink() != null) && (--i > 0)) {
			node = node.getLink();
		}

		if (node.getLink() != null) {
			while (node.getLink() != null) {
				nodeback = nodeback.getLink();
				node = node.getLink();
			}
		}

		System.out.println("N = " + n + " element from last is :"
				+ nodeback.getData());

	}

	/**
	 * Print middle element using slow and fast pointers.
	 */

	public void printMiddle(Node root) {
		if (root == null) {
			return;
		}

		System.out.println("Linked list is ");
		print(root);

		Node hare = null;
		Node tortoise = null;
		boolean temp = false;
		if (size(root) % 2 == 0)
			temp = true;

		if (temp) {
			hare = root.getLink();
			tortoise = root;
		} else {
			hare = root;
			tortoise = root;
		}

		while (hare != null && hare.getLink() != null) {
			hare = hare.getLink().getLink();
			tortoise = tortoise.getLink();
		 }
		if (temp) {
			System.out.println("Middle elements :" + tortoise.getData()
					+ " and " + tortoise.getLink().getData());
		} else {
			System.out.println("Middle element is :" + tortoise.getData());
		 }
	 }


	
	
	/**
	 * Helper functions for LinkedList
	 */
	public void add(Node ptr, int data) {
		if (ptr == null) {
			System.out.println("Always null ?");
			ptr = new Node(data);
		} else {
			Node newptr = ptr;
			while (newptr.getLink() != null) {
				newptr = newptr.getLink();
			}
			newptr.setLink(new Node(data));
			newptr.getLink().setLink(null);
		 }
	 }

	public void print(Node ptr) {

		if (ptr == null) {
			 return;
		}
		Node ptr1 = ptr;
		System.out.print(ptr1.getData() + "->");
		while ((ptr1 = ptr1.getLink()) != null) {
			System.out.print(ptr1.getData() + "->");
		}
		System.out.println("/n");

	 }

	public int size(Node ptr) {

		if (ptr == null) {
			return -1;
		}
		Node ptr1 = ptr;
		int i = 1;
		while ((ptr1 = ptr1.getLink()) != null) {
			i++;
		}
		return i;
	}

	
	/**
	 * static inner class for LinkedList Data Structure
	 */
	private static class Node{
		 private int data;
		 private Node link; 		 
		    
		    Node(){
		    	    	
		    }
		    
		    Node(int data){
		    	//mergedList=new Node();
		        this.setData(data);
		        this.setLink(null);       
		    }
		    
		    public int getData(){
		        return this.data;
		    }
		      
		    public Node getLink(){
		        return this.link;
		    }
		    
		    public void setData(int data){
		        this.data=data;
		    }       
		    
		    public void setLink(Node link){
		        this.link=link;
		    }  
	}
	
}

Reverse a LinkedList : recursive and iterative in java

Given a LinkedList reverse it
1. Iterative.
2. Recursive.

/**
* @author vikky.agrawal
* Link List reversal | Iterative and Recursive.
*/

public class LinkedList {

Node node = null;

public static void main(String[] args) {

        LinkedList list = new LinkedList();
        list.operations();

    }

    public void operations() {

        this.node = new Node(10);

        for (int i = 1; i < 6; i++) {
            add(node, (int) (Math.random() * 100));
        }

        System.out.println("Test: iterative, List before reversal");
        print(node);
        this.node=reverse(node); 
    
        
        System.out.println("Test: recursive, List before reversal");
        print(node);
        this.node=this.recursiveReverse(node);
        System.out.println("After recursice reverse list is : ");
        print(node); 
    }
    
    /**
     * Reverse a linked list iterative.
     * Using auxiliary pointers.
     */
    
    public Node reverse(Node ptr) {

        if (ptr == null) {
            System.out.println("List is empty:returning");
            return null;
        }
        Node ptr1 = ptr;
        Node ptr2 = ptr;
        Node ptr3 = null;

        while (ptr1.getLink() != null) {
            ptr2 = ptr1;
            ptr1 = ptr1.getLink();
            ptr2.setLink(ptr3);
            ptr3 = ptr2;

        }
        ptr1.setLink(ptr2); //setting link for the last node;

        System.out.println("Reversed List :");
        this.print(ptr1);
        return ptr1;
    }
    
    /**
     * RecursiveReverse() 
     * Use cases:
     * What is the reverse of null (the empty list)? null.
     * What is the reverse of a one element list? the element. 
     * What is the reverse of an n element list?
     * the reverse of the second element on
     * followed by the first element.
     */

    public Node recursiveReverse(Node root) {

        // base case

        if (root == null || root.getLink() == null) {
            return root;
        }
        Node temp = recursiveReverse(root.getLink());

        // temp contains last element when recursion done
        // take 2 nodes and dry-run
        root.getLink().setLink(root);
        root.setLink(null);
        return temp;

    }
    
    /**
     *  Print reverse of the link list 
     *  reccursively
     */
    
    public void printReverseRecursive(Node root){

        if(root.getLink()!=null){
            printReverseRecursive(root.getLink());
            System.out.println(root.getData());
        }else{
            System.out.println(root.getData());
        }
    }

    /**
     * Helper functions for LinkedList
     */
    public void add(Node ptr, int data) {
        if (ptr == null) {
            System.out.println("Always null ?");
            ptr = new Node(data);
        } else {
            Node newptr = ptr;
            while (newptr.getLink() != null) {
                newptr = newptr.getLink();
            }
            newptr.setLink(new Node(data));
            newptr.getLink().setLink(null);
        }
    }

    public void print(Node ptr) {

  if (ptr == null) {
   return;
  }
  Node ptr1 = ptr;
  System.out.print(ptr1.getData() + "->");
  while ((ptr1 = ptr1.getLink()) != null) {
   System.out.print(ptr1.getData() + "->");
  }
  System.out.println("/n");

 }
public int size(Node ptr) {

        if (ptr == null) {
            return -1;
        }
        Node ptr1 = ptr;
        int i = 1;
        while ((ptr1 = ptr1.getLink()) != null) {
            i++;
        }
        return i;
    }

        /**
     * static inner class for LinkedList 
     * Data Structure
     */
    private static class Node{
         private int data;
         private Node link;         
            
            Node(){
                        
            }
            
            Node(int data){
                //mergedList=new Node();
                this.setData(data);
                this.setLink(null);       
            }
            
            public int getData(){
                return this.data;
            }
              
            public Node getLink(){
                return this.link;
            }
            
            public void setData(int data){
                this.data=data;
            }       
            
            public void setLink(Node link){
                this.link=link;
            }  
    }
    
}

DS for tree and link list

public class Node {
private int data;
 private Node right;
 private Node left;

 Node() {
 }

 Node(int data) {
  this.setData(data);
  this.setLeft(null);
  this.setRight(null);
 }

 public int getData() {
  return this.data;
 }

 public Node getRight() {
  return this.right;
 }

 public Node getLeft() {
  return this.left;
 }

 public void setData(int data) {
  this.data = data;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public void setLeft(Node left) {
  this.left = left;
 }
}




/* Helper class for all Linked list data structures */

class LinkNode {

 private int data;
 private LinkNode link;

 LinkNode() {
 }

 LinkNode(int data) {
  this.setData(data);
  this.setLink(null);
 }

 public int getData() {
  return this.data;
 }

 public LinkNode getLink() {
  return this.link;
 }

 public void setData(int data) {
  this.data = data;
 }

 public void setLink(LinkNode link) {
  this.link = link;
 }
}