How does an array differ from a list?
An array and a list are both data structures that store collections of elements, but they are built differently internally and designed for different tasks.
1. Storage structure
- An array stores elements in contiguous memory cells. This means each element sits strictly next to the previous one, and all of them are the same type (for example, only numbers).
- A list (linked list) stores elements in separate nodes, each of which holds a value and a reference to the next element. So elements can be located anywhere in memory.
2. Operation performance
| Operation | Array | List |
|---|---|---|
| Access by index | O(1) - direct access | O(n) - must walk through nodes |
| Insert/delete in the middle | O(n) - requires shifting | O(1) if the node is known |
| Search for an element | O(n) | O(n) |
| Memory use | Compact | Larger (due to references) |
3. Data type
- An array stores homogeneous data: all elements of the same type (in languages like C, Java, C++).
- A list can store mixed-type elements and even other lists.
4. Size
- An array usually has a fixed size (you can't just "add" an element without allocating new memory).
- A list can grow and shrink dynamically: only the references change.
5. Visual example
Array:
[10][20][30][40] - elements one after another.
List:
[10 | *] → [20 | *] → [30 | *] → [40 | None] - each element "points" to the next.
6. Example in Python
In Python,
listis a dynamic array, not a classic linked list. But in theoretical terms, a "list" usually means a linked list.
Summary:
An array is faster to access and more memory-efficient. A list is more flexible for insertions and deletions, but slower for direct access.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.