JAVA | Implementation based ✅
---\n# Please Upvote \uD83D\uDE07\n---\n\n\nThis solution is purely implementation based.\n\nWe have a doubly linkedlist which will be pushed elements into from
---\n# Please Upvote \uD83D\uDE07\n---\n\n\nThis solution is purely implementation based.\n\nWe have a doubly linkedlist which will be pushed elements into from front and back (**[641. Design Circular Deque](https://leetcode.com/problems/design-circular-deque/description/)**).\n\nWe will keep an extra node `mid` to keep track of our mid position during push and pop operations, because we will need to push and pop elements at the middle as well.\n\nAn extra global variable `size` will let us know if the size is even or odd which will help us move the `mid` accordingly.\n\n---\n``` java []\nclass FrontMiddleBackQueue {\n    private int size;\n    private Node head, tail, mid;\n\n    public FrontMiddleBackQueue() {\n        size = 0;\n        head = tail = new Node(-1);\n        head.next = tail;\n        tail.prev = head;\n        mid = head;     // default mid position\n    }\n    \n    public void pushFront(int val) {\n        Node newNode = new Node(val);\n        add(head, newNode); // new node is added right to head\n        size++;\n\n        if (size == 1) {    // if its the first ever node\n            mid = head.next;    // make it the mid\n        }\n        if (size % 2 == 0) {    // mid is the former of the two mids\n            mid = mid.prev;\n        }\n    }\n    \n    public void pushMiddle(int val) {\n        Node newNode = new Node(val);\n        // if size is even, new mid will be at perfect centre\n        // that is, right next to mid\n        if (size % 2 == 0) {\n            add(mid, newNode);  // goes right next to mid\n            mid = mid.next;\n        } \n        // else new mid will go to the left of current mid \n        // i.e. the right next position of mid\'s current prev\n        else {\n            add(mid.prev, newNode); // go next to mid\'s prev\n            mid = mid.prev;\n        }\n        size++;\n    }\n    \n    public void pushBack(int val) {\n        Node newNode = new Node(val);\n        // gets added right before tail \n        // i.e. right next to tail\'s current prev\n        add(tail.prev, newNode);    \n        size++;\n        // if size becomes odd, mid will move to perfect centre\n        if (size % 2 == 1) {\n            mid = mid.next;\n        }\n    }\n    \n    public int popFront() {\n        if (size == 0) {\n            return -1;\n        }\n        if (size == 1) {  // if list wil become empty\n            mid = head;   // default mid is head\n        } else if (size % 2 == 0) {\n            // list will become odd, mid will move to next node\n            mid = mid.next; \n        }\n\n        int val = head.next.value;\n        delete(head.next);  // delete the node next to head\n        size--;\n        return val;\n    }\n    \n    public int popMiddle() {\n        if (size == 0) {\n            return -1;\n        }\n        \n        Node node = mid;\n        if (size == 1) {  // list wil become empty\n            mid = head;   // default mid is head\n        } else {\n            // if list will become odd, mid will go to next node\n            // if list will become even, mid will go to prev node\n            mid = (size % 2 == 0)? mid.next : mid.prev;\n        }\n\n        delete(node);   // delete the node (old mid)\n        size--;\n        return node.value;\n    }\n    \n    public int popBack() {\n        if (size == 0) {  \n            return -1;\n        }\n        if (size == 1) {  // list wil become empty\n            mid = head;   // default mid is head\n        } else if (size % 2 == 1) { // if list will become even\n            mid = mid.prev;         // mid will move to prev node\n        }\n\n        int val = tail.prev.value;\n        delete(tail.prev);  // delete the preceding node of tail\n        size--;\n        return val;\n    }\n\n    // Adds a node `newNode` right next to a reference node `ref`\n    private void add(Node ref, Node newNode) {\n        newNode.next = ref.next;\n        ref.next = newNode;\n        newNode.next.prev = newNode;\n        newNode.prev = ref;\n    }\n\n    // Deletes the passed in node \'node\'\n    private void delete(Node node) {\n        node.next.prev = node.prev;\n        node.prev.next = node.next;\n    }\n    \n    // Node class\n    private class Node {\n        int value;\n        Node next, prev;\n        private Node(int value) {\n            this.value = value;\n        }\n    }\n}\n```\n---\n![image.png](https://assets.leetcode.com/users/images/36e7b34d-af60-4777-aba5-a466a96a0ed9_1675419915.3056364.png)\n\n### Time complexity: $$O(n)$$\n> Let $$n$$ be the number of calls made to `pushFront`, `pushMiddle`, `pushBack`, `popFront`, `popMiddle`, and `popBack`. Each of them have a runtime of $$O(1)$$. So total time complexity becomes $$O(n)$$.\n### Space complexty: $$O(n)$$\n> We are maintaning a doubly linked-list which can be of size $$n$$ at max.
['Design', 'Doubly-Linked List', 'Java']