#include <iostream>

template <typename T>


class LinkedList
{
private:

    int Length;
    T Value;
    LinkedList* NextElement;
    LinkedList* Head;
    LinkedList* Tail;

    /*LinkedList(T* array)
    {
        T* currentElement = new LinkedList(Value = default(T), NextElement = nullptr);;
        for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
        {
            currentElement.Value = array[0];
        }
    }*/
public:

    LinkedList(){}

    LinkedList(T value, LinkedList* nextElement)
    {
        this->Value = value;
        this->NextElement = nextElement;
    }

    bool IsIndexCorrect(int index)
    {
        return index >= 0 && index < Length;
    }

    void AddToTail(T value)
    {
        if (Head == nullptr)
            this->Tail = this->Head = new LinkedList(Value = value, NextElement = nullptr);
        else
        {
            LinkedList* newElement = new LinkedList(Value = value, NextElement = nullptr);
            Tail->NextElement = newElement;
            Tail = newElement;
        }
        Length++;
    }

    void AddByIndex(int index, T value)
    {
        if (IsIndexCorrect(index))
        {

            if (index == Length - 1)
                AddToTail(value);
            else
            {
                LinkedList* current = Head;
                LinkedList* newElement = new LinkedList(Value = value, NextElement = current->NextElement);
                LinkedList* newElementNext;
                if (index == 0)
                {
                    newElementNext = Head->NextElement;
                    Head = newElement;
                    newElement->NextElement = newElementNext;
                }
                else
                {
                    for (int i = 0; i < index; i++)
                        current = current->NextElement;
                    newElementNext = current->NextElement;
                    current->NextElement = newElement;
                    newElement->NextElement = newElementNext;
                }
            }
        }
    }

    void DeleteByIndex(int index)
    {
        if (IsIndexCorrect(index))
        {
            LinkedList* current = Head;
            LinkedList* itemToDelete = nullptr;
            if (index == 0)
            {
                itemToDelete = current;
                Head = current->NextElement;
            }
            else
            {
                for (int i = 0; i < index - 1; i++)
                    current = current->NextElement;
                if (index == Length - 1)
                {
                    itemToDelete = Tail;
                    Tail = current;
                }
                else
                {
                    itemToDelete = current->NextElement;
                    current->NextElement = itemToDelete->NextElement;
                }
            }
            Length--;
            delete itemToDelete;
        }
    }

    bool Contains(T value)
    {
        bool isListContainValue = false;
        LinkedList* current = Head;
        while (current->NextElement != nullptr)
        {
            if (current->Value == value)
            {
                isListContainValue = true;
                break;
            }
            current = current->NextElement;
        }
        return isListContainValue;
    }
};

int main()
{
    LinkedList<int> list;
    list.AddToTail(666);
    list.AddToTail(777);
    list.DeleteByIndex(0);
    bool flag = list.Contains(666);
}