Static and Dynamic Structures: When the Size Gets Fixed
Every collection of data a program holds has to reserve memory somewhere, and the question that splits data structures into two families is when that reservation happens.
A static structure fixes its size the moment it is created; a dynamic structure can change size while the program is still running.
Static Data Structures: Space Reserved Up Front
Fixed size: the number of elements is set when the structure is created and cannot change after that.
Contiguous memory: all the elements sit in one unbroken block, one after another.
Because the block is unbroken, the computer reaches any element by arithmetic: start address plus index times element size, which is one step whatever the index.
The venue has 2000 seats, numbered before anyone arrives.
Seat 1147 is found instantly because the numbering is regular.
If 2100 people turn up, the extra 100 cannot be seated, and if 300 turn up, 1700 seats stay empty and unusable for anything else.
Dynamic Data Structures: Space Requested as Needed
Flexible size: elements can be added or removed while the program runs, so the size follows the data.
Memory on demand: the structure asks the operating system for memory as it grows and releases it as it shrinks.
The blocks it receives need not sit next to each other, so a dynamic structure stores extra information to keep track of where its elements are.
Examples: ArrayLists in Java, lists in Python.
Analogy
A dynamic structure is the snack stand at the same concert.
Stock is ordered in as demand appears and cleared away when it drops.
Nothing is wasted on stock nobody wants, but the restocking itself takes time that seat numbering never does.
How a Dynamic Structure Grows
Dynamic arrays such as Python lists and Java ArrayLists keep their elements contiguous, so growing means moving them.
The structure allocates a new, larger block, copies every existing element across, then releases the old block.
The new block is a multiple of the old one rather than one slot bigger, so a resize happens rarely and most additions cost a single step.
Linked structures avoid the copying by giving each element its own node that points to the next one.
Adding an element allocates one node and changes one pointer, so nothing already stored has to move.
The cost lands on reading instead: reaching element 500 means following 500 pointers, because there is no address arithmetic to shortcut with.
Example
A Java ArrayList starts with room for 10 elements.
The first 10 calls to add() drop straight into a free slot and cost one step each.
The 11th call allocates a larger array, copies all 10 elements into it, releases the old one, then stores the new element.
Because the capacity grows by a multiple each time, those copies get rarer as the list gets longer.
Averaged over many additions, the copying works out at roughly one extra step per element added.
What Static and Dynamic Structures Have in Common
Both store an ordered sequence of elements, so element 0 comes before element 1 in either one.
Both let a program reach an element by its index and walk through every element with a loop.
Both hold their contents in RAM only, so the data is lost when the program ends unless it is written to a file.
Both can be passed into a function and returned from one.
When the dynamic structure is a dynamic array, reading an element by index costs the same single step in both.
Common Mistake
Dynamic does not mean free.
Every resize copies data, and every node in a linked structure spends memory on its pointer.
A dynamic structure still fails when the machine runs out of memory, so it is flexible rather than unlimited.
Trade-offs: Speed, Memory and Flexibility
Speed
Static: reading any element takes one calculation, and nothing is ever copied.
Dynamic: reading is just as fast in a dynamic array, but growing it can trigger a copy of everything stored so far.
Memory usage
Static: the whole block is reserved whether or not it is used, so an array of 1000 slots holding 12 values wastes 988 of them.
Dynamic: only the space currently needed is held, but each element carries overhead, either spare capacity in a dynamic array or a pointer in a linked structure.
Flexibility
Static: the size has to be known before the structure exists, and running out means building a bigger one by hand.
Dynamic: the structure adapts to however much data arrives, which matters when the amount is decided by a user or by a file.
Exam technique
Read the command term before deciding what shape the answer takes.
Compare asks for similarities, referring to both structures throughout.
Distinguish asks for differences.
Evaluate asks for strengths weighed against limitations.
Name the scenario from the question in the answer rather than stating the property on its own.
A static array, because the board is always 8 by 8 and never changes size earns the mark; a static array on its own does not.
Choosing a Structure for a Given Scenario
A chess board
Eight rows by eight columns, fixed by the rules of the game, so a static two-dimensional array fits and no resizing code is needed.
An online shopping cart
The number of items depends on what the customer adds and removes, so a dynamic list is the only workable choice.
A sensor logging one temperature reading per second for an hour
Exactly 3600 readings are expected, so a static array of 3600 avoids resizing during the run, which matters on a small embedded device.
Lines read from a text file of unknown length
The count is not known until the file has been read to the end, so a dynamic list is the sensible option.
Active recall
At what point is the size of a static data structure fixed?
Describe the three steps a dynamic array takes when it runs out of space.
State two properties that static and dynamic structures share.
Why does a linked structure make adding an element cheap but reading element 500 expensive?
A program stores the readings from a sensor that logs once a second for exactly one hour. Which type of structure suits it, and why?
