일관적인 로직을 위해서 아무 값도 없는 head, tail Node를 사용하여 구현.

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None)  # 더미
        self.tail = Node(None)  # 더미
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _get(self, idx):
        # pop()/append() 최적화. 가까운 쪽에서 접근.
        if idx <= self.size // 2:
            cur = self.head.next
            for _ in range(idx):
                cur = cur.next
        else:
            # idx == size면 tail 자체 반환 (insert_at 맨 끝 삽입용)
            cur = self.tail
            for _ in range(self.size - idx):
                cur = cur.prev
        return cur

    def insert_at(self, idx, val):
        # idx 범위: 0 ~ size (size 허용 = 맨 끝 삽입. list.insert 표준 관례)
        ref = self._get(idx)
        new = Node(val)
        prev = ref.prev
        prev.next = new
        new.prev = prev
        new.next = ref
        ref.prev = new
        self.size += 1

    def delete_at(self, idx):
        # idx 범위: 0 ~ size-1 (존재하는 노드만 삭제 가능)
        cur = self._get(idx)
        cur.prev.next = cur.next
        cur.next.prev = cur.prev
        cur.prev = None
        cur.next = None
        self.size -= 1

    def __len__(self):
        return self.size

    # ──────────────────────────────────
    # 위 4개 조합으로 파생 가능
    # ──────────────────────────────────
    # append(val)      → insert_at(size, val)
    # appendleft(val)  → insert_at(0, val)
    # pop()            → delete_at(size - 1)   ← _get 최적화로 O(1)
    # popleft()        → delete_at(0)           ← O(1)
    # get(idx)         → _get(idx).val