One of the first architectural decisions when modeling data is choosing between static and dynamic allocation. This choice dictates how memory is reserved, whether size can change at runtime, and how efficiently the CPU can process items.
What is a Static Data Structure?
A static data structure has a fixed size determined at allocation time (either compile time or during runtime initialization). Once allocated, its memory capacity cannot expand or shrink.
// Fixed array of size 5 allocated in memory
val scores = IntArray(5)
Memory Characteristics of Static Structures
- Allocated as a single, contiguous block of bytes.
- Size must be known beforehand.
- No dynamic memory reallocation overhead during operations.
- Risk of buffer overflow (if data exceeds capacity) or wasted RAM (if oversized).
Static Array in Memory:
[ Index 0 ][ Index 1 ][ Index 2 ][ Index 3 ][ Index 4 ]
0x1000 0x1004 0x1008 0x100C 0x1010
What is a Dynamic Data Structure?
A dynamic data structure can expand and contract at runtime as elements are inserted or removed. It does not require a fixed upfront capacity.
Examples include:
- Node-based collections: Linked Lists, Trees, Graphs.
- Resizing array wrappers: Kotlin
ArrayList, JavaVector, C++std::vector.
// Dynamically sized list that allocates as needed
val dynamicList = ArrayList<String>()
dynamicList.add("User 1")
dynamicList.add("User 2")
Memory Characteristics of Dynamic Structures
- Linked nodes: Stored in non-contiguous heap memory, chained via pointers/references.
- Dynamic arrays: Underlying contiguous array is reallocated with a growth factor (e.g., 1.5x or 2x) when full.
Comprehensive Comparison Matrix
| Property | Static Data Structures (e.g. Fixed Array) | Dynamic Data Structures (e.g. LinkedList, ArrayList) |
|---|---|---|
| Size | Fixed at allocation time | Flexible; grows and shrinks at runtime |
| Memory Allocation | Typically Stack or single continuous Heap block | Heap memory allocated per node or dynamically resized |
| Access Time | O(1) constant time random access | O(1) for dynamic arrays, O(n) for linked lists |
| Insertion / Deletion | Inefficient (O(n) shift) or impossible | Efficient (O(1) at head/tail for linked nodes) |
| Memory Overhead | Zero pointer overhead; minimal metadata | High: 4-8 bytes per pointer + object headers |
| Cache Locality | Excellent (consecutive cache lines) | Poor in linked structures (pointer hopping) |
When to Choose Which?
Use Static Data Structures when:
- The maximum number of elements is strictly known in advance (e.g., days of week, 12 months, fixed size lookup tables).
- Memory constraints are critical (e.g., embedded systems, high-frequency audio DSP buffers, gaming engines).
- Maximum throughput and CPU cache hits are required.
Use Dynamic Data Structures when:
- The volume of data is unpredictable (e.g., user search queries, incoming network packets).
- Frequent insertions and deletions occur throughout the lifecycle of the collection.
- You want convenient high-level APIs without manually managing buffer growth.
Summary
- Static structures have fixed bounds, superior cache locality, and zero reference overhead, but lack flexibility.
- Dynamic structures adapt to fluctuating workloads at the expense of pointer memory overhead or reallocation penalties.