[Python3] O(1) doubly-linked list with pointer to middle element
Verbose, but efficient solution for the problem.\n\nGood idea for this implementation is to put insert very first node and remove very last node operations into
Verbose, but efficient solution for the problem.\n\nGood idea for this implementation is to put insert very first node and remove very last node operations into a separate methods, so you do less checks for None of prev and next properties.\n\n```\nclass ListNode:\n     def __init__(self, val=0, prev=None, next=None):\n         self.val = val\n         self.prev = prev\n         self.next = next\n\nclass FrontMiddleBackQueue:\n    def __init__(self):\n        self.start, self.middle, self.end = None, None, None\n        self.count = 0            \n\n    def pushBack(self, val: int) -> None:\n        if not self.count:\n            self.addFirstNode_(val)\n            return\n            \n        new_node = ListNode(val, self.end, None)\n        self.end.next = new_node            \n        self.end = new_node\n        if self.count % 2 == 0:            \n            self.middle = self.middle.next\n        self.count += 1        \n\n    def pushMiddle(self, val: int) -> None:\n        if not self.count:\n            self.addFirstNode_(val)\n            return\n        \n        if self.count % 2 == 1:\n            new_node = ListNode(val, self.middle.prev, self.middle)\n            if self.middle.prev:\n                self.middle.prev.next = new_node\n            self.middle.prev = new_node\n            if self.count == 1:\n                self.start = new_node\n            self.count += 1\n            self.middle = new_node\n        else:\n            new_node = ListNode(val, self.middle, self.middle.next)\n            if self.middle.next:\n                self.middle.next.prev = new_node\n            self.middle.next = new_node\n            self.count += 1\n            self.middle = new_node\n\n    def pushFront(self, val: int) -> None:\n        if not self.count:\n            self.addFirstNode_(val)\n            return\n        \n        new_node = ListNode(val, None, self.start)        \n        self.start.prev = new_node        \n        self.start = new_node\n        \n        if self.count % 2 == 1:            \n            self.middle = self.middle.prev\n            \n        self.count += 1                 \n\n    def popBack(self) -> int:\n        if not self.count:\n            return -1\n        elif self.count == 1: \n            return self.removeLastNode_()\n        \n        node = self.end        \n        self.end = self.end.prev        \n        self.end.next = None\n        \n        if self.count % 2 == 1:\n            self.middle = self.middle.prev        \n            \n        self.count-=1                \n        \n        return node.val\n\n    def popMiddle(self) -> int:\n        if not self.count:\n            return -1\n        elif self.count == 1: \n            return self.removeLastNode_()\n        \n        node = self.middle\n        if self.middle.prev:\n            self.middle.prev.next = self.middle.next        \n        \n        self.middle.next.prev = self.middle.prev\n        if self.start == self.middle:\n            self.start = self.start.next        \n            \n        if self.count % 2 == 0:\n            self.middle = self.middle.next\n        else:\n            self.middle = self.middle.prev\n            \n        self.count-=1        \n            \n        return node.val        \n\n    def popFront(self) -> int:\n        if not self.count:\n            return -1\n        elif self.count == 1: \n            return self.removeLastNode_()\n        \n        node = self.start\n        self.start = self.start.next\n        self.start.prev = None\n        \n        if self.count % 2 == 0:\n            self.middle = self.middle.next        \n            \n        self.count-=1        \n        \n        return node.val\n    \n    def addFirstNode_(self, val) -> None:\n        new_node = ListNode(val, None, None)\n        self.count = 1\n        self.start, self.middle, self.end = new_node, new_node, new_node     \n        \n    def removeLastNode_(self) -> None:\n        node = self.start\n        self.count = 0\n        self.start, self.middle, self.end = None, None, None\n        return node.val\n```
['Linked List', 'Doubly-Linked List', 'Python3']