Java O(1) Using Doubly LinkedList Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. As we all know if we use singly LinkedList then pushFront(),pushBack() and popFront() wil
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->As we all know if we use singly LinkedList then pushFront(),pushBack() and popFront() will take O(1) time complexity but popBack(),popMiddle() and pushMiddle() will take linear time complexity.\n\nbut we have another data structure called "Doubly LinkedList" which is similar to singly LinkedList and can solve above mentioned problem because it has an extra pointer "prev" other than "next" so by using it,we can pop and push items in middle or back in constant time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will make three nodes front,back and middle to push and pop items in list and maintain their position while pushing and popping items.\nand we will also create an integer size to keep track of length of list.\n\n# Complexity\n- Time complexity:O(1)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\npublic class FrontMiddleBackQueue {\n    private Node front;\n    private Node back;\n    private Node middle;\n    private int size;\n    //doubly Node having integer value with prev and next pointers\n    private class Node{\n        int val;\n        Node next;\n        Node prev;\n        Node(){};\n        Node(int value){\n            this.val=value;\n            this.next=null;\n            this.prev=null;\n        }\n    }\n    public FrontMiddleBackQueue() {\n    //initially front back and middle node will be null\n        front=null;\n        back=null;\n        middle=null;\n        size=0;\n    }\n\n    public void pushFront(int val) {\n        Node node=new Node(val);\n    //if front node is null then assign front,back and middle node \n    //to newly created node \n        if(front==null){\n            front=node;\n            back=front;\n            middle=front;\n        }\n    //otherwise push before front node and make that node front node\n        else{\n            node.next=front;\n            front.prev=node;\n            front=node;\n        }\n    //rearrange middle node\n        if(size%2==1) middle=middle.prev;\n        size++;\n    }\n\n    public void pushMiddle(int val) {\n        Node node=new Node(val);\n    //if middle node is null then assign front,back and middle node \n    //to newly created node \n        if(middle==null){\n            front=node;\n            back=front;\n            middle=front;\n        }\n    //Otherwise\n        else{\n        //if size of list is even then push after middle node and\n        // make that node middle node\n            if(size%2==0){\n                node.next=middle.next;\n                if(node.next!=null)node.next.prev=node;\n                middle.next=node;\n                node.prev=middle;\n                middle=node;\n            }\n    //otherwise push before middle node and make that node middle node\n            else{\n                if(middle.prev!=null)middle.prev.next=node;\n                node.prev=middle.prev;\n                middle.prev=node;\n                node.next=middle;\n                middle=node;\n            }\n            //important check\n            //if middle node becomes first node of list then make\n            //front node also first node\n            if(middle.prev==null){\n                front=middle;\n            }\n        }\n        size++;\n    }\n\n    public void pushBack(int val) {\n        Node node=new Node(val);\n    //if back node is null then assign front,back and middle node \n    //to newly created node \n        if(back==null){\n            front=node;\n            back=front;\n            middle=front;\n        }\n        //push after back node and make that node back node\n        else{\n            back.next=node;\n            node.prev=back;\n            back=node;\n        }\n        //rearrange middle node\n        if(size>0&&size%2==0) middle=middle.next;\n        size++;\n    }\n\n    public int popFront() {\n        if(front==null){\n            return -1;\n        }\n        int num=front.val;\n        //delete front node and move front node ahead by 1 position\n        front=front.next;\n        if(front!=null) front.prev=null;\n//if front node becomes null then make back and middle node also null\n        else{\n            back=null;\n            middle=null;\n        }\n        //rearrange middle node\n        if(size%2==0&&middle!=null) middle=middle.next;\n        size--;\n        return num;\n    }\n\n    public int popMiddle() {\n        if(middle==null){\n            return -1;\n        }\n        int num=middle.val;\n        //delete middle node\n        if(middle.prev!=null)middle.prev.next=middle.next;\n        if(middle.next!=null)middle.next.prev=middle.prev;\n//if size of list is even then move middle node ahead by 1 position\n        if(size%2==0) middle=middle.next;\n//otherwise move middle node behind by 1 position\n        else middle=middle.prev;\n        if(middle==null){\n            front=null;\n            back=null;\n        }\n    //important check\n    //if size=2 means front and middle node is same so by deleting\n    //middle node,front node will also be deleted so make front=middle\n        if(size==2) front=middle;\n        size--;\n        return num;\n    }\n\n    public int popBack() {\n        if(back==null){\n            return -1;\n        }\n        int num=back.val;\n        //delete back node and move back node behind by 1 position\n        back=back.prev;\n        if(back==null) back.next=null;\n        //if back node is null then make front node and\n        //middle node also null\n        else{\n            front=null;\n            middle=null;\n        }\n        //rearrange middle node\n        if(size%2==1&&middle!=null) middle=middle.prev;\n        size--;\n        return num;\n    }\n}\n\n```
['Doubly-Linked List', 'Java']