Choose Between an Array and a Linked List

Problem Statement

In high-performance and quantitative systems, data structure selection requires looking beyond theoretical Big O complexities to hardware-level realities such as CPU cache lines, memory fragmentation, and pointer indirection.

You are asked to evaluate the trade-offs between contiguous array storage and node-based linked lists, and implement a fixed-capacity circular array queue (CircularQueue) that demonstrates why arrays are often preferred over linked lists for high-throughput FIFO message passing.

Required Comparison Dimensions

Your analysis should address:

1. Cache Locality and Prefetching: Spatial/temporal locality, CPU cache line fills (typically 64 bytes), and hardware prefetchers.
2. Memory Overhead and Allocations: Per-node pointer overhead (e.g., 16 bytes for next/prev pointers on 64-bit systems) versus dynamic array over-allocation; heap allocation overhead and memory fragmentation.
3. Reference and Pointer Stability: What happens to memory addresses of existing elements during insertions, deletions, and reallocations.
4. Practical Operations: Trade-offs in random access O(1) vs O(n), arbitrary insertions (array element shifting vs pointer rewiring and pointer chasing), and FIFO queues.

Implementation Task

Implement the CircularQueue class using a fixed-size array/buffer with the following interface:

class CircularQueue:
    def __init__(self, capacity: int):
        """Initialize the queue with a maximum capacity."""
        pass

    def enqueue(self, val: int) -> bool:
        """Insert an element at the back. Return True if successful, False if full."""
        pass

    def dequeue(self) -> int:
        """Remove and return the front element. Return -1 if empty."""
        pass

    def get(self, index: int) -> int:
        """Return the element at 0-based offset from front. Return -1 if invalid."""
        pass

    def is_empty(self) -> bool:
        pass

    def is_full(self) -> bool:
        pass

Constraints

• 1 <= capacity <= 10^5
• 0 <= val <= 10^9
• 0 <= index < capacity
• All operations must run in strict O(1) time with no dynamic heap reallocations after initialization.

Example

q = CircularQueue(3)
q.enqueue(10)  # returns True
q.enqueue(20)  # returns True
q.enqueue(30)  # returns True
q.enqueue(40)  # returns False (queue is full)
q.get(1)       # returns 20
q.dequeue()    # returns 10
q.enqueue(40)  # returns True (wraps around)
q.get(2)       # returns 40

Edge Cases

• Dequeuing or accessing indices from an empty queue.
• Enqueuing to a full queue without overwriting existing data.
• Index out-of-bounds relative to the current logical size (not just buffer capacity).