How does a linked list differ from an array?
A linked list and an array are both data structures for storing a set of elements, but they are fundamentally organized differently. The key difference: an array stores elements sequentially, while a list is connected through a chain of references.
1. Placement in memory
| Characteristic | Array | Linked list |
|---|---|---|
| Storing elements | In contiguous memory cells | In different places in memory, connected by references |
| Structure | [1][2][3][4] | `[1 |
| Next element | Determined by index | Determined by a reference (next) |
2. Accessing elements
| Operation | Array | Linked list |
|---|---|---|
| Access by index | O(1) - instant (address is computed) | O(n) - need to walk from the start to the target element |
| Search by value | O(n) | O(n) |
Conclusion: an array is faster for frequent access to random elements.
3. Insertion and deletion
| Operation | Array | Linked list |
|---|---|---|
| Insertion/deletion in the middle | O(n) - elements need to be shifted | O(1) - it is enough to reassign references |
| Insertion at the end | O(1) or O(n) (depends on the implementation) | O(1), if there is a reference to tail |
Conclusion: a list is better when elements need to be added and removed frequently.
4. Size
| Parameter | Array | Linked list |
|---|---|---|
| Size | Fixed (in classic arrays) | Changes dynamically |
| Memory | Economical | Requires more (to store references) |
5. Practical difference
- An array is convenient when access speed and memory predictability matter.
- A list is convenient when flexibility, dynamic size change, and frequent insertions/deletions matter.
Summary:
An array is a fast structure for storing elements sequentially and accessing them quickly. A linked list is a flexible structure for dynamic data, where insertion and deletion operations matter, but access is slower.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.