Why Linked List Exists and What Problem It Solves in DSA C - Why This Pattern

Mental Model

A linked list lets us add or remove items easily without moving everything else.

Analogy: Imagine a treasure hunt where each clue points to the next one. You only need to follow the clues, not rearrange all of them when adding or removing one.

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

Dry Run Walkthrough

Input: array: [1, 2, 3], insert 4 at start

Goal: Show how linked list avoids moving all elements when inserting at start

Step 1: Create new node with value 4

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

Why: We prepare a new node to add without touching existing nodes

Step 2: Point new node's next to current head

new_node[4] -> [1] -> [2] -> [3] -> null

Why: Link new node to the start of the list

Step 3: Update head to new node

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

Why: Now the list starts with the new node without moving others

Result:

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

Annotated Code

DSA C

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

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

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

// Insert at start of linked list
void insertAtStart(Node** head, int value) {
    Node* newNode = createNode(value); // create new node
    newNode->next = *head;            // link new node to current head
    *head = newNode;                  // update head to new node
}

// Print linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    // Create initial list 1->2->3->null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    printf("Original list:\n");
    printList(head);

    // Insert 4 at start
    insertAtStart(&head, 4);

    printf("After inserting 4 at start:\n");
    printList(head);

    return 0;
}

Node* newNode = createNode(value); // create new node

create new node with given value

newNode->next = *head; // link new node to current head

point new node's next to current head to link it

*head = newNode; // update head to new node

update head pointer to new node to start list here

Output

Original list:

1 -> 2 -> 3 -> null

After inserting 4 at start:

4 -> 1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(1) because inserting at start only changes a few pointers without traversing the list

Space: O(1) because only one new node is created regardless of list size

vs Alternative: Compared to arrays where inserting at start requires shifting all elements O(n), linked lists do it in constant time O(1)

Edge Cases

empty list (head is NULL)

new node becomes the head and next points to NULL

DSA C

newNode->next = *head;

When to Use This Pattern

When you need to add or remove items often at the start or middle without moving all elements, linked list pattern helps by using pointers to link nodes.

Common Mistakes

Mistake: Not updating the head pointer after inserting at start
Fix: Assign the head pointer to the new node after linking it

Summary

Linked list lets you add or remove items easily by changing pointers, not moving data.

Use linked lists when you want fast insertions or deletions without shifting elements.

The key is each item points to the next, so you only change links to update the list.