using System;
using System.Collections.Generic;
using System.Text;

namespace Double_Link_List
{
    class Program
    {
        static void Main(string[] args)
        {
            DoubleLinkList s = new DoubleLinkList();
            s.InsertionAtFirst(2);
            s.InsertionAtFirst(1);
            Console.WriteLine("Traversing is......................");
            s.tarvasing();
            Console.WriteLine("Now insertion at last.............");
            s.InsertionAtLast(4);
            s.InsertionAtLast(5);
            Console.WriteLine("Traversing is......................");
            s.tarvasing();
            s.IsertionAtAnyPlace(3, 2);
            s.tarvasing();
            s.deletionatfront();
            s.tarvasing();c
        }
    }
    class Node
    {
        public object data;
        public Node llink;
        public Node rlink;
    }
    class DoubleLinkList
    {
        Node header = new Node();

        public void tarvasing()
        {
            Node pr = header;
            while (pr.rlink != null)
            {
                pr = pr.rlink;
                Console.WriteLine(pr.data);

}


        }

        public void InsertionAtFirst(object item)
        {
            header.llink = null;
            Node pr = header.rlink;
            Node newnode = new Node();
            //if(newnode.rlink!=null)
            //{
            newnode.llink = header.rlink;
            header.rlink = newnode;
            newnode.rlink = pr;
          //  pr.llink = newnode.rlink;
            newnode.data = item;
            
            
            Console.WriteLine("Value placed at front is   " + newnode.data);
            //}
            /*else 
            {
                Console.WriteLine("over flow");
            }*/

        }
        public void InsertionAtLast(object vaule)
        {
            try
            {
                header.llink = null;
                Node pr = header;
                while (pr.rlink != null)
                {
                    pr = pr.rlink;
                }
                Node newnode = new Node();
                pr.rlink = newnode;
                newnode.llink = pr;
                newnode.data = vaule;
                newnode.rlink = null;
                Console.WriteLine("Value is placed at last " + newnode.data);
            }
            catch (Exception er)
            {
                Console.WriteLine(er.Message);
            }
        }
        public void IsertionAtAnyPlace(object value, object key)
        {
            header.llink = null;
            Node pr = header;
            Node newnod = new Node();

            while ((pr.data != key) && (pr.rlink != null))
            {
                pr = pr.rlink;
                Console.WriteLine("key is not matched");
                if (pr.data.ToString() == key.ToString())
                    break;
            }
            /*if (newnod == null)
            {
                Console.WriteLine("memory is not availble");
            }*/
            if (pr.rlink == null)
            {

                newnod.llink = pr;
                pr.rlink = newnod;
                newnod.rlink = null;
                newnod.data = value;
                Console.WriteLine("value placed at any place is " + newnod.data);
            }
            else
            {
                Node pr1;
                pr1 = pr.rlink;
                newnod.llink = pr;
                newnod.rlink = pr1;
                pr.rlink = newnod;
                pr1.llink = newnod;
                pr = newnod;
                newnod.data = value;
                Console.WriteLine("value placed at any place is two " + newnod.data);
            }
        }
        public void deletionatfront() 
        {
            Node pr = header.rlink;
            Node pr1 = pr.rlink;
            header.rlink = pr1.llink;
            Console.WriteLine("value is deleted from first is : " + pr.data);
        }
    }
}