[Leetcode]641. Design Circular Deque

Design Circular Deque - LeetCode

Design Circular Deque - LeetCode

이중 연결리스트를 이용해 원형 데크를 구현하는 문제였다.

파이썬을 이용해 이중 연결리스트를 짜보는 건 처음이었는데 left,right를 따로 초기화 해주지않아도 되어서 다른 언어에 비해 간단한 면이 있었던 것 같다.

 

코드

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

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(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new

    def _del(self, node: ListNode):
        n = node.right.right
        node.right = n
        n.left = node

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

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

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

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self._del(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