How to Implement a Linked List from Scratch

What is linked list implementation?

Think of a linked list not as a list, but as a train. Each car (node) holds your data and has a single coupling (a next pointer) that points to the next car. There's no central depot; the entire train is found by starting at the first car and following the couplings one by one. This is the core intuition for a singly linked list: a chain of independent nodes connected only by these forward pointers.

This pointer-based chain is fundamentally different from an array's contiguous block of memory. An array is like a long row of houses—you know exactly where house #5 is by simple arithmetic. In a linked list train, you have to walk from the engine (the head) through each car to find the fifth one. That walk is traversal, and it's the price you pay for the list's flexible, dynamic size.

A common beginner assumption is that linked lists are universally "faster" than arrays because inserting or deleting feels like a simple pointer change. This is often wrong for real-world performance. The overhead of those extra pointers (memory) and the cost of chasing scattered memory addresses (time) usually makes arrays faster for most access patterns.

Arrays benefit from cache locality: when you read element 0, the CPU likely preloads elements 1, 2, 3... into its fast cache because they're right next door. A linked list's nodes can be scattered all over memory, causing constant cache misses and slowing down even simple traversal. So, while linked lists excel at frequent, arbitrary insertions/deletions, they are typically slower for sequential access than a well-used array.

Data structures for beginners: linked list fundamentals

Think of a singly linked list node as the simplest possible "smart container". It holds data and knows about exactly one other container. This simple pattern—a self-referential structure with a next pointer—is a fundamental building block.

Once you understand how to chain these nodes together, you can build more complex structures by simply changing the rules of connection:

In computer science, we separate the what (the Abstract Data Type, or ADT) from the how (the data structure). The ADT "list" promises operations like insert and delete. A linked list is one way to fulfill that promise—using dynamic nodes and pointers. Another way is an array (contiguous memory). Understanding the linked list implementation gives you a mental model for how dynamic, pointer-based structures work under the hood.

// Start at the first car
Node* current = head;

// Walk 'index' steps forward
for (int i = 0; i < index; i++) {
    // Check if we fell off the end
    if (current == NULL) {
        return NULL; 
    }
    // Follow the coupling to next car
    current = current->next;   
}
// Found the target car
return current;

The for loop is the walk. If index is 1000, you must perform up to 1000 pointer dereferences (current->next). This is fundamentally different from an array, where array[1000] calculates the memory address instantly (base address + element size * 1000), a constant-time O(1) operation.

Why this matters: If your algorithm frequently needs random access (e.g., "give me the 500th element"), a linked list will be dramatically slower than an array. The linked list's strength is efficient insertion/deletion once you're already at the correct position, and efficient sequential traversal. Never assume it provides fast random access—that's the array's job.

Linked list in C: setting up the environment

Welcome to the "under the hood" experience. If you've programmed in Python or Java, you're used to references feeling like magic—just assign node.next = other_node and the computer handles the rest.

In C, the magic curtain is pulled back. You are now the architect of memory. You explicitly ask for space, you explicitly hold the addresses, and you explicitly free it. This isn't just "harder"—it's empowering. By forcing you to handle the * (dereference) and & (address-of) operators, C ensures you truly understand that a pointer is simply an integer storing a memory location.

#include <stdio.h>
#include <stdlib.h> // CRITICAL: For memory allocation

// 1. The Node Definition
typedef struct Node {
    int data;               // The payload
    struct Node* next;      // The bridge to the next node
} Node;

int main() {
    // Start with an empty list (NULL)
    Node* head = NULL;

    // 2. Allocate memory for the first node
    // malloc asks the OS for enough bytes to hold a Node
    head = (Node*)malloc(sizeof(Node));

    // 3. Initialize
    head->data = 10;        // Set the value
    head->next = NULL;     // Mark end of list

    // ... use the list ...

    // 4. Clean up (prevent memory leaks)
    free(head);
    return 0;
}

When the compiler assumes int (32-bit) instead of void* (64-bit on modern systems), it chops off the upper half of your memory address. You end up with a pointer that points to the wrong place—often inside the operating system's protected memory. When you try to write data there, the OS kills your program instantly.

The Rule: Always include <stdlib.h> at the top. It tells the compiler: "I am going to ask for memory, and I expect a full pointer back."

Implement linked list from scratch: core structure

We've talked about the "train" analogy, but now we need to look at the blueprint. In C, a node isn't a magical object; it's a rigid block of memory defined by a struct.

The magic of the linked list lies in the next pointer. It doesn't hold the next node inside it—that would be infinite recursion! Instead, it holds the address (a number) of where the next node lives.

Notice something important: there is no struct LinkedList. The "list" is an illusion created by the head pointer.

The rule is simple: Always initialize your pointers. Even if you plan to assign them a valid memory address immediately after, setting them to NULL first is a safety habit that saves you from hours of debugging "Segmentation Faults."

Once head is safely NULL, you are ready to start allocating your first node and linking them together.

Core linked list operations: Rewiring the Train

We've established that a linked list is a chain of couplings. Now, let's perform surgery on the train. In C, operations like insertion and deletion are purely about rewiring.

You don't "shift" elements like in an array. You simply change the next pointer of the previous node to point to a different address.

Here is the correct pattern for deletion. Notice how we handle the rewiring (lines 13-17) before we call free() (line 19).

// Function to delete node at specific index
void delete_node_at_index(Node** head_ref, int index) {
    Node* current = *head_ref;
    Node* prev = NULL;

    // 1. Find the node to delete (and its predecessor)
    for (int i = 0; current != NULL && i < index; i++) {
        prev = current;
        current = current->next;
    }
    if (current == NULL) return; // Index out of bounds

    // 2. REWIRE: The Critical Step
    if (prev == NULL) {
        // Special case: Deleting the Head
        *head_ref = current->next; // Head now points to second node
    } else {
        // Normal case: Skip over 'current'
        prev->next = current->next; 
    }

    // 3. FREE: Now it's safe to scrap the memory
    free(current); 
}

Insertion in linked list: step-by-step guide

We've mastered the anatomy of the train. Now, let's perform the most common surgery: Insertion.

Think of the train cars again. Inserting a new car depends entirely on where you attach it.

Head insertion is the fastest operation you can perform—technically O(1). It doesn't matter if your list has 1 car or 1,000,000 cars. You just attach the new one at the front.

However, in C, this speed comes with a dangerous trap. Beginners often write code that looks correct but fails silently. This is the "Pass-by-Value" Trap.

To fix this, we need to give the function the address of the head variable itself. This is called a double pointer (Node**).

// Correct Implementation
void insert_at_head(Node** head_ref, int data) {
    // 1. Allocate new node
    Node* new_node = malloc(sizeof(Node));
    new_node->data = data;

    // 2. Point new node to the OLD head
    // *head_ref gives us the value of head (the address)
    new_node->next = *head_ref;

    // 3. Update the ORIGINAL head pointer
    // *head_ref = new_node changes the variable in main()
    *head_ref = new_node;
}

This pattern—Node** head_ref—is the standard way to modify the head of a linked list in C. It ensures that whether the list is empty or full, your new node becomes the new engine, and your program remains safe.

Traversal and searching in linked list

Traversal is simply walking the train. You start with your hand on the engine (head) and follow each coupling (next) until you reach the end (NULL).

There is no alternative—this is the only way to visit every node in sequence. Every other operation (insertion, deletion, searching) must begin with some form of traversal to reach the relevant position.

// Start at the engine
Node* current = head;

// Keep walking until you hit the end
while (current != NULL) {
    printf("%d ", current->data); // Process data
    current = current->next;            // Move to next coupling
}

This linear cost is by design, not a bug. It's the trade-off for dynamic size and cheap insertion/deletion. Traversal is acceptable when:

• You need to process every element (e.g., printing, summing).
• Your list is relatively small.
• Insertions/deletions are frequent, but full scans are rare.
• You're building something like a stack or queue where you only ever touch the head or tail.

Bottom line: Don't expect linked lists to beat arrays at searching or random access. Their strength is flexible reshaping of the chain after you've walked to the right spot. If your workload involves many "find and insert/delete" operations on large lists, consider whether the traversal overhead negates the insertion benefit—sometimes a balanced tree or a dynamic array is better.

Testing and debugging linked list code

You've written insert_at_head, delete_at_index, and traverse. You run main(), it prints something, and it exits without crashing. Is it correct? Probably not.

Linked list bugs are silent assassins. A single misplaced pointer can leave your list internally inconsistent—nodes orphaned, cycles created, memory leaked—yet the program may still run and print something. The only way to gain confidence is to systematically verify the list's structure after every operation, not just its output.

// Test 1: Insert three nodes at head
insert_at_head(&head, 30);
insert_at_head(&head, 20);
insert_at_head(&head, 10); 

// Expected: 10 -> 20 -> 30 -> NULL
int expected[] = {10, 20, 30};
Node* current = head;

for (int i = 0; i < 3; i++) {
    // 1. Check if node exists
    assert(current != NULL);        
    // 2. Check if data matches
    assert(current->data == expected[i]); 
    // 3. Move to next
    current = current->next;
}
// 4. Check termination
assert(current == NULL);

Common Misconception: "If the program runs and prints something, it's fine. I'll only debug when it segfaults."

// The Correct Pattern
void delete_node(Node** head_ref, int key) {
    Node* temp = *head_ref;
    Node* prev = NULL;

    // 1. Locate the node
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;

    // 2. REWIRE (Critical Step)
    // If prev exists, point it to temp's next
    if (prev != NULL) prev->next = temp->next;
    else *head_ref = temp->next;

    // 3. FREE (Safe now)
    free(temp); 
}

Tools of the Trade:
AddressSanitizer (ASan): Compile with gcc -fsanitize=address -g. It detects invalid reads/writes and use-after-free errors instantly.
Valgrind: Run valgrind --leak-check=full ./program. It tracks every allocation and reports exactly where memory was lost.

Bottom line: A program that "seems to work" is often a program with a ticking memory bomb. Your job is to prove it's safe, not assume it. Write assert tests for structure, and run your code through ASan/Valgrind for memory safety.

Frequently Asked Questions (FAQ)

You've built the train, learned to add cars, and even performed surgery on the couplings. Now, let's address the most common questions that trip up students.

void delete_head(Node* head) {
    free(head);
    // head = head->next; 
    // This only changes the LOCAL copy!
    // The original 'head' in main() is still pointing to free'd memory.
}

void delete_head(Node** head_ref) {
    // Use ** (pointer to pointer)
    Node* temp = *head_ref;
    *head_ref = (*head_ref)->next; // Update the ORIGINAL head
    free(temp);
}