Design Circular Deque

해당 문제는 leetcode 641번 Design Circular Deque이며,
해당 내용은 '파이썬 알고리즘 인터뷰'의 풀이를 참고하여 정리하였다.

원형 데크를 구현하기 위해 이중 연결 리스트를 사용한다.

이중 연결 리스트는 노드와 노드가 서로 연결되어 있는 리스트로, 각 노드는 자신의 왼쪽, 오른쪽 노드를 연결하는 링크 필드 두 개와 데이터 필드 한 개로 구성되어 있다.

class MyCircularDeque:

    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.maxlen, self.len = k, 0
        self.head.right = self.tail
        self.tail.left = self.head

init 함수에서는 왼쪽 링크 필드와 오른쪽 링크 필드를 각각 head, tail로 정의한다. 최대 길이 정보와 노드의 실제 길이는 maxlen과 len으로 설정한다. 이중 연결 리스트이므로 head의 right 부분을 tail과 연결하고, tail의 left 부분을 head와 연결한다.

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

_add 함수는 now의 오른쪽에 new를 추가한다. 이때 기존에 있었던 노드 간 연결을 찢고 그 사이로 새 노드가 삽입된다.
_del 함수는 현재 노드의 오른쪽 노드를 삭제한다.

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

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

데크의 처음 혹은 마지막에 노드를 추가하는 insert 함수이다. 원형 데크가 full일 때는 false를 리턴한다. insertLast 함수를 작성할 때 주의할 점은 _add 함수 사용 시 self.tail이 아니라 self.tail.left를 현재 노드로 지정하여 삽입해야 한다. tail을 현재 노드로 지정할 경우 right 노드가 없으므로 runtime error가 발생한다.

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

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

데크의 처음 혹은 마지막에 노드를 삭제하는 delete 함수이다. 원형 데크가 empty일 때는 삭제할 노드가 없으므로 false를 리턴한다. deleteLast 함수를 작성할 때 _del 함수 사용 시 self.tail.left가 아니라 self.tail.left.left를 현재 노드로 지정해야 하는데, 데이터가 있는 마지막 노드인 self.tail.left를 삭제하기 위해서다.

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.maxlen == self.len

이 코드를 작성할 때 가장 중요한 점은 head와 tail은 데이터를 갖지 않는 노드이며, 데이터가 있는 첫 노드는 head.right이고, 데이터가 있는 마지막 노드는 tail.left라는 점이다.