Why does Memory Allocation matter?
Array (陣列)
Requires contiguous (side-by-side) memory blocks. It's like booking adjacent seats in a cinema.
- Access: Fast O(1)
Because memory is continuous, the computer can instantly calculate the exact location of any item using math. - Insert/Delete: Slow O(n)
To insert an item in the middle, you must shift all subsequent elements one space to the right to make room. - Memory Efficiency: High
Only stores the actual data. No extra memory is wasted.
Linked List (鏈結串列)
Uses scattered memory. Nodes are connected via pointers, like a treasure hunt.
- Access: Slow O(n)
You must start from the beginning and follow the pointers one by one to find your target. - Insert/Delete: Fast O(1)
No shifting needed! Just change the pointer of the previous node to point to the new node. - Memory Overhead: Higher
Each node must store the data AND a pointer (the memory address of the next node).
Core Concept: Memory Fragmentation
Why does RAM get fragmented? Operating systems and programs constantly load and unload data of varying sizes. When programs close, they leave small, non-contiguous "holes" of free memory. Over time, these gaps prevent the system from allocating large, continuous blocks for new tasks.
Even if there is enough total free space, an Array might fail to initialize because it cannot find enough continuous space. Linked Lists solve this by fitting into any available gaps!
Interactive Simulation
(Leave blank for random)
System RAM (8x8 Grid)
Free
Occupied