import java.lang.*;

class DoublyLinkedList {
    Node head;
    // not using parameterized constructor would by default
    // force head instance to become null
    // Node head = null;  // can also do this, but not required

    // Node Class
    class Node {
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }

    public void insertBeginning(int data) {
        // Creating newNode memory & assigning data value
        Node freshNode = new Node(data);

        freshNode.next = head;
        freshNode.prev = null;

        // if DLL had already >=1 nodes
        if (head != null)
            head.prev = freshNode;

        // changing head to this
        head = freshNode;
    }

    public void insertEnd(int data) {
        // Creating newNode memory & assigning data value
        Node freshNode = new Node(data);

        // assign data
        // since this will be the last node its next will be NULL
        freshNode.next = null;

        //if we are entering the first node
        if (head == null) {
            head = freshNode;
            freshNode.prev = null;
            return;
        }

        Node last = head;

        // traverse to the current last node
        while (last.next != null)
            last = last.next;

        // assign current last node's next to this new node
        // assign new node's previous to this last node
        last.next = freshNode;
        freshNode.prev = last;
        // new_node becomes the last node now

    }

    public void insertAfterPosition(int n, int data) {
        int len = getLength(head);

        // if insertion position is 0 means entering at start
        if (n == 0) {
            insertBeginning(data);
            return;
        }
        // means inserting after last item
        if (n == len) {
            insertEnd(data);
            return;
        }

        // else insertion will happen somewhere in the middle


        if (n < 1 || len < n) System.out.println("Invalid position");
        else { Node freshNode = new Node(data);
            // can remove null assignments also (constructor takes care of these)
            // added just for explanation purpose

            freshNode.next = null;

            freshNode.prev = null;
            // nthNode used to traverse the Linked List

            Node nthNode = head;

            // traverse till the nth node
           
            while (--n > 0) {
            nthNode = nthNode.next;
        }

        Node nextNode = nthNode.next; // (n+1)th node

        // assigning (n+1)th node's previous to this new node
        nextNode.prev = freshNode;

        // new_node's next assigned to (n+1)th node
        freshNode.next = nextNode;
        // new_node's previous assigned to nth node
        freshNode.prev = nthNode;

        // assign nth node's next to new_node
        nthNode.next = freshNode;
    }
}

    public void printList() {
        Node node = head;
        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while (node != null) {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println();
    }

    // required for insertPosition() method
    public int getLength(Node node) {
        int size = 0;
        // traverse to the last node each time incrementing the size
        while (node != null) {
            node = node.next;
            size++;
        }
        return size;
    }

}
class Main{

    public static void main(String args[])
    {
        DoublyLinkedList doublylist = new DoublyLinkedList();

        doublylist.insertBeginning(3);
        doublylist.insertBeginning(2);
        doublylist.insertBeginning(1);

        doublylist.printList();

        doublylist.insertEnd(4);
        doublylist.insertEnd(6);
        doublylist.insertEnd(7);
        doublylist.insertEnd(8);

        doublylist.printList();

        //Inserts after 4th position
        doublylist.insertAfterPosition(4,5);

        doublylist.printList();
    }
}

import java.lang.*;

// Node Class
class Node {
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
        prev = null;
    }
}

class Main
{
    static Node insertBeginning(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if(head !=null)
            head.prev = newNode;

        // changing head to this
        head = newNode;

        return head;
    }

    static Node insertEnd(Node head, int data) {

        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // assign data
        // since this will be the last node its next will be NULL
        newNode.next = null;

        //if we are entering the first node
        if(head==null){
            head = newNode;
            newNode.prev = null;
            return head;
        }

        Node last = head;

        // traverse to the current last node
        while(last.next!=null)
            last = last.next;

        // assign current last node's next to this new node
        // assign new node's previous to this last node
        last.next = newNode;
        newNode.prev = last;
        // new_node becomes the last node now

        return head;
    }

    static Node insertAfterPosition(int n, int data, Node head) {
        int len = getLength(head);

        // if insertion position is 0 means entering at start
        if(n == 0){
            head = insertBeginning(head, data);
            return head;
        }
        // means inserting after last item
        if(n == len){
            head = insertEnd(head, data);
            return head;
        }

        // else insertion will happen somewhere in the middle


        if(n < 1 || len < n) System.out.println("Invalid position");
        else { Node newNode = new Node(data);
            // can remove null assignments also (constructor takes care of these)
            // added just for explanation purpose
            newNode.next = null;
            newNode.prev = null;
            // nthNode used to traverse the Linked List

            Node nthNode = head;

            // traverse till the nth node

            while(--n > 0){
            nthNode = nthNode.next;
        }

        Node nextNode = nthNode.next; // (n+1)th node

        // assigning (n+1)th node's previous to this new node
        nextNode.prev = newNode;

        // new_node's next assigned to (n+1)th node
        newNode.next= nextNode;
        // new_node's previous assigned to nth node
        newNode.prev = nthNode;

        // assign nth node's next to new_node
        nthNode.next = newNode;
    }
        return head;
}

    static void printList(Node temp) {

        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while(temp!=null)
        {
            System.out.print(temp.data + " ");
            end = temp;
            temp = temp.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println();
    }

    // required for insertAfterPosition() method
    static int getLength(Node node){
        int size=0;

        // traverse to the last node each time incrementing the size
        while(node!=null)
        {
            node = node.next;
            size++;
        }
        return size;
    }

    public static void main(String args[])
    {
        Node head = null;
        head = insertBeginning(head,3);
        head = insertBeginning(head,2);
        head = insertBeginning(head,1);

        printList(head);

        head = insertEnd(head,4);
        head = insertEnd(head,6);
        head = insertEnd(head,7);
        head = insertEnd(head,8);

        printList(head);

        //Inserts after 4th position
        head = insertAfterPosition(4,5,head);

        printList(head);

    }
}