Array vs. Linked List: Differences and When to Use Each

In a technical screening round, the interviewer asks: **What are the differences between an array and a linked list? When would you choose one over the other?** Walk through the differences in memory layout, the cost of the core operations (indexed access, search, insertion, deletion), and memory overhead — then give concrete situations where each data structure is the better choice. Treat this as a short screening question: the interviewer wants a structured, complete answer delivered in a few minutes, not an essay. ```hint How to structure the comparison Don't list facts in random order. Organize the answer along fixed dimensions — memory layout, random access, insertion/deletion, memory overhead, and cache behavior — and close with one concrete use case for each structure. Screening questions on fundamentals are graded on structure and completeness as much as on correctness. ``` ```hint A nuance that separates strong answers The claim "linked lists have $O(1)$ insertion" is only true **if you already hold a reference to the node** at the insertion point. If you must first search for the position, the total cost is $O(n)$. Calling this out explicitly is a strong signal. ``` ### Constraints & Assumptions - Assume a general-purpose language; "array" covers both fixed-size arrays and dynamic arrays (e.g., C++ `std::vector`, Java `ArrayList`, Python `list`) — call out where the two differ. - "Linked list" means a singly linked list by default; mention where a doubly linked list or a tail pointer changes the answer. - Give costs in Big-O, but also address real-world performance (cache locality, allocation cost), not just asymptotics. - Aim for a 3–5 minute spoken answer, as appropriate for a 15-minute screening call. ### Clarifying Questions to Ask - Should I compare against a fixed-size array, a dynamic array, or both? - Is the linked list singly or doubly linked, and does it maintain a tail pointer? - Do you want asymptotic complexity only, or also practical performance characteristics like cache behavior? - Would you like concrete examples of systems or problems where each structure is the right choice? ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - How does a dynamic array achieve amortized $O(1)$ append, and what is the worst-case cost of a single append? - Linked lists advertise $O(1)$ insertion — why is that claim misleading in most real workloads? - Name a real data structure or system where a linked list is genuinely the right choice, and explain why. - How does your comparison change on modern hardware, where a cache miss is orders of magnitude more expensive than a cache hit?