Past exam question: 2076 Baisakh (Back), Q4
Open in the Padhaiko appQuestion
Explain array representation of list ? How is it different from dynamic list?
Solution
Array Representation of List: In an array-based list, elements are stored in contiguous slots of a fixed-capacity array items[MAX] alongside an integer size tracking the active count:
- Access:
items[i]runs in using direct index calculation. - Insertion at index : Requires shifting
items[i..size-1]one position right (). - Deletion at index : Requires shifting
items[i+1..size-1]one position left ().
Differences from Dynamic List (Linked List):
| Feature | Array List (Static) | Dynamic List (Linked List) |
|---|---|---|
| Memory Allocation | Fixed compile-time contiguous block | Runtime heap allocation per node (malloc/free) |
| Size Growth | Bounded by MAX (can overflow) | Grows/shrinks dynamically until heap RAM ends |
| Random Access | via index | sequential traversal from head |
| Insert / Delete (Middle/Head) | data shifting | pointer rewiring (once position is reached) |
| Memory Overhead | No pointer overhead (but unused slots waste space) | Extra pointer field per node (no unused capacity waste) |
Answer:
An array list stores items in contiguous items[MAX] slots with random indexing and insertion/deletion shifting, whereas a dynamic (linked) list allocates scattered nodes at runtime with flexible size and pointer-based splicing at the cost of sequential access and pointer storage.