/**
 * Node class is storage for Linked list node.
 * which has data, prev and next node.
 */
class DLLNode {
    //To hold previous node
    private DLLNode prev;
    
    //To hold data
    private int data;
    
    //To hold next node object
    private DLLNode next;
    
    //Constructor to create Node with data.
    public DLLNode(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 DLLNode getNext() {
        return next;
    }
    public void setNext(DLLNode next) {
        this.next = next;
    }
    public DLLNode getPrev() {
        return prev;
    }
    public void setPrev(DLLNode prev) {
        this.prev = prev;
    }
}

/**
 * List of abstract methods for LinkedList Implementation
 */
interface DoublyLinkedListDAO {
    //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 DLLNode removeAtBegin();
    
    //remove node at end
    public DLLNode 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 DoublyLinkedListImpl implements DoublyLinkedListDAO {
    private int length;
    private DLLNode head;
    
    public DoublyLinkedListImpl(){
        //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
        DLLNode newNode = new DLLNode(data);
        
        //Setting next node as current head node
        newNode.setNext(head);
        
        //Setting current node as previous node for head
        if (head != null)
        head.setPrev(newNode);
        
        //head node pointing new node.
        head = newNode;
        
        //increasing length by 1.
        length++;
    }

    //insert data at end
    public void insertAtEnd(int data) {
        DLLNode newNode = new DLLNode(data);
        
        if (head == null) {
            //no data in linked list
            head = newNode;
        }
        else {
            //if list has nodes.
            
            DLLNode 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);
                    
                    //Setting newNode previous node
                    newNode.setPrev(current);
                    
                    length++;
                    break;
                }
                
                current = current.getNext();
            }
        }
    }

    //insert data at specific position
    public void insert(int data, int position) {
        DLLNode newNode = new DLLNode(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.setPrev(newNode);
            head = newNode;
            length++;
        }
        else {
            //in different position
            int currentPosition = 1;
            DLLNode current = head;
            
            while(current != null) {
                if (currentPosition == position) {
                    //Pointing new node previous and next
                    newNode.setNext(current);
                    newNode.setPrev(current.getPrev());
                    
                    //Setting current node prev to next node.
                    current.setPrev(newNode);
                    newNode.getPrev().setNext(newNode);
                
                    length++;
                    break;
                }
                
                current = current.getNext();
                currentPosition++;
            }
        }
    }

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

    //remove node at end
    public DLLNode 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
            DLLNode current = head;
            
            while(current != null) {
                
                //reached last node
                if (current.getNext() == null) {
                    current.getPrev().setNext(null);
                    
                    length--;
                    break;
                }
                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;
            DLLNode current = head;
            while (current != null) {
                
                if (currentPosition == position) {
                    current.getPrev().setNext(current.getNext());
                    length--;
                    break;
                }
                
                current = current.getNext();
                currentPosition++;
            }
        }
    }

    //get position of the passing data.
    public int getPosition(int data) {
        int position = 1;
        DLLNode 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() {
        DLLNode 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 DoublyLinkedListExample {
    
    /**
     * printList - prints the linked list and length of the linked list.
     */
    public static void printList(DoublyLinkedListDAO list) {
        System.out.println("LinkedList: "+list);
        System.out.println("Length: "+list.getLength());
        System.out.println();
    }
    
    public static void main(String[] args) {
        DoublyLinkedListDAO list = new DoublyLinkedListImpl();
        
        /*
         * 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));
    }
}