A Singly Linked List is one of the most fundamental dynamic data structures in computer science. Unlike arrays, which require a contiguous block of memory with a fixed size, linked lists store elements as independent nodes scattered across the Heap, connected together by pointer addresses.

Linked lists allow O(1) constant-time insertions and deletions at the head without resizing or shifting elements.

In this step-by-step guide, you will learn how to build a complete, robust singly linked list in C from scratch. We will implement node creation, insertion at the head, tail, and arbitrary positions, node deletion, searching, list reversal, and safe memory destruction with zero leaks.

---

1. Array vs. Linked List: Complexity Comparison

---

2. Anatomy of a Node: Structure & Visual Memory

Each element in a singly linked list is called a Node. A node contains two parts:

1. Data: The value stored in the node (e.g., int, float, or a struct).
2. Next Pointer: A pointer variable holding the memory address of the subsequent node in the chain. The last node in the list points to NULL.

c (ISO Standard)
Run in Compiler.cCopy
typedef struct Node {
    int data;           // Stored payload
    struct Node *next;  // Pointer to the next node
} Node;

text (ISO Standard)
Copy
[Head Pointer] 
     | (0x1000)
     v
+--------------+      +--------------+      +--------------+
| Data: 10     | ---> | Data: 20     | ---> | Data: 30     | ---> NULL
| Next: 0x2000 |      | Next: 0x3000 |      | Next: NULL   |
+--------------+      +--------------+      +--------------+
Address: 0x1000       Address: 0x2000       Address: 0x3000

---

3. Step-by-Step Function Implementations

Let us build every operation required for a complete linked list implementation.

---

Step 1: Creating a New Node

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdlib.h>

Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Error: Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

---

Step 2: Insert at the Beginning (Head) — O(1)

To insert at the beginning, point the new node's next to the current head, then update head to become the new node. We pass Node **headRef (a double pointer) so we can modify the caller's head variable:

c (ISO Standard)
Run in Compiler.cCopy
void insertAtHead(Node **headRef, int data) {
    Node *newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

---

Step 3: Insert at the End (Tail) — O(n)

If the list is empty, the new node becomes the head. Otherwise, traverse to the last node whose next == NULL and link it:

c (ISO Standard)
Run in Compiler.cCopy
void insertAtTail(Node **headRef, int data) {
    Node *newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }

    Node *current = *headRef;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

---

Step 4: Delete a Node by Value — O(n)

When deleting a node, you must bridge the previous node's next pointer directly to the target node's subsequent node before calling free():

c (ISO Standard)
Run in Compiler.cCopy
void deleteByValue(Node **headRef, int targetValue) {
    if (*headRef == NULL) return;

    Node *temp = *headRef;

    // Case 1: The head node holds the target value
    if (temp->data == targetValue) {
        *headRef = temp->next;
        free(temp);
        return;
    }

    // Case 2: Search for the node to delete, tracking 'prev'
    Node *prev = NULL;
    while (temp != NULL && temp->data != targetValue) {
        prev = temp;
        temp = temp->next;
    }

    // Value not found in list
    if (temp == NULL) return;

    // Unlink target node from list and free memory
    prev->next = temp->next;
    free(temp);
}

---

Step 5: Safe Memory Destruction (Preventing Leaks)

To delete the entire list, save current->next into a temporary pointer before calling free(current):

c (ISO Standard)
Run in Compiler.cCopy
void freeList(Node **headRef) {
    Node *current = *headRef;
    Node *nextNode = NULL;

    while (current != NULL) {
        nextNode = current->next; // Save address before freeing!
        free(current);
        current = nextNode;
    }

    *headRef = NULL; // Prevent dangling pointer
}

---

4. Complete Runnable C Program

Here is the complete, self-contained implementation with list printing and traversal:

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>
#include <stdlib.h>

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

Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        fprintf(stderr, "Allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtHead(Node **headRef, int data) {
    Node *newNode = createNode(data);
    newNode->next = *headRef;
    *headRef = newNode;
}

void insertAtTail(Node **headRef, int data) {
    Node *newNode = createNode(data);
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }
    Node *current = *headRef;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

void deleteByValue(Node **headRef, int targetValue) {
    if (*headRef == NULL) return;
    Node *temp = *headRef;

    if (temp->data == targetValue) {
        *headRef = temp->next;
        free(temp);
        return;
    }

    Node *prev = NULL;
    while (temp != NULL && temp->data != targetValue) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

void printList(const Node *head) {
    const Node *current = head;
    printf("List: ");
    while (current != NULL) {
        printf("[%d] -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void freeList(Node **headRef) {
    Node *current = *headRef;
    Node *nextNode = NULL;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
}

int main(void) {
    Node *head = NULL;

    printf("=== Singly Linked List Operations ===\n");
    insertAtTail(&head, 10);
    insertAtTail(&head, 20);
    insertAtTail(&head, 30);
    printList(head); // Output: [10] -> [20] -> [30] -> NULL

    printf("\nInserting 5 at Head:\n");
    insertAtHead(&head, 5);
    printList(head); // Output: [5] -> [10] -> [20] -> [30] -> NULL

    printf("\nDeleting value 20:\n");
    deleteByValue(&head, 20);
    printList(head); // Output: [5] -> [10] -> [30] -> NULL

    // Release all heap memory
    freeList(&head);
    printf("\nAfter freeList:\n");
    printList(head); // Output: List: NULL

    return 0;
}

---

Frequently Asked Questions (FAQ)

1. How do you reverse a singly linked list iteratively in C?

Reversing a linked list requires three pointers: prev, current, and next:

c (ISO Standard)
Run in Compiler.cCopy
void reverseList(Node **headRef) {
    Node *prev = NULL;
    Node *current = *headRef;
    Node *next = NULL;

    while (current != NULL) {
        next = current->next; // Store next
        current->next = prev; // Reverse current node's pointer
        prev = current;       // Move prev forward
        current = next;       // Move current forward
    }
    *headRef = prev;
}

2. How do you detect a cycle (loop) in a linked list?

Use Floyd's Cycle-Finding Algorithm (also known as the Tortoise and Hare Algorithm). Maintain a slow pointer advancing 1 node at a time and a fast pointer advancing 2 nodes at a time. If slow == fast at any point, a cycle exists.

3. Why pass a double pointer Node **headRef to insertion functions?

In C, function arguments are passed by value. If you pass a single pointer Node *head, modifying head = newNode inside the function alters only a local copy. Passing a double pointer (&head) lets the function modify the caller's actual head pointer variable.

---

Conclusion

Building a singly linked list in C gives you deep insight into how pointer references, dynamic heap allocation, and data structures interact at the hardware level. By mastering node traversal, insertion/deletion pointer rewiring, and safe memory destruction, you are equipped to build advanced structures like stacks, queues, hash tables, and binary search trees.

---

Related Technical Resources

• Master pointer mechanics in Pointers in C Explained — Visual Memory & Code Guide.
• Prevent memory leaks in How to Prevent Memory Leaks in C with malloc & free.