LeetCode - 641. Design Circular Deque [Python]

https://leetcode.com/problems/design-circular-deque/

Design Circular Deque - LeetCode

---

풀이 과정

원형 덱을 구현하는 문제이다.

 

left, right 포인터를 가진 양방향 링크드 리스트로 구현하였고, head 노드와 tail 노드는 실제로 값을 가진 노드를 가리키는게 아닌 덱의 맨 앞과 맨 뒤를 접근하기 위한 노드로 구현하였다.

 

실제 덱의 맨 앞의 값을 조회하려면 head.right.val로 조회하여야 하고, 맨 뒤의 값을 조회 하려면 tail.left.val로 조회하여야 한다.

---

소스 코드

class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head
        
    def add_node(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new
        
    def del_node(self, node: ListNode):
        n = node.right.right
        node.right, n.left = n, node

    def insertFront(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self.add_node(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.k:
            return False
        self.len += 1
        self.add_node(self.tail.left, ListNode(value))
        return True
        

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self.del_node(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self.del_node(self.tail.left.left)
        return True

    def getFront(self) -> int:
        return self.head.right.val if self.len else -1

    def getRear(self) -> int:
        return self.tail.left.val if self.len else -1

    def isEmpty(self) -> bool:
        return self.len == 0        

    def isFull(self) -> bool:
        return self.len == self.k