Nodes, Links, and Memory References

Unlike arrays, which demand contiguous memory blocks, a Linked List stores elements in separate, independently allocated memory blocks called nodes. Each node contains both the payload data and a pointer (or reference) to the next node in the chain.

Anatomy of a Node

In memory, a singly linked list node has two distinct fields:

1. Data Field: The value or object reference being stored.
2. Next Pointer / Link: A reference holding the physical memory address of the next node.

Copy code+-------------------+
|     Node in RAM   |
| +---------------+ |
| | Data: 42      | |
| +---------------+ |
| | Next: 0x7F20  | | ----> Points to address 0x7F20
| +---------------+ |
+-------------------+

In Kotlin, a basic node is declared as:

Copy codeclass Node<T>(
    var data: T,
    var next: Node<T>? = null
)

The Chain in Physical Memory

Because nodes are allocated dynamically on the heap as needed, they do not occupy consecutive addresses:

Copy codeHeap Addresses:
  0x1040: [ Data: "A" | Next: 0x8820 ]
  0x8820: [ Data: "B" | Next: 0x3100 ]
  0x3100: [ Data: "C" | Next: null   ]

Logical View:
  [ Head: "A" ] ---> [ "B" ] ---> [ "C" | null ]

The list is accessed through a single entry reference called the Head. The last node's next pointer points to null (or nullptr), signaling the end of the sequence.

The Mechanism of Pointer Hopping

To read the k-th element, the CPU cannot compute an offset mathematically as it does in an array. It must start at head and follow pointers sequentially:

Copy codefun get(head: Node<T>?, index: Int): T? {
    var current = head
    var count = 0
    while (current != null) {
        if (count == index) return current.data
        count++
        current = current.next // Dereference pointer: jump to next heap address
    }
    return null // Out of bounds
}

This pointer traversal runs in O(n) time and incurs CPU cache misses because each node is located in a different cache line in RAM.

Memory Overhead of Node References

Consider storing 1,000,000 32-bit integers:

• IntArray (4MB): 1,000,000 × 4 bytes = 4 MB payload, 0 pointer overhead.
• LinkedList (32–48MB):
  • Each Node object header: 16 bytes.
  • Data reference: 8 bytes (or boxed Integer: 16 bytes + 4 bytes).
  • Next pointer: 8 bytes.
  • Total per node: ~32 to 48 bytes.
  • Total memory: 32 MB to 48 MB — an 8x to 12x memory inflation!

Summary

• Linked lists store elements in discrete nodes connected via pointers/references.
• Nodes are scattered throughout heap memory, requiring sequential O(n) pointer traversal.
• Offers fast O(1) insertion at known pointers, but carries heavy pointer memory overhead.