using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int? nTest2 = null;     

        if (nTest2.HasValue)

            Console.WriteLine("nTest2 hat einen Wert");

        else

            Console.WriteLine("nTest2 hat keinen Wert");

        nTest2 = 7;

        if (nTest2.HasValue)

            Console.WriteLine("nTest2 hat einen Wert");

        else

            Console.WriteLine("nTest2 hat keinen Wert");

        LinkedList list = new LinkedList();

        list.InsertHead(5);

        list.InsertHead(4);

        list.InsertHead(3);

        list.InsertHead(2);

        list.Print();

        list.InsertTail(4);

        list.InsertTail(3);

        list.InsertTail(2);

        list.Print();

        list.DeleteTail();

        list.DeleteTail();

        list.Print();

        list.DeleteHead();

        list.DeleteHead();

        list.Print();

        list.InsertAt(2, 8);

        list.Print();

        list.InsertAt(5, 9);

        list.Print();

        list.DeleteAt(2);

        list.Print();

        list.DeleteAt(5);

        list.Print();

    }

}

​

​

class Node

{

    public int data;

    public Node? next;

​

    public Node(int data)    

    {

        this.data = data;

        this.next = null;

    }

}

​

class LinkedList

{

    int length;

    Node? start;

    public LinkedList()

    {

        length = 0;

        this.start = null;

    }

    public void InsertHead(int data)

    {

        Node newNode = new Node(data);

        if (start == null)

            start = newNode;

        else

        {

            newNode.next = start;

            start = newNode;

        }

        length++;

    }

    public void InsertTail(int data)

    {

        Node newNode = new Node(data);

        if (start == null)

            start = newNode;

        else

        {

            Node? n = this.start;

            while(n.next != null)

            {

                n = n.next;

            }

            n.next = newNode;

        }

        length++;

    }

    public void DeleteHead()

    {

        if (start == null)

            return;

        Node n = this.start;

        start = n.next;        

        length--;

    }

    public void DeleteTail()

    {

        if (start == null)

            return;

        Node n = start;

        while(n.next.next != null)

        {

            n = n.next;

        }

        n.next = null;

        length--;

    }

    public void InsertAt(int index, int data)

    {

        Node newNode = new Node(data);

        if (start == null)

            start = newNode;

        else if(index == 0)

            InsertHead(data);

        else if(index > length)

            InsertTail(data);

        else

        {

            Node? n = this.start;           

            int i = 1;

            while(i < index)

            {

                n = n.next;

                i++;

            }

            newNode.next = n.next;

            n.next = newNode;       

            length++;

        }       

    }

    public void DeleteAt(int index)

    {       

        if (start == null)

            return;

        else if(index == 0)

            DeleteHead();

        else if(index > length)

            DeleteTail();

        else

        {

            Node? n = this.start;           

            int i = 1;

            while(i < index)

            {

                n = n.next;

                i++;

            }

            Node temp = n;          

            n.next = temp.next.next;    

            length--;

        }

    }

    public void Print()

    {

        Console.WriteLine(ToString() + $" length: {length}");

    }

    public override string ToString() 

    {

        Node? n = this.start;

        string strReturn = "";

        while(n != null)

        {

            strReturn += $"{n.data}, ";

            n = n.next;

        }

        return strReturn;

    }

    public string PrintReverse(Node? n)

    {

        if(n != null)

        {

            return PrintReverse(n.next) + $"{n.data}";

        }

        return "";

    }

}