What are the trade-offs between using a linked list and an array?

• A. Linked lists have dynamic resizing and O(1) inserts at ends but have noncontiguous memory; arrays provide fast random access and memory locality but fixed size.
• B. Linked lists have constant-time random access; arrays do not.
• C. Arrays are dynamically resizable with O(1) inserts; linked lists have fast random access.
• D. Linked lists use contiguous memory; arrays do not.

Answer: (A)

Think about how memory layout affects typical operations. A linked list grows by allocating separate nodes for each element, so you can keep adding elements without moving existing ones. Inserting at the front (and, with a tail pointer, at the end) can be done in constant time. The trade-off is that the elements are scattered in memory, so finding the i-th element or traversing to a particular position isn’t constant time.

An array stores elements contiguously, which means you can access any position directly in constant time. This also improves cache performance, since nearby elements are loaded together. The downside is you usually have to allocate enough space upfront or resize as you grow, which can be costly because it may involve copying many elements to a new block.

So the best description is that linked lists offer dynamic growth and O(1) inserts at ends but noncontiguous memory, while arrays give fast random access and good memory locality but fixed size (in their static form). The other statements mix up these properties—linked lists don’t provide constant-time random access, and arrays aren’t inherently fixed in all contexts, while linked lists do not use contiguous memory.