Skip to main content

Array representation vs dynamic list

Short answer

In array representation, elements are stored in consecutive memory locations with O(1) random access but insertion/deletion requires shifting and costs O(n). A dynamic linked list stores nodes anywhere in memory joined by pointers, allowing O(1) insert/delete after locating position but sequential O(n) access and extra pointer overhead.

Explain array representation of list. How does it differ from dynamic list?

Array representation of a list

In array representation the elements of the list are stored in consecutive memory locations of an array. Element i is at address base + i × size, and the order of elements is given by the physical order. A variable n holds the current number of elements and MAX is the capacity.

index:   0    1    2    3    4 ...  MAX-1
       | 10 | 20 | 30 | 40 |    |  ...  |
         n = 4

Operations: insertion at position k shifts elements k..n−1 one place right; deletion shifts them left; both take O(n). Access a[i] takes O(1).

Difference from a dynamic list (linked list)

Array listDynamic list
Elements in contiguous memoryNodes anywhere in memory, joined by pointers
Fixed maximum sizeGrows and shrinks at run time
Order given by positionOrder given by next links
Random access O(1)Sequential access O(n)
Insert/delete needs shifting: O(n)Insert/delete by changing pointers: O(1) after locating position
No pointer overheadExtra pointer in each node
Memory wasted if array is large and list smallMemory used as needed
Overflow when array is fullOverflow only when no heap memory is left

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 3 questions →