Creating a Singly Linked List from Scratch in DSA C - Step-by-Step

Mental Model

A singly linked list is a chain of nodes where each node points to the next one, forming a line.

Analogy: Imagine a treasure hunt where each clue (node) tells you where to find the next clue, leading you step by step to the treasure.

head -> [node1] -> [node2] -> [node3] -> null

Dry Run Walkthrough

Input: Create a singly linked list with values 1, 2, 3 in order

Goal: Build a linked list where each node holds a value and points to the next node, ending with null

Step 1: Create first node with value 1 and set head to it

head -> [1] -> null

Why: We need a starting point for the list

Step 2: Create second node with value 2 and link first node to it

head -> [1] -> [2] -> null

Why: Link the new node to the list to extend it

Step 3: Create third node with value 3 and link second node to it

head -> [1] -> [2] -> [3] -> null

Why: Continue linking nodes to build the list

Result:

head -> 1 -> 2 -> 3 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define the node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node with given data
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data; // store data in node
    newNode->next = NULL; // next pointer is null initially
    return newNode;
}

// Function to print the linked list
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data); // print current node data
        current = current->next; // move to next node
    }
    printf("null\n");
}

int main() {
    struct Node* head = NULL; // start with empty list

    // Step 1: create first node
    head = createNode(1);

    // Step 2: create second node and link
    head->next = createNode(2);

    // Step 3: create third node and link
    head->next->next = createNode(3);

    // Print the final list
    printList(head);

    return 0;
}

newNode->data = data; // store data in node

store the value in the new node

newNode->next = NULL; // next pointer is null initially

initialize next pointer to null since it's a new node

head = createNode(1);

create the first node and set it as head

head->next = createNode(2);

create second node and link it to first

head->next->next = createNode(3);

create third node and link it to second

while (current != NULL) {

traverse the list until the end

current = current->next; // move to next node

advance to next node to continue traversal

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we create and link n nodes one by one

Space: O(n) because we allocate memory for n nodes

vs Alternative: Compared to arrays, linked lists allow dynamic size without shifting elements, but accessing nodes is slower since we must follow pointers

Edge Cases

empty list (no nodes created)

head remains NULL and printList prints 'null'

DSA C

while (current != NULL) {

single node list

list has one node pointing to null, printed correctly

DSA C

head = createNode(1);

When to Use This Pattern

When you need a flexible list of items where size changes often, and you want to add nodes easily, think of creating a singly linked list from scratch.

Common Mistakes

Mistake: Forgetting to set the next pointer of a new node to NULL
Fix: Always initialize newNode->next = NULL to mark the end of the list

Mistake: Not linking the new node to the previous node
Fix: Assign the previous node's next pointer to the new node to maintain the chain

Summary

Creates a chain of nodes where each node points to the next, forming a singly linked list.

Use when you want a list that can grow dynamically without fixed size.

Remember each node must store data and a pointer to the next node, ending with null.