Node Structure and Pointer Design in DSA C

Mental Model

A node is a small box that holds data and a pointer to the next box, linking them like a chain.

Analogy: Imagine a treasure hunt where each clue points you to the next clue, forming a chain of clues to follow.

Node1[data|->] -> Node2[data|->] -> Node3[data|->] -> null

Dry Run Walkthrough

Input: Create a linked list with nodes holding values 10, 20, 30 linked in order

Goal: Build a chain of nodes where each node points to the next, ending with null

Step 1: Create first node with data 10 and pointer null

[10|null]

Why: Start the chain with the first node pointing to nothing yet

Step 2: Create second node with data 20 and pointer null

[10|null]   [20|null]

Why: Prepare the next node to link after the first

Step 3: Set first node's pointer to second node

[10|->] -> [20|null]

Why: Link first node to second to form the chain

Step 4: Create third node with data 30 and pointer null

[10|->] -> [20|null]   [30|null]

Why: Prepare the third node to add to the chain

Step 5: Set second node's pointer to third node

[10|->] -> [20|->] -> [30|null]

Why: Link second node to third to complete the chain

Result:

[10|->] -> [20|->] -> [30|null]

Annotated Code

DSA C

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

// Define the node structure
typedef struct Node {
    int data;           // Store the value
    struct Node* next;  // Pointer to next node
} Node;

// Function to create a new node with given data
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;          // Set data
    newNode->next = NULL;           // Initialize next pointer to NULL
    return newNode;
}

// Function to print the linked list
void printList(Node* head) {
    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() {
    // Step 1: Create first node
    Node* head = createNode(10);

    // Step 2: Create second node
    Node* second = createNode(20);

    // Step 3: Link first node to second
    head->next = second;

    // Step 4: Create third node
    Node* third = createNode(30);

    // Step 5: Link second node to third
    second->next = third;

    // Print the linked list
    printList(head);

    // Free allocated memory
    free(third);
    free(second);
    free(head);

    return 0;
}

newNode->data = value; // Set data

store the value in the node

newNode->next = NULL; // Initialize next pointer to NULL

initialize pointer to null to mark end

head->next = second;

link first node to second node

second->next = third;

link second node to third node

while (current != NULL) { printf("%d -> ", current->data); current = current->next; }

traverse nodes printing data until end

Output

10 -> 20 -> 30 -> null

Complexity Analysis

Time: O(n) because creating and linking n nodes requires visiting each node once

Space: O(n) because each node uses memory for data and pointer

vs Alternative: Compared to arrays, linked nodes allow dynamic size without shifting elements but use extra memory for pointers

Edge Cases

Empty list (no nodes)

Head pointer is NULL, no nodes to link or print

DSA C

while (current != NULL) {

Single node list

Node's next pointer is NULL, list ends after one node

DSA C

newNode->next = NULL;

When to Use This Pattern

When you need a flexible chain of elements that can grow or shrink easily, look for node and pointer design to build linked lists.

Common Mistakes

Mistake: Forgetting to set the next pointer to NULL when creating a new node
Fix: Always initialize the next pointer to NULL to mark the end of the list

Mistake: Not linking nodes properly, leaving pointers unconnected
Fix: Assign the next pointer of the current node to the new node to maintain the chain

Summary

It creates small boxes (nodes) that hold data and point to the next box, forming a chain.

Use it when you want a list that can grow or shrink without moving all elements.

Remember each node must store data and a pointer to the next node or null if last.