Design Circular Deque - Video Solutions

Problem Overview: Design a double-ended queue (deque) with a fixed capacity that behaves like a circular buffer. You must support operations such as insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull in constant time.

Approach 1: Circular Array (O(1) time, O(k) space)

This approach stores elements in a fixed-size array and treats it as circular using modular arithmetic. Maintain two pointers: front and rear. When inserting at the front, decrement the front index using (front - 1 + capacity) % capacity. When inserting at the rear, increment rear using (rear + 1) % capacity. Deletions move the pointers in the opposite direction. The key insight is that wrap‑around indexing lets the array reuse freed positions instead of shifting elements. A counter or size variable helps detect isFull and isEmpty. All operations run in O(1) time with O(k) space, where k is the deque capacity. This approach leverages simple memory layout and cache-friendly access patterns using an array.

Approach 2: Doubly Linked List (O(1) time, O(k) space)

A linked list implementation models the deque with nodes that store prev and next pointers. Maintain two references: head for the front and tail for the rear. Insertions at either end create a new node and adjust the neighboring pointers. Deletions simply move the head or tail pointer and detach the removed node. Because each node directly connects to both neighbors, operations at both ends remain constant time. Track the current size to enforce the capacity limit and determine isFull or isEmpty. Every operation runs in O(1) time with O(k) space for storing nodes. This approach is more flexible but has slightly higher memory overhead due to pointer storage.

Both implementations follow the core behavior of a deque: efficient insertions and removals from both ends. The difference lies in memory layout and pointer management. Circular arrays rely on index arithmetic, while linked lists rely on pointer adjustments.

Recommended for interviews: The circular array implementation is usually the expected answer. It demonstrates understanding of circular buffers, modular arithmetic, and memory efficiency. The linked list approach still satisfies the requirements and shows solid knowledge of pointer manipulation, but interviewers often prefer the array solution because it avoids extra node allocations and mirrors how real systems implement bounded deques.