Linked Lists from First Principles

The Question That Started It All

A few months ago, a senior colleague asked me a seemingly simple question: "How do linked lists actually work?"

I had used them in interviews. I had implemented them in coding problems. But standing there, trying to explain the fundamental mechanism, I realized something uncomfortable: I didn't actually understand them at a deep level. I knew the syntax. I didn't know the why.

This article is what I wish I could have said that day. It is an explanation of linked lists built from first principles, starting from the absolute basics of how computers store data and working up to why pointers are not just useful, but necessary.

Part 1: The Problem of Storage

To understand linked lists, we first need to understand the problem they solve: how computers store data.

Computer memory is a grid of numbered boxes. When you create a variable, the computer picks a box and stores your value there:

int score = 42;  // Stored in Box 5000, for example

The Array Assumption

Arrays store values in consecutive boxes:

int scores[3] = {10, 20, 30};
// Box 5000: 10, Box 5001: 20, Box 5002: 30

This design is fast for access, you can jump to any element with simple math. But it has a cost: you must know your size upfront. If you need a fourth element, you cannot simply exten -> you must find a new block, copy everything, and abandon the old location.

Contiguous Memory

Elements sit side by side in memory having fast access, but fixed size

Arrays store elements consecutively. Linked lists scatter nodes across memory and connect them through pointers.

Part 2: The Insight That Changes Everything

What if we abandoned the requirement that everything be consecutive?

Then we would not need to know how much we will store upfront. We could create elements as needed, placing each wherever memory is available.

But here is the problem: how do you find the next piece if it is not right next to the current one?

The Treasure Hunt Metaphor

Imagine a treasure hunt where each clue is hidden in a different location. The first clue is in your mailbox. When you open it, it says: "The next clue is under the third bench in the park." You go to the park, find the clue under the bench, and it says: "The next clue is taped behind the coffee shop's menu board."

Each clue contains: a message (the data) and the location of the next clue.

This is exactly how a linked list works. Instead of consecutive storage, we place each node wherever memory is available, and include a note saying where to find the next node. That note is a memory address a pointer.

Part 3: Understanding Pointers

A pointer is simply a variable that stores a memory address.

int score = 42;
int* ptr = &score;  // ptr stores the address of score

Three things happen:

score goes in Box 5000 with value 42
&score returns 5000 (the address)
ptr goes in Box 6000 with value 5000

The pointer does not contain 42—it contains where to find 42.

Why This Matters for Linked Lists

A node needs two things:

The data you want to store
The address of the next node (a pointer)

The current node cannot store the actual next node, it might not exist yet or might live elsewhere. What it can store is where to find the next node.

Part 4: Building a Linked List

Let us walk through construction step by step.

Step 1: Define the Node

struct Node {
    int data;       // The value we care about
    Node* next;     // Address of the next node
};

Step 2: Create the First Node

An empty list starts with a null pointer:

Node* head = nullptr;  // "The list points to nothing"

Node* first = new Node();
first->data = 10;
first->next = nullptr;
head = first;

new Node() asks the OS for memory and returns an address. head now points to that address.

Building a Linked List

Start with an empty list: head = nullptr

Empty list

Click "Add Node" to step through creating and linking nodes one by one.

Step 3: Add a Second Node

Node* second = new Node();
second->data = 20;
second->next = nullptr;
first->next = second;  // Link first node to second

Now:

First node (Box 8000): data=10, next=9000
Second node (Box 9000): data=20, next=nullptr
head points to 8000

The nodes are scattered in memory (8000 and 9000), but they are linked. Node 8000 says "the next node is at 9000."

Part 5: Traversing the Chain

Unlike arrays, we cannot jump to position 3 with math. We must follow the chain:

void printList(Node* head) {
    Node* current = head;
    
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "null" << endl;
}

For a list 10 -> 20 -> null:

Start: current points to 10
Print 10, move to what next points to (20)
Print 20, move to what next points to (null)
Loop ends

With arrays: base + (index * size). With linked lists: read the "next" pointer from each node. No formula—just follow the chain.

Traversing a Linked List

→

null

NULL

Press Traverse to start walking the list

The "current" pointer visits each node, following the chain until null.

Part 6: Modifying the List

Because nodes are not consecutive, inserting and deleting requires only rewiring pointers not shifting elements.

Inserting at the Front

void insertAtFront(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;    // New node points to old first node
    head = newNode;          // Head now points to new node
}

Inserting 5 at the front of 10 -> 20:

Create node with 5, point its next to the old head (10)
Update head to point to the new node (5)

Result: 5 -> 10 -> 20. No elements moved. Just rewired two pointers.

Insert at Front

head

→

null

NULL

Current list: head → 20 → 30 → 40 → NULL

Create, link, update. Three steps, no element movement.

Deleting a Node

void deleteNode(Node*& head, int value) {
    if (head == nullptr) return;
    
    // Special case: deleting the head
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    
    // General case: find node before target
    Node* current = head;
    while (current->next != nullptr && current->next->data != value) {
        current = current->next;
    }
    
    if (current->next != nullptr) {
        Node* temp = current->next;
        current->next = temp->next;  // Bypass target
        delete temp;                    // Free memory
    }
}

Deletion rewires: find the node before your target, change its next to skip the target, then free the detached node.

Delete a Node

head

→

null

NULL

Current list: head → 10 → 20 → 30 → 40 → NULL

Rewire to bypass, then delete. Order matters.

Part 7: Arrays vs Linked Lists

Operation	Array	Linked List
Access by index	O(1)	O(n)
Insert at front	O(n)	O(1)
Insert at end	O(1)	O(n)
Memory	Contiguous block	Scattered
Size	Fixed	Dynamic

Arrays win for fast random access when size is known. Linked lists win for dynamic growth and frequent front insertions.

Part 8: Complete Program

Complete Program

Initialize an empty list

head = nullptr

Node* head = nullptr;

Step through the complete program to see the list grow.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void insertAtFront(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data;
        if (current->next != nullptr) cout << " -> ";
        current = current->next;
    }
    cout << " -> null" << endl;
}

int main() {
    Node* head = nullptr;
    
    insertAtFront(head, 30);  // List: 30
    insertAtFront(head, 20);  // List: 20 -> 30
    insertAtFront(head, 10);  // List: 10 -> 20 -> 30
    
    printList(head);  // Output: 10 -> 20 -> 30 -> null
    return 0;
}

Part 9: The Deeper Understanding

When I finally understood linked lists at this level, several things clicked:

Pointers Are Infrastructure

Pointers are often taught as confusing syntax: asterisks, ampersands, arrows. But they are simply variables that store memory addresses. The syntax exists because indirection is fundamental to building complex data structures.

Dynamic Memory Requires Responsibility

Every new needs a corresponding delete. Unlike local variables, dynamically allocated nodes persist until you explicitly free them. This is power (data outlives the function that created it) and responsibility (you must clean up).

Data Structures Are Tradeoffs

Arrays sacrifice flexibility for speed. Linked lists sacrifice speed for flexibility. There is no "best" structure, only structures better suited to specific constraints.

The Physical Reality of Abstraction

Underneath every high-level concept is physical reality: electrons, memory cells, addresses. Linked lists make this visible. Each node is a real memory allocation. Each pointer is a real address. The structure lives in hardware, not just in the compiler's abstract world.

Final Thought

The next time someone asks you how linked lists work, you can say this:

A linked list solves the problem of storing an unknown amount of data. Instead of requiring consecutive memory like an array, it stores each element wherever memory is available and uses pointers variables that hold memory addresses to connect elements into a chain. Each node contains data and the address of the next node. To traverse, start at the head and follow the chain until you reach null.

Pointers are not a quirk of C++. They are the mechanism that makes non-consecutive data structures possible. Without them, every collection would need to be a fixed-size block. With them, we can build structures that grow and shrink dynamically.

That is the fundamental idea. Everything else -> insertion, deletion, traversal is just implementation of that core concept.

If you work through this explanation yourself, you will find that linked lists stop being a memorized algorithm and start being an obvious solution to a real problem. That is the difference between knowing syntax and understanding fundamentals.