class MyLinkedList {

    struct ListNode{

        int val;

        ListNode *prev;

        ListNode *next;

        ListNode(int x):val(x),prev(nullptr),next(nullptr){}

    };

    ListNode *head;

    ListNode *tail;

    int size;

public:

    MyLinkedList() {

        head =nullptr;

        tail =nullptr;

        size=0;

    }

   

    int get(int index) {

        if(index<0 || index>=size){

            return -1;

        }

        ListNode *p =head;

        for(int i=0;i<index;i++){

            p=p->next;

        }

        return p->val;

    }

   

    void addAtHead(int val) {

        ListNode *newNode =new ListNode(val);

        if(size==0){

            head=newNode;

            tail=newNode;

        }else{

            newNode->next=head;

            head->prev =newNode;

            head=newNode;

        }

        size++;

    }

   

   void addAtTail(int val) {

    ListNode *newNode = new ListNode(val);

    if (size == 0) {

        head = newNode;

        tail = newNode;

    } else {

        // 确保 tail 不为 nullptr

        if (tail != nullptr) {

            tail->next = newNode;

            newNode->prev = tail;

            tail = newNode;

        } else {

            // 处理异常情况

            head = newNode;

            tail = newNode;

        }

    }

    size++;

}

   

    void addAtIndex(int index, int val) {

        if(index<0||index>size){

            return ;

        }

        if(index==size){

            addAtTail(val);

            return;

        }

        if(index==0){

            addAtHead(val);

            return;

        }

        ListNode *newNode=new ListNode(val);

        ListNode *p=head;

        for(int i=0;i<index-1;i++){

            p=p->next;

        }

        newNode->next=p->next;

        newNode->prev=p;

        p->next->prev=newNode;

        p->next=newNode;

        size++;

    }

   

    void deleteAtIndex(int index) {

       if(index<0||index>=size){

            return;

       }

       if(index==0){

            ListNode *temp=head;

            head=head->next;

            if(head){

                head->prev=nullptr;

            }else{

                tail=nullptr;

            }

            delete temp;

            size--;

            return;

       }

        else if(index==size-1){

            ListNode *temp=tail;

            tail=tail->prev;

            if(tail){

                tail->next=nullptr;

            }else{

                head=nullptr;

            }

            delete temp;

            size--;

            return ;

        }

        ListNode *p=head;

        for(int i=0;i<index-1;i++){

            p=p->next;

        }

        ListNode *toDelete=p->next;

        p->next=toDelete->next;

        if(toDelete->next){

            toDelete->next->prev=p;

        }else{

            tail=p;

        }

        toDelete->next=nullptr;

        toDelete->prev=nullptr;

        delete toDelete;

        size--;

    }

   

};