/**
 * Node class is storage for Linked list node.
 * which has data and next node.
 */
class Node {
    //To hold data
    private int data;
    
    //To hold next node object
    private Node next = null;
    
    //Constructor to create Node with data.
    public Node(int data) {
        this.data = data;
    }
    
    //Setters and Getters for data and next members.
    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;
    }
}

/**
 * List of abstract methods for LinkedList Implementation
 */
interface LinkedListDAO {
    //insert data at begin
    public void insertAtBegin(int data);
    
    //insert data at end
    public void insertAtEnd(int data);
    
    //insert data at specific position
    public void insert(int data, int position);
    
    //remove node at first
    public Node removeAtBegin();
    
    //remove node at end
    public Node removeAtEnd();
    
    //remove node at specific position
    public void remove(int position);
    
    //get position of the passing data.
    public int getPosition(int data);
    
    //to get length of the linked list.
    public int getLength();
    
    //clear linked list
    public void clearList();
    
    //to read linkedlist as string.
    public String toString();
}

/**
 * LinkedListImpl is implementation of the LinkedList Data structure.
 * insertion: insertAtFirst, insertAtEnd, insertAtPostion
 * deletion: deleteAtFirst, deleteAtEnd, deleteAtPosition
 * length
 * clearList
 * get position
 * toString
 */
class LinkedListImpl implements LinkedListDAO {
    private int length;
    private Node head;
    
    public LinkedListImpl(){
        //initialize length as zero when creating linkedlist.
        this.length = 0;
        head = null;
    }
    
    //insert data at begin
    public void insertAtBegin(int data) {
        //Creating node with new data
        Node newNode = new Node(data);
        
        //Setting next node as current head node
        newNode.setNext(head);
        
        //head node pointing new node.
        head = newNode;
        
        //increasing length by 1.
        length++;
    }

    //insert data at end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        
        if (head == null) {
            //no data in linked list
            head = newNode;
        }
        else {
            //if list has nodes.
            
            Node current = head;
            //Looping till reaching end node.
            while(current != null) {
                
                //If current node is end node.
                if (current.getNext() == null) {
                    //Setting last node next node is new node.
                    current.setNext(newNode);
                    
                    length++;
                    break;
                }
                
                current = current.getNext();
            }
        }
    }

    //insert data at specific position
    public void insert(int data, int position) {
        Node newNode = new Node(data);
        
        //fixing position
        if (position < 1) {
            position = 1;
        }
        if (position > length) {
            position = length;
        }
        
        if (head == null) {
            //if list is empty
            
        }
        else if (position == 1) {
            //if insert at first position
            newNode.setNext(head);
            head = newNode;
            length++;
        }
        else {
            //in different position
            int currentPosition = 1;
            Node current = head;
            Node previous = null;
            
            while(current != null) {
                if (currentPosition == position) {
                    //Setting new node's next node is current node's next node.
                    newNode.setNext(current);
                    
                    //current node's next node is new Node
                    previous.setNext(newNode);
                
                    length++;
                    break;
                }
                
                previous = current;
                current = current.getNext();
                currentPosition++;
            }
        }
    }

    //remove node at first
    public Node removeAtBegin() {
        //Creating temp variable to hold head node.
        Node temp = head;
        
        if (temp != null) {
            //taking next node from head node and point to current head.
            head = temp.getNext();
            temp.setNext(null);
            length--;
        }
        
        //returning delinked node from linked list
        return temp;
    }

    //remove node at end
    public Node removeAtEnd() {
        if (head == null) {
            //if empty list
            return null;
        }
        else if (head.getNext() == null) {
            //if has one head node.
            head = null;
            return head;
        }
        else {
            //if has more than one node
            Node current = head;
            Node previous = null;
            
            while(current != null) {
                
                //reached last node
                if (current.getNext() == null) {
                    previous.setNext(null);
                    length--;
                    
                    break;
                }
                
                previous = current;
                current = current.getNext();
            }
            
            //sending last node as output
            return current;
        }
    }

    //remove node at specific position
    public void remove(int position) {
        //fix position
        if (position < 1) {
            position = 1;
        }
        if (position > length) {
            position = length;
        }
        
        if (head == null) {
            return;
        }
        else if (position == 1) {
            //if at 1.
            head = head.getNext();
            length--;
            return;
        }
        else {
            //greater than position one.
            int currentPosition = 1;
            Node current = head;
            Node previous = null;
            while (current != null) {
                
                if (currentPosition == position) {
                    previous.setNext(current.getNext());
                    length--;
                    break;
                }
                
                previous = current;
                current = current.getNext();
                currentPosition++;
            }
        }
    }

    //get position of the passing data.
    public int getPosition(int data) {
        int position = 1;
        Node current = head;
        while(current != null) {
            if (current.getData() == data) {
                
                return position;
            }
            
            position++;
            current = current.getNext();
        }
        
        return -1;
    }

    //to get length of the linked list.
    public int getLength() {
        return this.length;
    }

    //clear linked list
    public void clearList() {
        head = null;
        length = 0;
    }

    //to read linkedlist as string.
    public String toString() {
        Node current = head;
        StringBuilder sb = new StringBuilder();
        while(current != null) {
            sb.append(current.getData());
            
            if (current.getNext() != null) {
                sb.append(",");
            }
            
            current = current.getNext();
        }
        
        return sb.toString();
    }
}

/**
 *
 *  Example of using LinkedList Implementation
 *
 */
public class SinglyLinkedListExample {
    
    /**
     * printList - prints the linked list and length of the linked list.
     */
    public static void printList(LinkedListDAO list) {
        System.out.println("LinkedList: "+list);
        System.out.println("Length: "+list.getLength());
        System.out.println();
    }
    
    public static void main(String[] args) {
        LinkedListDAO list = new LinkedListImpl();
        
        /*
         * insert data at first
         */
        list.insertAtBegin(10);
        list.insertAtBegin(20);
        list.insertAtBegin(30);
        printList(list);
        
        
        /*
         * insert data at end
         */
        list.insertAtEnd(40);
        list.insertAtEnd(50);
        list.insertAtEnd(60);
        printList(list);
        
        
        /*
         * insert at specific pos
         */
        list.insert(12, 2);
        printList(list);
        
        
        /*
         * remove from begin
         */
        list.removeAtBegin();
        printList(list);

        
        /*
         * remove at end
         */
        list.removeAtEnd();
        printList(list);
        
        
        /*
         * remove at position
         */
        list.remove(1);
        printList(list);
        
        
        /*
         * Get current position of the data.
         */
        System.out.println("POSITION list[10]: "+list.getPosition(10));
        System.out.println("POSITION list[112]: "+list.getPosition(112));
    }
}