Which is a primary advantage of a linked-list-based queue over an array-based queue?

• A. Enqueues and dequeues can be performed in constant time without resizing.
• B. Elements are stored contiguously in memory.
• C. Memory usage per element is always lower than array-based.
• D. Access by index is faster.

Answer: (A)

The main advantage is that a linked-list queue allows enqueues and dequeues in constant time without needing to resize the storage. In a linked-list implementation, each element is a node with a value and a pointer to the next node. You keep pointers to the front and the back of the queue. Enqueueing adds a new node at the tail and simply updates the tail pointer; dequeuing removes the node at the head and moves the head pointer forward. These adjustments are O(1) because they involve only pointer updates, regardless of how many elements are in the queue. No shifting of many elements or allocating a bigger underlying block is required as the queue grows.

In contrast, an array-based queue relies on a fixed block of memory. If you run out of space, you must resize the array (allocate a larger array and copy elements) or implement a more complex wraparound scheme that can still require resizing or shifting in some scenarios. That resizing incurs an O(n) cost at the moment it happens, which breaks the guarantee of constant-time updates.

So the linked-list approach provides consistent, constant-time updates without resizing, making it the strongest advantage in this comparison. Access by index and memory contiguity aren’t improved in a linked list, which is why those aspects aren’t the selling points here.