using System;

​

public class DoublyLinkedList

{

    Node head;

    public class Node

    {

        public int data;

        public Node next;

        public Node prev;

        public Node (int val)

        {

            data = val;

            next = null;

            prev = null;

        }

    }

    private void insertAtPos(int key, int position)

    {

        Node newNode = new Node(key);

        int k = 1;

        if(head == null){

            head = newNode;

            return;

        }

        if(position == 1)

        {

            //  Insert at beginning

            newNode.next = head;

            head.prev = newNode;

            head = newNode;

            return;

        }

        else 

        {

            Node cur = head;

            Node prev = head;

            while(k < position && cur != null)

            {

                k++;

                prev = cur;

                cur = cur.next;             

            }

            if(prev.next == null && k!= position)

            {

                Console.WriteLine("Position is incorrect");

                return;

            }

            newNode.next = cur;

            if(cur!=null)

            {

                cur.prev = newNode;

            }

            prev.next = newNode;

            newNode.prev = prev;

        }

        return;     

    }

    private void printDLL()

    {

        Node cur = head;

        if(head == null){

            Console.WriteLine("No linked list exists");

            return;

        }

        while(cur!=null){

            Console.Write(cur.data);

            Console.Write("-->");

            cur = cur.next;         

        }

        Console.WriteLine();Console.WriteLine();        

    }

    private void deleteAtPos(int position)

    {

        if(head == null)

        {

            Console.WriteLine("Linked list does not exist");

            return;

        }

        if(position == 1)

        {

            if(head.next == null)

            {

                // Delete the only node

                head = null;

                return;

            }

            else

            {

                head = head.next;

                head.prev = null;

                return;

            }

        }

        else

        {

            Node cur = head;

            Node prev = head;

            int k = 1;

            while(k<position && cur!=null)

            {

                k++;

                prev = cur;

                cur = cur.next;

            }

            if(k != position)

            {

                Console.WriteLine("Incorrect position to delete");

                return;

            }

            prev.next = cur.next;

            if(cur.next != null)

            {

                cur.next.prev = prev;               

            }

        }

    }

    public static void Main(String[] args)

    {

        DoublyLinkedList dll = new DoublyLinkedList();

        //  Inserting at front

        dll.insertAtPos(5, 1);

        dll.printDLL();

        //  Inserting at last

        dll.insertAtPos(6, 2);

        dll.printDLL();

        dll.insertAtPos(7, 2);

        dll.printDLL();

        dll.insertAtPos(4, 7);

        dll.printDLL();

        dll.insertAtPos(-1, 3);

        dll.printDLL();

        dll.insertAtPos(89, 1);

        dll.printDLL();

        //  Deletion at front

        dll.deleteAtPos(1);

        dll.printDLL();

        //  Deletion in middle

        dll.deleteAtPos(2);

        dll.printDLL();

        //  Deletion at end

        dll.deleteAtPos(3);

        dll.printDLL();

        //  Incorrect deletion

        dll.deleteAtPos(5);

        dll.printDLL();

    }

}