Tower of Hanoi solution using recursion in java

Tower of hanoi is one of the basic questions to learn recursion and very commonly asked interview question at beginner and intermediate level.

Section in this post:

1. Problem statement
2. Iterative solution
3. Alternate iterative solution
4. Recursive solution
5. Java Implementation

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

 With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ - 1, where n is the number of disks.

Iterative solution

 

Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.

 

Simpler statement of iterative solution

 

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:

• make the legal move between pegs A and B

• make the legal move between pegs A and C
• make the legal move between pegs B and C
• repeat until complete

For an odd number of disks:

• make the legal move between pegs A and C
• make the legal move between pegs A and B
• make the legal move between pegs C and B
• repeat until complete

In each case, a total of 2ⁿ-1 moves are made.

Equivalent iterative solution

 

Another way to generate the unique optimal iterative solution:

Number the disks 1 through n (largest to smallest).

• If n is odd, the first move is from the Start to the Finish peg.
• If n is even, the first move is from the Start to the Using peg.

Now, add these constraints:

• No odd disk may be placed directly on an odd disk.
• No even disk may be placed directly on an even disk.
• Never undo your previous move (that is, do not move a disk back to its immediate last peg).

Considering those constraints after the first move, there is only one legal move at every subsequent turn.

The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.

Recursive solution

 

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:

• label the pegs A, B, C — these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc n alone on peg A
2. move disc n from A to C
3. move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Below is my Java code to solve the problem recursively.

Class TowerOfHanoi:

public class TowerOfHanoi {

  public static void solveHanoi(int nTop, char fromTower, char midTower,
                              char toTower) {
    if (nTop == 1){
      System.out.println("Disk 1 from " + fromTower + " to " + toTower);
    }else {
      solveHanoi(nTop - 1, fromTower, toTower, midTower);
      System.out.println("Disk " + nTop + " from " + fromTower 
                 + " to " + midTower);
      solveHanoi(nTop - 1, midTower, fromTower, toTower);
    }
  }

  public static void main(String[] args) {
    int nDisks = 3;
    solveHanoi(nDisks, 'A', 'B', 'C');
  }
}

output :
===================================================================
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C

Factorial of a number using recursion in Java

Java program to calculate factorial of integer using recursion


public class Factorial
{
     public int fact(int n) {
if(n==1) {
return 1;
}
else {
return  fact(n-1) * n;
}
    }

public static void main(String args[]){
       int number =4;
Factorial factorial = new factorial();
System.out.println("The factorial of the number is : " + factorial.fact(number);
     }
}

Doubly Link List In Java

In my previous post  I made a simple link list which holds integer values. Moving ahead in  this post I am creating my own doubly link list .

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

Sections in this post: 

1. Link List Interface
2. Link List Node
3. Implementation

Link List Interface

Below is my Link List Interface. It is not at  all mandatory to write Interface for link list . I have written so as to make code more understandable and  to follow good code writing practices.

public interface LLInterface {
 /*
  * different overloaded insert
  */
 public boolean insertAtStart(Node nodeToInsert);
 public boolean insertAtStart(int data);
 public boolean insertAtEnd(Node nodeToInsert);
 public boolean insertAtEnd(int data);
 public boolean insert(Node nodeToInsert, int loc);
 public boolean insert(int data, int loc);

 /*
  * different overloaded delete
  */
 public Integer deleteFirst();
 public Integer deleteLast();
 public Integer delete(int loc);
 public boolean deleteThis(int data);

 /*
  * ADT method to know if list is empty
  * we will be using this method at many places such as
  * before deleting a node to make sure list is already not empty
  */
 public boolean isEmpty();

 /*
  * ADT method to print entire list
  *
  */
 public void printList(Node head);


 /* ADT method to get number of nodes present after the given node.
        *If head is passed as argument then it will return size of list
         *This method should be avoided at places such as,
         *to validate given insertion or deletion location as it
         *internally traverse complete list once.
  */
 public int getSize(Node head);
}

Link List Node

In Link list data is stored in nodes. therefore let's see how to implement a node. For the sake of simplicity I am considering nodes having only integer values but this can be changed easily.

public class Node {
 // data variable will hold integer value 
 private int data;
 //Reference(Pointer) to next node in list 
 private Node next;
 //Reference(Pointer) to previous node in list 
 private Node prev;
 
 public Node(int data) { 
  super();
  this.data = data; 
  this.next = null; 
  this.prev = null;
 }
 
 public Node(){ 
  super();
 }

 /*
  * Getter and setters 
  */
 public int getData() { 
  return data;
 } 

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

 public Node getNext()
 {
  return next;
 }

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

 public Node getPrev() { 
  return prev;
 }

 public void setPrev(Node prev) { 
  this.prev = prev;
 }
}

Implementation

package single;

public class SLL implements LLInterface {

    private Node head;

    @Override
    public boolean insertAtStart(Node nodeToInsert) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // some one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // check if list is empty then set node as head
        if (isEmpty()) {
            head = nodeToInsert;
        }
        // make nodeToInsert as head and head as second
        // node(nodeToInsert-->head-->....)
        else {
            nodeToInsert.setNext(head);
            head = nodeToInsert;
        }
        return true;
    }

    @Override
    public boolean insertAtStart(int data) {

        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at beginning having node
        // object
        // as parameter we will just call that
        // else we can add all the code of that method here itself
        return insertAtStart(nodeToInsert);

    }

    @Override
    public boolean insertAtEnd(Node nodeToInsert) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // Check if list is empty then set node as head
        if (isEmpty()) {
            head = nodeToInsert;
            return true;
        }
        Node currentNode = head;
        while (currentNode.getNext() != null) {
            currentNode = currentNode.getNext();
        }
        currentNode.setNext(nodeToInsert);
        return true;
    }

    @Override
    public boolean insertAtEnd(int data) {

        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at end having node object
        // as
        // parameter we will just call that
        // else we can add all the code of that method here itself
        return insertAtEnd(nodeToInsert);
    }

    @Override
    public boolean insert(Node nodeToInsert, int loc) {
        // Check if node is not null else return
        // We add this check as there can be situation where object is set to
        // null or
        // some one has used default constructor make the node object etc.
        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }
        // validate given location to add node, we wont check with list size
        // here as
        // it internally traverse complete list once
        if (loc < 1) {
            System.out.println("Invalid Location specifed to insert node");
            return false;
        }
        if (loc == 1) {
            insertAtStart(nodeToInsert);
        } else {
            Node currentNode = head;
            // Now we will reach the required location so that we can add node
            // there
            // note that we will stop one place before we want to add node and
            // keep in
            // mind current node is already at first node i.e head
            // e.g. if we want to add new node at location five, then we will
            // traverse
            // till node four
            // we will also check whether current node is not null as location
            // given
            // can be more then list size
            for (int i = 0; i < loc - 2 && currentNode != null; i++) {
                currentNode = currentNode.getNext();
            }
            if (currentNode == null) {
                System.out.println("Invalid Location specifed to insert node");
                return false;
            }
            // Now we need to insert new node at this location
            // so we will make new node's next to point to current node's next
            // and current node will point to new node
            // Note that order is important here
            nodeToInsert.setNext(currentNode.getNext());
            currentNode.setNext(nodeToInsert);
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(int data, int loc) {
        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values using
         * setters
         * 
         * Node nodeToInsert = new Node(); nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */
        Node nodeToInsert = new Node(data);

        // As we already have a method to insert node at end having node object
        // as parameter we will just call that
        // else we can add all the code of that method here itself
        return insert(nodeToInsert, loc);
    }

    @Override
    public Integer deleteFirst() {
        // Check if list is already Empty
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return null;
        }
        /* First save head value to return then Make head to point next node in the list
         *Again order is important
        */
        int deletedNodeValue = head.getData();
        if(null != head.getNext()) {
           head.getNext().setPrev(null);
    head = head.getNext();
 }
 else {
    head = null;
 }
        return deletedNodeValue;
    }

    @Override
    public Integer deleteLast() {
        // Check if list is already Empty
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return null;
        }
        Node currentNode = head;
        // TODO
        return null;
    }

    @Override
    public Integer delete(int loc) {
        // validate given location to delete node, we wont check with list size
        // here
        // as it internally traverse complete list once
        if (loc < 1) {
            System.out.println("Invalid Location specifed to delete node");
            return null;
        }
        Node currentNode = head;
        if (loc == 1) {
            return deleteFirst();
        }
        // we will also check whether current node is not null as location given
        // can
        // be can be more then list size
        for (int i = 0; i < loc - 2 && currentNode != null; i++) {
            currentNode = currentNode.getNext();
        }
        if (currentNode == null) {
            System.out.println("Invalid    Location specifed to delete node");
            return null;
        }
        int deletedNodeValue = currentNode.getData();
        currentNode.setNext(currentNode.getNext().getNext());
        return deletedNodeValue;
    }

    @Override
    public boolean deleteThis(int data) {

        if (head.getData() == data) {            
            return (deleteFirst()!= null);
        }
        // Check if list is already Empty
        // We are checking isEmpty after checking for head data as deleteFirst
        // also
        // has list empty check
        // and we do'nt want to execute this check twice by putting below
        // isEmpty
        // check at start of this method call
        if (isEmpty()) {
            System.out.println("List is empty, can not eprform delete operation");
            return false;
        }

        Node currentNode = head;

        //Iterate list until node to delete is reached or list ends
        while (currentNode.getNext() != null) {
            if (currentNode.getNext().getData() == data) {
                currentNode.setNext(currentNode.getNext().getNext());
                return true;
            }
            currentNode = currentNode.getNext();
        }
        System.out.println("data not present in the list");
        return false;
    }

    /*
     * This method will return true if List is Empty else false List will be
     * empty when head is null
     */
    @Override
    public boolean isEmpty() {
        return null == head;
    }

    @Override
    public void printList(Node head) {
        if (head == null) {

            System.out.println("Invalid node given");
            return;
        }
        Node currentNode = head;
        System.out.print("List is: [");
        while (currentNode != null) {
            System.out.print("    "+currentNode.getData());
            currentNode = currentNode.getNext();
        }
        System.out.println("    ]");
    }

    public void printList() { 
 if(head == null) { 
  System.out.println("Invalid node given"); 
  return;
 }
 Node currentNode = head;
 System.out.print("List is: [ "); 
 while(currentNode != null) {
  System.out.print(currentNode.getData() +" ");
  currentNode = currentNode.getNext();
 }
 System.out.println("]");
  }
 
     @Override
    public int getSize(Node head) {
        int count = 0;
        Node currentNode = head;
        while (currentNode != null) {
            count++;
            currentNode = currentNode.getNext();
        }
        return count;
    }

    public static void main(String[] args) {
        SLL myLst = new SLL();

        myLst.insert(new Node(41),0);
        myLst.insert(new Node(42),2);
        myLst.insert(new Node(43),1);
        myLst.insert(new Node(44),1);
        myLst.insert(new Node(45),2);
        myLst.insert(new Node(46),4);
        myLst.insert(null,3);

        myLst.insert(51,0);
        myLst.insert(52,2);
        myLst.insert(53,1);
        myLst.insert(54,1);
        myLst.insert(55,2);
        myLst.insert(56,4);

        myLst.insertAtStart(1);
        myLst.insertAtStart(2);
        myLst.insertAtStart(3);
        myLst.insertAtStart(4);

        myLst.insertAtStart(new    Node(11));
        myLst.insertAtStart(new    Node(12));
        myLst.insertAtStart(new    Node(13));
        myLst.insertAtStart(new    Node(14));
        myLst.insertAtStart(null);

        myLst.insertAtEnd(21);
        myLst.insertAtEnd(22);
        myLst.insertAtEnd(23);
        myLst.insertAtEnd(24);

        myLst.insertAtEnd(new Node(31));
        myLst.insertAtEnd(new Node(32));
        myLst.insertAtEnd(new Node(33));
        myLst.insertAtEnd(new Node(34));
        myLst.insertAtEnd(null);

        myLst.printList(myLst.head);
        System.out.println("===========================deletefirst=================");
        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.printList(myLst.head);
        System.out.println("=========delete from location==============");        
        myLst.delete(0);
        myLst.delete(1);
        myLst.delete(30);        
        myLst.delete(2);
        myLst.printList(myLst.head);
        System.out.println("=========delete this(data)========");
        myLst.deleteThis(31);
        myLst.deleteThis(131);
        myLst.deleteThis(45);
        myLst.printList(myLst.head);
    }
}

If we run the program we will get output like this:

Output

==========================================================================

Invalid Location specifed to insert node
Invalid Location specifed to insert node
Node you are trying to insert is null
Invalid Location specifed to insert node
Node you are trying to insert, is null
Node you are trying to insert is null
List is: [14    13    12    11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
===========================delecefirst================================
List is: [11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
 ============================deleteloc================================
Invalid Location specifed to delete node
Invalid Location specifed to delete node
List is: [4    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
============================deletethis(data)============================
data not present in the list
List is: [4    2    1    54    55    53    56    44    52    43    46    21    22    23    24    32    33    34    ]
 ============================deletelast================================
34
List is: [4    2    1    54    55    53    56    44    52    43    46    21    22    23    24    32    33    ]

In next post we will talk about circular link list and then we will see some commonly asked question on link list.

Link list Implementation in Java

linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays.

Sections in this post: 

1. Link List Interface
2. Link List Node
3. Implementation

Link List Interface

Below is my Link List Interface. It is not at  all mandatory to write Interface for link list . I have written so as to make code more understandable and  to follow good code writing practices.

public interface LLInterface {
 /*
  * different overloaded insert
  */
 public boolean insertAtStart(Node nodeToInsert);
 public boolean insertAtStart(int data);
 public boolean insertAtEnd(Node nodeToInsert);
 public boolean insertAtEnd(int data);
 public boolean insert(Node nodeToInsert, int loc);
 public boolean insert(int data, int loc);

 /*
  * different overloaded delete
  */
 public Integer deleteFirst();
 public Integer deleteLast();
 public Integer delete(int loc);
 public boolean deleteThis(int data);

 /*
  * ADT method to know if list is empty
  * we will be using this method at many places such as
         * before deleting a node to make sure list is already not empty
  */
 public boolean isEmpty();

 /*
  * ADT method to print entire list
  *
  */
 public void printList(Node head);


 /* ADT method to get number of nodes present after the given node.
        *If head is passed as argument then it will return size of list
         *This method should be avoided at places such as,
         *to validate given insertion or deletion location as it
         *internally traverse complete list once.
  */
 public int getSize(Node head);
}

Link List Node

In Link list data is stored in nodes. therefore let's see how to implement a node. For the sake of simplicity I am considering nodes having only integer values but this can be changed easily.

public class Node {

    // data variable will hold integer
    private int data;

    // Reference(Pointer) to next node
    private Node next;

    public Node(int data) {
        super();
        this.data = data;
        this.next = null;
    }

    public Node() {
        super();
    }
    /*
     * Getter and setters
     */

    public int getData() {
        return data;
    }

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

    public Node getNext() {
        return next;
    }

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

Implementation

Now lets see how to implement link list. Whenever I am saying link list I am referring to singly link list. refer my other posts for Doubly link list and circular link list .

public class SLL implements LLInterface {

    private Node head;

    @Override
    public boolean insertAtStart(Node nodeToInsert) {
       /* Check if node is not null else return
        * We add this check as there can be situation where object is set
        * to null or some one has used default constructor make the node
        * object etc.
        */

        if (nodeToInsert == null) {
            System.out.println("Node you are trying to insert is null");
            return false;
        }

        // check if list is empty then set node as head

        if (isEmpty()) {
            head = nodeToInsert;
        }

        // make nodeToInsert as head and head as second
        // node(nodeToInsert-->head-->....)

        else {
            nodeToInsert.setNext(head);
            head = nodeToInsert;
        }
        return true;
    }

    @Override
    public boolean insertAtStart(int data) {

        /*
         * we can have two approaches to get new node
         * 
         * First Approach: Use default constructor and then set values
         * using setters
         * Node nodeToInsert = new Node();
         * nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         *
         * Second approach: Use overloaded constructor of Node class
         */

        Node nodeToInsert = new Node(data);

        /* As we already have a method to insert node at beginning having
         * node object as parameter we will just call that
         * else we can add all the code of that method here itself
         */

        return insertAtStart(nodeToInsert);
     }

    @Override
    public boolean insertAtEnd(Node nodeToInsert) {

        /* Check if node is not null else return
         * We add this check as there can be situation where object 
        * is set to null or one has used default constructor make the node
        * object etc.
         */

        if (nodeToInsert == null) {

            System.out.println("Node you are trying to insert is null");
            return false;
        }

        // Check if list is empty then set node as head

        if (isEmpty()) {

            head = nodeToInsert;
            return true;
        }

        Node currentNode = head;
        while (currentNode.getNext() != null) {
            currentNode = currentNode.getNext();
        }

        currentNode.setNext(nodeToInsert);
        return true;
    }

    @Override
    public boolean insertAtEnd(int data) {

        /*
         * we can have two approaches to get new node 

         * First Approach: Use default constructor and then set

         * values using setters 

         * Node nodeToInsert = new Node(); 
         * nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */

        Node nodeToInsert = new Node(data);

        /* As we already have a method to insert node at end having
         * node object as parameter we will just call that
         * else we can add all the code of that method here itself
         */
        
         return insertAtEnd(nodeToInsert);
    }

    @Override
    public boolean insert(Node nodeToInsert, int loc) {

        /* Check if node is not null else return
         * We add this check as there can be situation where
         * object is set to null or some one has used default constructor
         * make the node object etc.
         */
         if (nodeToInsert == null) {

            System.out.println("Node you are trying to insert is null");
            return false;
        }

        /* validate given location to add node, we wont check with list
         * size here as it internally traverse complete list once
         */
         if (loc < 1) {
           System.out.println("Invalid Location specified to insert node");
           return false;
        }

        if (loc == 1) {
            insertAtStart(nodeToInsert);
        } else {

            Node currentNode = head;

            /* Now we will reach the required location so that we can add
             * node there.Note that we will stop one place before we want
             * to add node and keep in mind current node is already at head
             * e.g. if we want to add new node at location five, then we
             * will traverse till node four.
             * We will also check whether current node is not null
             * as location given can be more then list size
             */
            
             for (int i = 0; i < loc - 2 && currentNode != null; i++) {
                currentNode = currentNode.getNext();
            }

          if (currentNode == null) {
            System.out.println("Invalid Location specified to insert node");
            return false;
          }

            /* Now we need to insert new node at this location.
             * So we make new node's next to point to current node's next
             * and current node will point to new node.
             * Note that order is important here.
             */
            nodeToInsert.setNext(currentNode.getNext());
            currentNode.setNext(nodeToInsert);

            return true;
        }

        return false;
    }

    @Override
    public boolean insert(int data, int loc) {

        /*
         * we can have two approaches to get new node
         *
         * First Approach: Use default constructor and
         * then set values using setters
         *
         * Node nodeToInsert = new Node();
         * nodeToInsert.setData(data);
         * nodeToInsert.setNext(null);
         * 
         * Second approach: Use overloaded constructor of Node class
         */

        Node nodeToInsert = new Node(data);

        /* As we already have a method to insert node at end
         * having node object as parameter we will just call that
         * else we can add all the code of that method here itself 
         */

        return insert(nodeToInsert, loc);
    }

    @Override
    public Integer deleteFirst() {

        // Check if list is already Empty

        if (isEmpty()) {
          System.out.println("List empty,can not perform delete operation");
          return null;
        }

        /* First save head value to return,then Make head to point next
         * node in the list
         * Again order is important 
         */

        int deletedNodeValue = head.getData();
        head = head.getNext();
        return deletedNodeValue;
    }

    @Override
    public Integer deleteLast() {

        //Check if list is already Empty 
 if(isEmpty()) {
  System.out.println("List is empty, return null, can not perform delete operation");  
  return null;
 }

 if(head.getNext() == null) {
  int deletedNode = head.getData() ;
  head = null;
  return deletedNode;
 }
 Node currentNode = head.getNext();
 Node prevNode = head;
 while(currentNode.getNext() != null) { 
  prevNode =currentNode;
  currentNode = currentNode.getNext();
 }
 int deletedNode = currentNode.getData(); 
 currentNode = null; 
 prevNode.setNext(null); 
 return deletedNode;
    }

    @Override
    public Integer delete(int loc) {

        /* validate given location to delete node,
         * we wont check with list size here
         * as it internally traverse complete list once
         */
        if (loc < 1) {

            System.out.println("Invalid Location specified to delete");
            return null;
        }

        Node currentNode = head;

        if (loc == 1) {
            return deleteFirst();
        }

        /* we will also check whether current node is not null
         * as location given can be can be more then list size
         */
        for (int i = 0; i < loc - 2 && currentNode != null; i++) {
            currentNode = currentNode.getNext();
        }

        if (currentNode == null) {
            System.out.println("Invalid Location specified to delete");
            return null;
        }

        int deletedNodeValue = currentNode.getData();
        currentNode.setNext(currentNode.getNext().getNext());
        
       return deletedNodeValue;

    }

    @Override
    public boolean deleteThis(int data) {

        if (head.getData() == data) {
            return (deleteFirst()!= null);
        }

        /* Check if list is already Empty
         * We are checking isEmpty after checking for head data as
         * deleteFirst also has list empty check
         * and we don't want to execute this check twice
         * by putting below isEmpty check at start of this method call
         */
        
        if (isEmpty()) {

          System.out.println("List empty,can not perform delete operation");
            return false;
        }
        Node currentNode = head;

        //Iterate list until node to delete is reached or list ends

        while (currentNode.getNext() != null) {

            if (currentNode.getNext().getData() == data) {

                currentNode.setNext(currentNode.getNext().getNext());
                return true;
            }
            currentNode = currentNode.getNext();
        }

        System.out.println("data not present in the list");
        return false;
    }

    /*
     * This method will return true if List is Empty else false.
     * List will be empty when head is null
     */

    @Override
    public boolean isEmpty() {
        return null == head;
    }

    @Override
    public void printList(Node head) {

        if (head == null) {
            System.out.println("Invalid node given");
            return;
        }

        Node currentNode = head;
        System.out.print("List is: [");

        while (currentNode != null) {
            System.out.print("    "+currentNode.getData());
            currentNode = currentNode.getNext();
        }
        System.out.println("    ]");
    }
 
     public void printList() {
 if (head == null) {

  System.out.println("Invalid node given");
  return;
 }
 Node currentNode = head;
 System.out.print("List is: [");
 while (currentNode != null) {
  System.out.print(" "+currentNode.getData());
  currentNode = currentNode.getNext();
 }
 System.out.println(" ]");
   }
 
      @Override
    public int getSize(Node head) {

        int count = 0;
        Node currentNode = head;

        while (currentNode != null) {

            count++;
            currentNode = currentNode.getNext();
        }
        return count;
    }

    public static void main(String[] args) {

        SLL myLst = new SLL();

        myLst.insert(new Node(41),0);
        myLst.insert(new Node(42),2);
        myLst.insert(new Node(43),1);
        myLst.insert(new Node(44),1);
        myLst.insert(new Node(45),2);
        myLst.insert(new Node(46),4);
        myLst.insert(null,3);
        
        myLst.insert(51,0);
        myLst.insert(52,2);
        myLst.insert(53,1);
        myLst.insert(54,1);
        myLst.insert(55,2);
        myLst.insert(56,4);

        myLst.insertAtStart(1);
        myLst.insertAtStart(2);
        myLst.insertAtStart(3);
        myLst.insertAtStart(4);

        myLst.insertAtStart(new Node(11));
        myLst.insertAtStart(new Node(12));
        myLst.insertAtStart(new Node(13));
        myLst.insertAtStart(new Node(14));

        myLst.insertAtStart(null);

        myLst.insertAtEnd(21);
        myLst.insertAtEnd(22);
        myLst.insertAtEnd(23);
        myLst.insertAtEnd(24);

        myLst.insertAtEnd(new Node(31));
        myLst.insertAtEnd(new Node(32));
        myLst.insertAtEnd(new Node(33));
        myLst.insertAtEnd(new Node(34));
        myLst.insertAtEnd(null);

        myLst.printList(myLst.head);
        System.out.println("=================deletefirst===============");

        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.deleteFirst();
        myLst.printList(myLst.head);

        System.out.println("=========delete from location==============");       

        myLst.delete(0);
        myLst.delete(1);
        myLst.delete(30);
        myLst.delete(2);

        myLst.printList(myLst.head);
        System.out.println("=========delete this(data)=================");

        myLst.deleteThis(31);
        myLst.deleteThis(131);
        myLst.deleteThis(45);

        myLst.printList(myLst.head);
    }
}

If we run the program we will get output like this:

Output

==========================================================================

Invalid Location specified to insert node
Invalid Location specified to insert node
Node you are trying to insert is null
Invalid Location specified to insert node
Node you are trying to insert is null
Node you are trying to insert is null
List is: [    14    13    12    11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
===========================deletefirst=============================
List is: [    11    4    3    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
==========================delete from location========================
Invalid Location specified to delete node
Invalid Location specified to delete node
List is: [    4    2    1    54    55    53    56    44    52    45    43    46    21    22    23    24    31    32    33    34    ]
==========================delete this(data)==========================
data not present in the list
List is: [    4    2    1    54    55    53    56    44    52    43    46    21    22    23    24    32    33    34    ]

In next post we will talk about doubly Link List and Circular Link List and then some commonly asked question based on link list.