Java O(1) DoublyLinkedList
Constraints allow you O(N) solution.\nBut we can do better.\nSo this is O(1) doubly linked list solution with pointers on first, last and middle elements.\n\nTr
Constraints allow you O(N) solution.\nBut we can do better.\nSo this is **O(1)** doubly linked list solution with pointers on first, last and middle elements.\n\nTricky point:\nWhen you add to front or back you have to rebalance mid. But it also depends on what is the size of our dll.\nSince we want to maintain the **frontmost** middle pointer, we reassign middle according to the size % 2.\n```\nclass FrontMiddleBackQueue {\n        ListNode dummyStart;\n        ListNode dummyTail;\n        ListNode mid;\n        int size;\n\n        public FrontMiddleBackQueue() {\n            dummyStart = new ListNode(0);\n            dummyTail = new ListNode(0);\n            dummyStart.next = dummyTail;\n            dummyTail.prev = dummyStart;\n        }\n\n        public void pushFront(int val) {\n            ListNode newStart = new ListNode(val);\n            newStart.next = dummyStart.next;\n            newStart.prev = dummyStart;\n            dummyStart.next.prev = newStart;\n            dummyStart.next = newStart;\n            size++;\n            if (size == 1) {\n                mid = newStart;\n            } else {\n                if (size % 2 == 0) {\n                    mid = mid.prev;\n                }\n            }\n        }\n\n        public void pushMiddle(int val) {\n           if (size == 0) {\n               ListNode newMid = new ListNode(val);\n               newMid.prev = dummyStart;\n               newMid.next = dummyTail;\n               dummyStart.next = newMid;\n               dummyTail.prev = newMid;\n               mid = newMid;\n               size++;\n               return;\n           }\n            if (size % 2 == 0) {\n                pushNext(val);\n            } else {\n                pushPrev(val);\n            }\n            size++;\n        }\n\n        private void pushPrev(int val) {\n            ListNode newMid = new ListNode(val);\n            newMid.next = mid;\n            newMid.prev = mid.prev;\n            newMid.prev.next = newMid;\n            mid.prev = newMid;\n            mid = newMid;\n        }\n\n        private void pushNext(int val) {\n            ListNode newMid = new ListNode(val);\n            newMid.next = mid.next;\n            newMid.prev = mid;\n            mid.next.prev = newMid;\n            mid.next = newMid;\n            mid = newMid;\n        }\n\n        public void pushBack(int val) {\n            ListNode newEnd = new ListNode(val);\n            newEnd.prev = dummyTail.prev;\n            newEnd.next = dummyTail;\n            dummyTail.prev.next = newEnd;\n            dummyTail.prev = newEnd;\n            size++;\n            if (size == 1) {\n                mid = newEnd;\n            } else {\n                if (size % 2 != 0) {\n                    mid = mid.next;\n                }\n            }\n        }\n\n        public int popFront() {\n            if (size > 0) {\n                ListNode next = dummyStart.next;\n                removeNode(next);\n                size--;\n                if (size % 2 != 0) {\n                    mid = mid.next;\n                }\n                return next.val;\n            }\n            return -1;\n        }\n\n        private void removeNode(ListNode node) {\n            node.next.prev = node.prev;\n            node.prev.next = node.next;\n        }\n\n        public int popMiddle() {\n            if (size > 0) {\n                int val = mid.val;\n                mid.next.prev = mid.prev;\n                mid.prev.next = mid.next;\n                if (size % 2 == 0) {\n                    mid = mid.next;\n                } else {\n                    mid = mid.prev;\n                }\n                size--;\n                return val;\n            }\n            return -1;\n        }\n\n        public int popBack() {\n            if (size > 0) {\n                ListNode prev = dummyTail.prev;\n                removeNode(prev);\n                size--;\n                if (size % 2 == 0) {\n                    mid = mid.prev;\n                }\n                return prev.val;\n            }\n            return -1;\n        }\n\n        static class ListNode {\n            int val;\n            ListNode prev;\n            ListNode next;\n\n            public ListNode(int val) {\n                this.val = val;\n            }\n\n        }\n}\n```\n
[]