Memory Layout: Stack, Heap, Pointers

To truly master data structures, you must look beneath programming language syntax and understand how hardware RAM is partitioned by the operating system and language runtimes (like the JVM, ART, or native C/Rust runtimes).

The Virtual Memory Layout

When an operating system launches a process, it assigns it a virtual address space typically divided into distinct segments:

Copy codeHigher Memory Addresses
+------------------------------------+
| Stack (Grows Downward ↓)           |
| Local variables, function frames   |
+------------------------------------+
|               ↓                    |
|          Unallocated Gap           |
|               ↑                    |
+------------------------------------+
| Heap (Grows Upward ↑)              |
| Dynamic objects, reference types   |
+------------------------------------+
| BSS & Data Segments                |
| Global & static variables          |
+------------------------------------+
| Text / Code Segment                |
| Compiled machine instructions      |
+------------------------------------+
Lower Memory Addresses

The Stack

The Stack is a strict LIFO (Last-In-First-Out) memory structure managed directly by the CPU.

How Stack Execution Works:

1. Every time a function is called, a stack frame is pushed onto the stack.
2. The stack frame stores:
   • Return address.
   • Function arguments.
   • Primitive local variables.
   • Object reference variables (pointers).
3. When the function returns, its frame is popped in a single CPU instruction (moving the stack pointer register ESP/RSP).

Copy codefun calculateTotal(price: Int, count: Int): Int {
    val tax = 5 // Allocated directly inside calculateTotal stack frame
    return (price * count) + tax
}

Characteristics of Stack Memory:

• Blazing Fast: Allocation and deallocation are O(1) operations simply advancing a CPU pointer.
• Scope-Bound: Memory is automatically reclaimed when the function exits.
• Limited Size: Usually 1MB to 8MB per thread. Exceeding this limit causes a StackOverflowError (common in infinite recursion).

The Heap

The Heap is a large, shared pool of memory used for dynamic allocations where the lifetime of data is not tied to a single function scope.

How Heap Execution Works:

1. When you create an object with new or a class constructor, memory is allocated from the heap.
2. Objects remain in the heap until explicitly freed (in C/C++ via free) or collected by the Garbage Collector (in Kotlin/Java/Go).

Copy codeclass User(val name: String, val age: Int)

fun createUser(): User {
    // The reference 'u' lives on the Stack
    // The actual User object instance lives on the Heap
    val u = User("Alice", 28)
    return u // Object survives after function returns!
}

Copy codeSTACK FRAME:
+---------------------------+
| u (pointer: 0x7FFF0040) --+--------> HEAP MEMORY:
+---------------------------+          +------------------------+
                                       | Address: 0x7FFF0040    |
                                       | Class Header: User     |
                                       | name -> "Alice" (Heap) |
                                       | age  -> 28             |
                                       +------------------------+

Pointers and References

A pointer (or reference in managed runtimes like Java/Kotlin) is simply a variable that holds a physical memory address pointing to another location in memory.

Reference Overhead

On a 64-bit architecture:

• Every reference pointer occupies 8 bytes (or 4 bytes with JVM Compressed Oops).
• An object in the heap has header overhead (typically 12–16 bytes in Android ART/HotSpot for mark word and class pointer).
• Therefore, a linked list node holding an integer has significant memory overhead compared to a primitive integer array!

Copy codePrimitive Int Array (4 ints):
[ 4 bytes ][ 4 bytes ][ 4 bytes ][ 4 bytes ] = 16 bytes total payload

Linked List of 4 boxed Integers:
Node (16B header + 8B value ptr + 8B next ptr) + Integer (16B header + 4B int)
= ~48 bytes per element!

Summary

• Stack: Fast, CPU-register managed, scope-limited, holds primitive locals and reference variables.
• Heap: Flexible, larger memory pool for dynamic object instances, managed via Garbage Collection.
• Pointers/References: Address variables connecting stack frames to heap objects, or linking nodes together in pointer-based data structures.