// @Title: 设计链表 (Design Linked List)
// @Author: qisiii
// @Date: 2024-09-12 19:54:04
// @Runtime: 9 ms
// @Memory: 44.3 MB
// @comment: 
// @flag: 
class MyLinkedList {
    private int size;
    private Node head;
    private Node tail;
    static class Node{
        private int val;
        private Node next;
        public Node(int val,Node next){
            this.val=val;
            this.next=next;
        }
    }
    public MyLinkedList() {
    
    }
    
    public int get(int index) {
        if(index<0||index==0&&size==0||index>=size){
            return -1;
        }
        Node temp=head;
        while(index>0){
            temp=temp.next;
            index--;
        }
        return temp.val;
    }
    
    public void addAtHead(int val) {
        if(head==null){
            head=new Node(val,null);
            tail=head;
        }else{
            Node newHead=new Node(val,head);
            head=newHead;
        }
        size++;
    }
    
    public void addAtTail(int val) {
        if(tail==null){
            head=new Node(val,null);
            tail=head;
        }else{
            Node temp=new Node(val,null);
            tail.next=temp;
            tail=temp;
        }
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index==0){
            addAtHead(val);
        }else if(index==size){
            addAtTail(val);
        }else if(index>size){
            return;
        }else{
            Node temp=head;
            while(index>1){
                temp=temp.next;
                index--;
            }
            Node newNode=new Node(val,temp.next);
            temp.next=newNode;
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        if(index<0||index>size-1){
            return;
        }else if(index==0&&head==null){
            return;
        }else if(index==0){
            head=head.next;
            if(size==1){
                tail=null;
            }
        }else{
            Node temp=head;
            while(index>1){
                temp=temp.next;
                index--;
            }
            temp.next=temp.next.next;
            if(temp.next==null){
                tail=temp;
            }
        }
        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);
 */