Question: Design a circular deque (double-ended queue) using a doubly linked list. Your deque should support the following operations:

1. Insertion at the front
2. Insertion at the rear
3. Deletion from the front
4. Deletion from the rear
5. Get the front item
6. Get the rear item
7. Check if the deque is empty

You are given the following node structure for the doubly linked list:

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

Implement the CircularDeque class with the above functionality.

Answer:

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

class CircularDeque:
    def __init__(self, k: int):
        self.k = k
        self.size = 0
        self.head = None
        self.tail = None

    def insertFront(self, value: int) -> bool:
        if self.size == self.k:
            return False
        node = Node(value)
        if self.size == 0:
            self.head = node
            self.tail = node
            node.next = node
            node.prev = node
        else:
            node.next = self.head
            node.prev = self.tail
            self.head.prev = node
            self.tail.next = node
            self.head = node
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.size == self.k:
            return False
        node = Node(value)
        if self.size == 0:
            self.head = node
            self.tail = node
            node.next = node
            node.prev = node
        else:
            node.next = self.head
            node.prev = self.tail
            self.head.prev = node
            self.tail.next = node
            self.tail = node
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.size == 0:
            return False
        if self.size == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = self.tail
            self.tail.next = self.head
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.size == 0:
            return False
        if self.size == 1:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = self.head
            self.head.prev = self.tail
        self.size -= 1
        return True
            
    def getFront(self) -> int:
        if self.size == 0:
            return -1
        return self.head.val

    def getRear(self) -> int:
        if self.size == 0:
            return -1
        return self.tail.val

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

Explanation:

1. We first define a Node class to represent the nodes of the doubly linked list. Each node has a value, a reference to the previous node, and a reference to the next node.
2. We then define the CircularDeque class, which has a constructor method to initialize the deque with a given maximum size `k’. The size of the deque is initialized to 0, and the head and tail pointers are set to None.
3. insertFront method inserts a new node at the front of the deque. If the deque is full, it returns False; otherwise, it creates a new node and adjusts the pointers accordingly, incrementing the size and returning True.
4. insertLast method inserts a new node at the rear of the deque. Similar to insertFront, it checks if the deque is full, creates a new node, adjusts the pointers, and increments the size.
5. deleteFront and deleteLast methods delete a node from the front and rear of the deque, respectively. They check if the deque is empty and update the pointers accordingly.
6. getFront and getRear methods return the value of the node at the front and rear of the deque, respectively. If the deque is empty, they return -1.
7. isEmpty method checks if the deque is empty by comparing the size to 0 and returns a boolean value.

The implementation uses a circular structure, where the head node’s previous pointer points to the tail node, and the tail node’s next pointer points to the head node, creating a circular linkage. This allows for constant time insertion and deletion at both ends of the deque.