#include <iostream>
#include <vector>
#include<algorithm> 
using namespace std;
//struct LinkNode
//{
//    int val;
//    LinkNode *next;
//    LinkNode():val(NULL), next(nullptr) {}
//    LinkNode(int x) :val(x),next(nullptr){}
//    LinkNode(int x , LinkNode *prt) :val(x),next(prt) {}
//};
class MyLinkedList {
public:
    struct LinkNode
    {
        int val;
        LinkNode* next;
        LinkNode() :val(NULL), next(nullptr) {}
        LinkNode(int x) :val(x), next(nullptr) {}
        LinkNode(int x, LinkNode* prt) :val(x), next(prt) {}
    };
    MyLinkedList() {
        Dummy_head = new LinkNode(0);
        size = 0;
    }
    int get(int index) {
        LinkNode* temp = Dummy_head->next;
        if (index > (size - 1) || index < 0) return -1;
        else
        {
            while (index--)
            {
                temp = temp->next;
            }
            return temp->val;
        }
    }
    void addAtHead(int val) {
         LinkNode* temp = new LinkNode(val, Dummy_head->next);
         Dummy_head->next = temp;
         size++;
    }
    void addAtTail(int val) {
        LinkNode* temp = new LinkNode(val,nullptr);
        LinkNode* cur = Dummy_head;
        while (cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = temp;
        size++;
    }
    void addAtIndex(int index, int val) {
        LinkNode* temp = new LinkNode(val);
        LinkNode* cur =  Dummy_head;
        if ( index>size || index < 0) return;
        while (index--)
        {
            cur = cur->next;
        }
        temp->next = cur->next;
        cur->next = temp;
        size++;
    }
    void deleteAtIndex(int index) {
        LinkNode* cur = Dummy_head;
        if (index >= size || index < 0) return;
        while (index--)
        {
            cur = cur->next;
        }
        LinkNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        size--;
    }
    void print_list()
    {
        LinkNode* cur = Dummy_head;
        while (cur->next != nullptr)
        {
            cout << cur->next->val << ' ';
            cur = cur->next;
        }
        cout << endl;
    }   
private:
    LinkNode* Dummy_head;
    int size;
};
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
int main()
{
    MyLinkedList *linkedList = new MyLinkedList;
    for (int i = 1; i < 5; i++)
    {
        linkedList->addAtHead(i);
    }
    for (int i = 1; i < 5; i++)
    {
        linkedList->addAtTail(i);
    }
    linkedList->print_list();
    linkedList->deleteAtIndex(0);
    linkedList->print_list();
   /* cout<<linkedList->get(0);*/
  return 0;
}