Insert at End

Appending at the tail of a singly linked list means linking the new node after the current last node. If you only keep head, you must walk from the head until cur->next == NULL—that walk is O(n) in the list length. The empty list (head == NULL) is a special case: the new node becomes the head.

C program (return `head`)

The function returns the same head after appending (except when the list was empty, in which case the new node becomes the head). In main you still write head = insert_end(head, value); for consistency.

newNode->next = NULL; because the new node is always the last.
If head == NULL, return newNode; otherwise find the last node and set cur->next = newNode.

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

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

struct Node *insert_end(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)
        return newNode;

    struct Node *cur = head;
    while (cur->next != NULL)
        cur = 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");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

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

    head = insert_end(head, 10);
    head = insert_end(head, 20);
    head = insert_end(head, 30);

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

    free_list(head);
    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_end(head, 10)`	Node with data `10`	`10`
3	`head = insert_end(head, 20)`	Still first node `0x1000`	`10 20`
4	`head = insert_end(head, 30)`	Still first node `0x1000`	`10 20 30`
5	`print_list(head)`	Same as step 4	Output line: `10 20 30`
6	`free_list(head)`	All nodes freed	List destroyed (no nodes left)

Each `insert_end` call in detail

Call 1: insert_end(NULL, 10)

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

After call 1:

head → [10 | NULL]

Call 2: insert_end(0x1000, 20)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x2000`
2	Set `newNode->data` / `next`	`newNode`	`20`, `next = NULL`
3	`head` not `NULL`	`cur`	Walk: `cur = head`, then `cur->next == NULL` → last is `0x1000`
4	Link last to new node	`cur->next`	`0x2000`
5	Return `head`	return value	`0x1000` (unchanged)

After call 2:

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

Call 3: insert_end(0x1000, 30)

Step	Operation	Variable	Value
1	Allocate new node	`newNode`	Address: `0x3000`
2	Set `newNode->data` / `next`	`newNode`	`30`, `next = NULL`
3	Walk to last node	`cur`	`0x1000` → `0x2000` (stops; last node)
4	`cur->next = newNode`	`cur->next`	`0x3000`
5	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` (first insert)	10	`0x2000`	`n2`
`0x2000`	`n2`	20	`0x3000`	`n3`
`0x3000`	`n3` (last insert)	30	`NULL`	nowhere

Visual representation

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

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

Inside insert_end when head is 0x1000 (list 10 → 20) and data is 30:

Line	Code	Before	After
1	`malloc(sizeof(struct Node))`	—	Heap block at `0x3000`; `newNode = 0x3000`
2	`if (newNode == NULL)`	`newNode = 0x3000` (not `NULL`)	Skip `return head`
3	`newNode->data = data;`	`newNode->data` uninitialized	`newNode->data = 30`
4	`newNode->next = NULL;`	—	New node is ready as tail
5	`if (head == NULL)`	`head = 0x1000`	Skip `return newNode`
6	`cur = head;`	—	`cur = 0x1000`
7	`while (cur->next != NULL) cur = cur->next;`	`cur` at `0x1000`, then `0x2000`	`cur` is last node (`0x2000`)
8	`cur->next = newNode;`	`0x2000->next` was `NULL`	`0x2000->next = 0x3000`
9	`return head;`	Return `0x1000`	In `main`: `head` still `0x1000`

Complexity summary

Operation	Time	Extra space
`insert_end` (no tail pointer)	`O(n)` — walk to last node; `n` = current length	`O(1)` for the one new node
`print_list`	`O(n)`	`O(1)`
`free_list`	`O(n)`	`O(1)`
Whole program (repeated append + print + free)	`O(n²)` total time for `n` successive appends (each walk grows); print/free `O(n)` each	`O(n)` nodes stored in the list

The key takeaway is that inserting at the end without a tail pointer costs O(n) time per insert because you must scan from the head to the last node. That makes building a list with many appends O(n²) overall, unlike insert-at-head. Keeping a tail pointer (or a doubly linked list with tail) gives O(1) append when you only need access at both ends.

Alternative: maintain struct Node *tail (update it whenever the list changes), or pass struct Node **head / **tail so the callee can update both—same append logic, no full walk each time if tail is known.