Java || Two Doubly Linked Lists
\n/**\n * We shall implement two lists i.e. front half and rear half or back half\n * whose sizes are denoted by fSize and bSize respectively\n * \n * We\'ll ma
```\n/**\n * We shall implement two lists i.e. front half and rear half or back half\n * whose sizes are denoted by fSize and bSize respectively\n * \n * We\'ll make sure that after each push or pop operation\n * \t\tEither fSize == bSize\n * \t\tOr fSize == bSize-1\n * By maintaining this, we can make the pushMiddle and popMiddle efficient\n * For fSize == bSize, pushMiddle will push it in the back half and popMiddle will pop from the front half\n * For fSize == bSize-1, pushMiddle will push it in the front half and popMiddle will pop from the back half\n * To maintain this, we shall always push the first element in the back half irrespective of its requirement\n * So if bSize is 0, we are pushing the first element\n * if fSize is 0, we are pushing the second element\n * \n * front and back denote the two ends of our queue\n * frontEnd and backEnd denote the joining point i.e. if we have to make a single list, we have to join these two points\n * \n * e.g->\n * 5 6 8 9 2 3 4\n * Here 5 is front, 8 is frontEnd, 9 is backEnd and 4 is back\n * \n * 5 6 8 9 2 3 4 6\n * Here 5 is front, 9 is frontEnd, 2 is backEnd and 6 is back\n * */\nclass Node\n{\n    Node front;\n    int val;\n    Node back;\n    Node(int v)\n    {\n        val = v;\n    }\n}\nclass FrontMiddleBackQueue {\n    Node front, frontEnd, back, backEnd;\n    int fSize, bSize;\n    public FrontMiddleBackQueue() {\n        front = frontEnd = back = backEnd = null;\n        fSize = bSize = 0;\n    }\n    \n    public void pushFront(int val) {\n        if (bSize == 0) //if first element, push in back half\n        {\n            back = new Node(val);\n            backEnd = back;\n            ++bSize;\n        }\n        else if (fSize == 0) //if second element, push in front half\n        {\n            front = new Node(val);\n            frontEnd = front;\n            ++fSize;\n        }\n        else //in all other cases, push in front\n        {\n            Node newNode = new Node(val);\n            front.front = newNode;\n            newNode.back = front;\n            front = newNode;\n            ++fSize;\n            if (fSize > bSize) //if fSize exceeds bSize, move one node from the front half to the back half\n                moveFrontEndToBackEnd();\n        }\n    }\n    \n    public void pushMiddle(int val) {\n        if (bSize == 0) //if first element, push in back half\n        {\n            back = new Node(val);\n            backEnd = back;\n            ++bSize;\n        }\n        else //otherwise\n        {\n            Node newNode = new Node(val);\n            if (fSize == bSize) //if sizes are same, push in back half\n            {\n                newNode.back = backEnd;\n                backEnd.front = newNode;\n                backEnd = newNode;\n                ++bSize;\n            }\n            else //otherwise (fSize is guaranteed to be smaller) push in front half\n            {\n                if (fSize == 0)\n                {\n                    front = frontEnd = newNode;\n                }\n                else\n                {\n                    newNode.front = frontEnd;\n                    frontEnd.back = newNode;\n                    frontEnd = frontEnd.back;\n                }\n                ++fSize;\n            }\n        }\n    }\n    \n    public void pushBack(int val) {\n        if (bSize == 0)\n        {\n            back = new Node(val);\n            backEnd = back;\n            ++bSize;\n        }\n        else\n        {\n            Node newNode = new Node(val);\n            back.back = newNode;\n            newNode.front = back;\n            back = newNode;\n            ++bSize;\n            if (bSize == fSize+2) //if the gap exceeds 1, move one node from back half to front half\n                moveBackEndToFrontEnd();\n        }\n    }\n    \n    public int popFront() {\n        int val = 0;\n        if (bSize == 0) //if no elements\n        {\n            val = -1;\n        }\n        else if (fSize == 0) //if only one element is remaining (guaranteed to be in the back half)\n        {\n            val = back.val;\n            back = backEnd = null;\n            bSize = 0;\n        }\n        else //in all other cases, remove from front\n        {\n            val = front.val;\n            front = front.back;\n            if (front == null) frontEnd = null;\n            else front.front = null;\n            --fSize;\n            if (bSize == fSize+2) //if the difference exceeds 1, move one node from back half to front half\n                moveBackEndToFrontEnd();\n        }\n        return val;\n    }\n    \n    public int popMiddle() {\n        int val = 0;\n        if (bSize == 0) //if no elements\n        {\n            val = -1;\n        }\n        else if (fSize == 0) //if only one element is remaining (guaranteed to be in the back half)\n        {\n            val = back.val;\n            back = backEnd = null;\n            bSize = 0;\n        }\n        else //in all other cases\n        {\n            val = 0;\n            if (fSize == bSize) //if sizes are same, pop from front half\n            {\n                val = frontEnd.val;\n                frontEnd = frontEnd.front;\n                if (frontEnd == null) front = null;\n                else frontEnd.back = null;\n                --fSize;\n            }\n            else //otherwise (fSize is guaranteed to be smaller) pop from back half\n            {\n                val = backEnd.val;\n                backEnd = backEnd.back;\n                if (backEnd == null) back = null;\n                else backEnd.front = null;\n                --bSize;\n            }\n        }\n        return val;\n    }\n    \n    public int popBack() {\n        int val = 0;\n        if (fSize == 0 && bSize == 0) //if no elements\n        {\n            val = -1;\n        }\n        else if (fSize == 0) //if only one element is remaining\n        {\n            val = back.val;\n            back = backEnd = null;\n            bSize = 0;\n        }\n        else //in all other cases, remove from back\n        {\n            val = back.val;\n            back = back.front;\n            if (back == null) backEnd = null;\n            else back.back = null;\n            --bSize;\n            if (bSize < fSize) //if bSize decreases\n                moveFrontEndToBackEnd(); //move one node from front half to back half\n        }\n        return val;\n    }\n    \n    private void moveBackEndToFrontEnd()\n    {\n        if (fSize == 0) //if front half has no elements (back half is guaranteed to have only one element)\n        {\n            front = frontEnd = backEnd;\n            backEnd = backEnd.back;\n        }\n        else //otherwise\n        {\n            frontEnd.back = backEnd;\n            backEnd = backEnd.back;\n            frontEnd.back.front = frontEnd;\n            frontEnd = frontEnd.back;\n        }\n        frontEnd.back = backEnd.front = null;\n        ++fSize;\n        --bSize;\n    }\n    \n    private void moveFrontEndToBackEnd()\n    {\n        if (bSize == 0) //if back half has no elements (front half is guaranteed to have 2 elements)\n        {\n            back = backEnd = front;\n            front = frontEnd = null;\n            backEnd.front = backEnd.back = null;\n        }\n        else //otherwise\n        {\n            backEnd.front = frontEnd;\n            frontEnd = frontEnd.front;\n            backEnd.front.back = backEnd;\n            backEnd = backEnd.front;\n            backEnd.front = frontEnd.back = null;\n        }\n        --fSize;\n        ++bSize;\n    }\n}\n\n/**\n * Your FrontMiddleBackQueue object will be instantiated and called as such:\n * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();\n * obj.pushFront(val);\n * obj.pushMiddle(val);\n * obj.pushBack(val);\n * int param_4 = obj.popFront();\n * int param_5 = obj.popMiddle();\n * int param_6 = obj.popBack();\n \n```
['Doubly-Linked List']