Skip to main content

Static vs dynamic implementation of list

Short answer

Static list (array) has fixed size, contiguous memory, O(1) index access, but insertion/deletion requires shifting elements O(n). Dynamic list (linked nodes) allocates memory at runtime, uses pointers, allows O(1) insertion/deletion after position is found, but sequential access O(n).

Differentiate between static and dynamic implementation of list with suitable example.

A list is a linear collection of elements in a sequence. It can be implemented statically (array) or dynamically (linked nodes with pointers).

Static implementation (array)Dynamic implementation (linked list)
Elements stored in contiguous memoryNodes stored anywhere; linked by pointers
Size fixed at compile timeSize changes at run time
Memory is allocated even if unusedMemory allocated only when a node is needed
Insertion/deletion in the middle needs shifting of elements: O(n)Only pointers change once the position is known: O(1)
Random access by index: O(1)Sequential access only: O(n)
No extra memory for linksExtra memory for the pointer in every node
Overflow when array is fullOverflow only when heap is exhausted
Memory freed only at program endMemory returned with free()

Example: list 10, 20, 30

Static:

int list[100] = {10, 20, 30};   // n = 3
// insert 15 at index 1: shift 20, 30 right -> 10 15 20 30

Dynamic:

struct node { int info; struct node *next; };
// head -> [10|*] -> [20|*] -> [30|NULL]
// insert 15 after 10: p->next = q->next; q->next = p;  (no shifting)

Choose arrays when the size is known and fast access is needed; choose linked lists when size varies and insertions/deletions are frequent.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 3 questions →