Questions to ask

1. Is random indexed access needed?
2. Are insertions mainly at an end or in the middle?
3. Must values remain ordered?
4. Is the maximum size known?
5. Are memory usage and allocation failures important?

Examples

A fixed table of marks suits an array because indexed access is direct. A changing sequence with frequent head insertion can suit a linked list. A reverse-order undo history suggests a stack, while arrival-order work suggests a queue. Relationships between cities suggest a graph.

Trade-offs

Arrays have contiguous storage and efficient indexed access, but a middle insertion can require shifting. Linked nodes can be relinked efficiently when the relevant location is known, but finding that location may require traversal and each node carries link storage.

Time and space

Compare whole workloads, not one isolated best-case operation. An operation that first searches n nodes and then relinks one link still has O(n) total search-and-update work. Include input storage, output storage and auxiliary storage deliberately rather than mixing those categories.

Design process

State the expected workload, choose a simple correct representation, define an interface, then test boundary cases. A more complicated structure can add maintenance cost without helping a small task. The selected structure must also represent the required logical relationships accurately.