Linked Lists in Memory

Linked Lists in Computer Memory

To truly master Data Structures, you have to understand what the computer is doing physically under the hood.

In the previous tutorial, we introduced the concept of a Linked List. Now, let's look at how your computer actually stores it in RAM (Random Access Memory).

1. The Array Memory Problem

Remember how Arrays work? They require contiguous memory.

If you want to create an array that holds 4 items, the computer must find 4 empty memory slots right next to each other.

What happens if your computer's RAM is fragmented? What if there are plenty of empty slots, but no 4 slots are side-by-side?

If you try to create an Array, the computer will throw an "Out of Memory" error, even if there is technically enough total space available!

2. The Linked List Solution

A Linked List solves this fragmentation problem beautifully.

When you create a Node in a Linked List, the computer just finds the very first empty slot it can find anywhere in RAM. It drops the Node there.

When you create a second Node, the computer finds another random empty slot.

Because the Nodes have Pointers, they don't need to be neighbors! Node 1 simply holds the exact GPS coordinates (the memory address) of Node 2.

Arrays must be packed together. Linked Lists can stretch across scattered memory cells.

3. Pointers and References

What exactly is a Pointer?

A Pointer (or Reference) is just a variable that stores a memory address instead of an actual value.

If Node 1's data is the number 10, and Node 1 lives at memory address 0x100, it might look like this:

• Address: 0x100
• Data: 10
• Next Pointer: 0x450 (This points to Node 2!)

The computer looks at the Next Pointer, instantly jumps across the RAM to address 0x450, and finds Node 2 waiting there.

4. The Hidden Cost: Memory Overhead

Nothing in Computer Science is perfect. Linked Lists come with a hidden cost: Memory Overhead.

Because every single Node must store both its Data AND a Next Pointer, a Linked List actually takes up more total memory than an Array holding the same data.

Example:

If you store the number 10 in an Array, it takes up 4 bytes of memory. If you store the number 10 in a Linked List Node, it takes 4 bytes for the number, plus 8 extra bytes to store the Pointer to the next node!

Summary:

• Arrays: Highly memory efficient, but inflexible.
• Linked Lists: Highly flexible, but require extra memory for pointers.