Static and Dynamic List Structure

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Static and Dynamic List Structure

Fixed size vs growing size — a decision that ripples through your whole program's design.

📏 Static vs Dynamic

StaticFixed size decided at creation (like a plain array) — fast access, but wastes space if underused, or fails if you need more than allocated.

DynamicGrows/shrinks as needed (like a linked list, or a dynamically resizing array) — flexible, at the cost of some extra overhead per element.

💡 One-liner: give one real scenario where static structure is preferable, and one where dynamic is preferable — e.g. static for a fixed-size lookup table; dynamic for a to-do list app where item count is unpredictable.

What "dynamic" actually costs

A dynamically resizing array does not grow one element at a time — that would be ruinous. When it fills, it allocates a larger block, typically double, and copies everything across.

A single one of those copies costs O(n), which looks alarming. But because the capacity doubles each time, the copies get rarer as the array grows, and the cost averaged over all insertions works out to O(1) each. This is called amortised constant time, and the word is doing real work: any individual insertion may be slow, while the average stays fast.

💡 Exam distinction: amortised O(1) is not the same as O(1). In a real-time system where one slow operation could miss a deadline, the occasional O(n) copy matters even though the average is fine — which is a legitimate reason to prefer a fixed-size structure.

Choosing between them

⚖️ What actually decides it

Known sizeStatic wins — no resize logic, no wasted capacity, no pointer overhead.

Unpredictable sizeDynamic, or a static structure sized for the worst case if that is knowable and affordable.

Access patternFrequent random access favours contiguous arrays; frequent insertion in the middle favours linked structures.

PredictabilityStatic gives consistent timing. Dynamic gives a good average with occasional spikes.

Syllabus points

Static list structure
Static vs dynamic representation

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.