Insert at Position (Middle)

Inserting at a 0-based index pos means: if pos == 0, update the head like insert-at-beginning; otherwise walk pos - 1 links to the predecessor, then splice newNode->next = cur->next and cur->next = newNode. That walk is O(pos) and at worst O(n) for length n. Invalid pos (past the end) should be rejected.

C program (return `head`)

Index pos is 0-based: 0 is the first node, length would be append-at-end (here we only use valid indices 0, 1, 2 as the list grows). In main we use head = insert_at(head, pos, value);.

pos == 0: new node's next is the old head; return the new node as head.
pos > 0: advance (pos - 1) times, then link the new node after cur.

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

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

/* pos is 0-based: 0 = before first element (new head). */
struct Node *insert_at(struct Node *head, int pos, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;

    if (pos == 0) {
        newNode->next = head;
        return newNode;
    }

    struct Node *cur = head;
    int i = 0;
    while (cur != NULL && i < pos - 1) {
        cur = cur->next;
        i++;
    }

    if (cur == NULL) {
        free(newNode);
        return head;
    }

    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

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

    head = insert_at(head, 0, 10);
    head = insert_at(head, 1, 20);
    head = insert_at(head, 2, 30);

    print_list(head);   /* 10 20 30 */

    return 0;
}

Program output

10 20 30

Overall program flow

Step	Operation	`head` points to	List state (values)
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_at(head, 0, 10)`	Node with data `10`	`10`
3	`head = insert_at(head, 1, 20)`	Still first node `0x1000`	`10 20`
4	`head = insert_at(head, 2, 30)`	Still first node `0x1000`	`10 20 30`
5	`print_list(head)`	Same as step 4	Output line: `10 20 30`

Each `insert_at` call in detail

Call 1: insert_at(NULL, 0, 10)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x1000`
2	Set `newNode->data`	`newNode->data`	`10`
3	`pos == 0`	—	`newNode->next = head` (`NULL`), return `0x1000`

After call 1:

head → [10 | NULL]

Call 2: insert_at(0x1000, 1, 20)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x2000`
2	Set `newNode->data`	`newNode->data`	`20`
3	`pos > 0`, walk `pos - 1 = 0` steps	`cur`	Stays at `head` (`0x1000`)
4	Splice after `cur`	`newNode->next`, `cur->next`	`20` after `10`
5	Return `head`	return value	`0x1000` (unchanged)

After call 2:

head → [10 | 0x2000] → [20 | NULL]

Call 3: insert_at(0x1000, 2, 30)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x3000`
2	Set `newNode->data`	`newNode->data`	`30`
3	Walk `pos - 1 = 1` step	`cur`	`0x1000` → `0x2000` (predecessor of tail)
4	`newNode->next = cur->next`	`newNode->next`	`NULL`
5	`cur->next = newNode`	`cur->next`	`0x3000`
6	Return `head`	return value	`0x1000` (unchanged)

After call 3:

head → [10 | 0x2000] → [20 | 0x3000] → [30 | NULL]

Memory layout (example addresses)

Final list in heap

Address	Node	`data`	`next`	Points to
`0x1000`	`n1` (index `0`)	10	`0x2000`	`n2`
`0x2000`	`n2` (index `1`)	20	`0x3000`	`n3`
`0x3000`	`n3` (index `2`)	30	`NULL`	nowhere

Visual representation

head (0x1000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x3000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
 (index 0)            (index 1)            (index 2)

Detailed step-by-step: call 3 (insert `30` at index `2`)

Inside insert_at when head is 0x1000 (list 10 → 20), pos == 2, and data is 30:

Line	Code	Before	After
1	`malloc(sizeof(struct Node))`	—	`newNode = 0x3000`
2	`if (newNode == NULL)`	`newNode = 0x3000`	Skip `return head`
3	`newNode->data = data;`	garbage	`30`
4	`if (pos == 0)`	`pos = 2`	Skip head-insert branch
5	`cur = head;` / `i = 0;`	—	`cur = 0x1000`, `i = 0`
6	`while (cur != NULL && i < pos - 1)`	First: `cur` at `0x1000`, `i < 1`	After one iter: `cur = 0x2000`, `i = 1`
7	`if (cur == NULL)`	`cur = 0x2000`	Skip error `free` / `return`
8	`newNode->next = cur->next;`	`0x2000->next` was `NULL`	`newNode->next = NULL`
9	`cur->next = newNode;`	—	`0x2000->next = 0x3000`
10	`return head;`	—	In `main`: `head` still `0x1000`

Complexity summary

Operation	Time	Extra space
`insert_at`	`O(pos)` ≤ `O(n)` — walk up to predecessor; index `0` is `O(1)`	`O(1)` for the one new node
`print_list`	`O(n)`	`O(1)`
Whole program (build + print)	`O(n²)` worst case for `n` successive indexed inserts when indices grow; print `O(n)`	`O(n)` nodes stored in the list

The key takeaway is that insert at position combines insert-at-head for pos == 0 and otherwise needs a walk from head to the node before the gap—so cost grows with index and list length, unlike a plain head insert for every call.

Alternative: pass struct Node **head and update *head when pos == 0, or use a doubly linked list to reach the predecessor from a known node faster when you already have pointers.