Insert at End Tail Insert in DSA C

Mental Model

Add a new item at the very end of a chain of items by moving to the last one and linking the new item after it.

Analogy: Imagine a line of people holding hands. To add a new person at the end, you walk to the last person and hold their hand.

head -> 1 -> 2 -> 3 -> null
                 ↑
               current

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, insert value 4 at end

Goal: Add the value 4 as the last node so the list becomes 1 -> 2 -> 3 -> 4 -> null

Step 1: start at head node with value 1

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

Why: We begin traversal from the first node to find the end

Step 2: move current to next node with value 2

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

Why: We keep moving forward to reach the last node

Step 3: move current to next node with value 3

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

Why: Current is now at the last node before null

Step 4: create new node with value 4 and link it after current

head -> 1 -> 2 -> 3 -> [4] -> null
                         ↑ new tail

Why: Attach new node at the end by setting last node's next to new node

Result:

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

Annotated Code

DSA C

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

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

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

// Insert at end function
void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode; // empty list, new node is head
        return;
    }
    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next; // advance to last node
    }
    current->next = newNode; // link new node at end
}

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

int main() {
    struct Node* head = createNode(1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    insertAtEnd(&head, 4); // insert value 4 at end
    printList(head);
    return 0;
}

while (current->next != NULL) { current = current->next; // advance to last node }

advance current to last node to find where to insert

current->next = newNode; // link new node at end

attach new node after last node to extend list

if (*head == NULL) { *head = newNode; // empty list, new node is head return; }

handle empty list by making new node the head

Output

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

Complexity Analysis

Time: O(n) because we traverse all n nodes once to reach the end

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to inserting at the front which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes the head of the list

DSA C

if (*head == NULL) {
        *head = newNode; // empty list, new node is head
        return;
    }

single element list

new node is linked after the single existing node

DSA C

while (current->next != NULL) {
        current = current->next; // advance to last node
    }

When to Use This Pattern

When you need to add an item at the end of a linked list, use the tail insert pattern by traversing to the last node and linking the new node after it.

Common Mistakes

Mistake: Not handling the empty list case, causing a null pointer dereference
Fix: Check if head is NULL and assign new node as head before traversal

Mistake: Linking new node before reaching the last node, breaking the list
Fix: Traverse fully until current->next is NULL before linking new node

Summary

Adds a new node at the end of a linked list by traversing to the last node and linking the new node.

Use when you want to keep the existing order and append new data at the tail.

The key insight is to find the last node whose next pointer is null and attach the new node there.

Practice

1. What does the 'Insert at End' operation do in a singly linked list?

easy

A. Adds a new node at the end (tail) of the list

B. Deletes the last node of the list

C. Adds a new node at the beginning (head) of the list

D. Searches for a node at the end of the list

Solution

1. Step 1: Understand the operation

   Inserting at the end means adding a new node after the current last node.

2. Step 2: Identify the effect on the list

   The new node becomes the new tail, extending the list by one node.

3. Final Answer:

   Adds a new node at the end (tail) of the list -> Option A

4. Quick Check:

   Insert at end = Add node at tail [OK]

Hint: Insert at end means add after last node [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it deletes a node
• Assuming it searches instead of inserts

2. Which of the following is the correct syntax to create a new node in C for tail insertion?

easy

A. newNode = malloc(sizeof(Node));

B. struct Node newNode = malloc(sizeof(struct Node));

C. Node newNode = malloc(sizeof(Node));

D. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

Solution

1. Step 1: Understand node creation in C

   We use malloc to allocate memory and cast it to pointer of struct Node.

2. Step 2: Check syntax correctness

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); correctly casts malloc result to (struct Node*) and uses sizeof(struct Node).

3. Final Answer:

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); -> Option D

4. Quick Check:

   Correct malloc and cast syntax = struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); [OK]

Hint: Use malloc with (struct Node*) cast for new node [OK]

Common Mistakes:

• Missing cast to (struct Node*)
• Using wrong type without struct keyword
• Assigning malloc to struct variable instead of pointer

3. What will be the output linked list after inserting 4 at the end of the list 1 -> 2 -> 3 -> NULL using tail insertion?

medium

A. 1 -> 2 -> 3 -> NULL

B. 1 -> 2 -> 3 -> 4 -> NULL

C. 1 -> 2 -> 4 -> 3 -> NULL

D. 4 -> 1 -> 2 -> 3 -> NULL

Solution

1. Step 1: Understand tail insertion effect

   Inserting 4 at the end adds it after 3, the current tail.

2. Step 2: Visualize the new list

   The list becomes 1 -> 2 -> 3 -> 4 -> NULL after insertion.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> NULL -> Option B

4. Quick Check:

   Insert 4 at tail = 1->2->3->4->NULL [OK]

Hint: New node goes after last node, not at front [OK]

Common Mistakes:

• Inserting at head instead of tail
• Placing new node in middle
• Not updating tail pointer

4. Given the following code snippet for tail insertion, what is the error?

void insertAtEnd(struct Node** head, int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  if (*head == NULL) {
    *head = newNode;
  } else {
    struct Node* temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp = newNode;
  }
}

medium

A. temp = newNode; does not link newNode to the list

B. Missing malloc for newNode

C. newNode->next should not be NULL

D. Head pointer is not updated when list is empty

Solution

1. Step 1: Analyze the while loop and insertion

   The code moves temp to last node, but then does temp = newNode; which only changes temp pointer.

2. Step 2: Identify correct linking

   To link newNode, temp->next should be assigned newNode, not temp itself.

3. Final Answer:

   temp = newNode; does not link newNode to the list -> Option A

4. Quick Check:

   Link newNode by temp->next = newNode [OK]

Hint: Assign newNode to temp->next, not temp [OK]

Common Mistakes:

• Assigning newNode to temp pointer instead of temp->next
• Forgetting to set newNode->next to NULL
• Not handling empty list case

5. You have a singly linked list with nodes 10 -> 20 -> 30 -> NULL. You want to insert 40 at the end using tail insertion. Which of the following code snippets correctly performs this insertion and updates the list?

hard

A. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nhead = newNode;

B. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = head;\nhead = newNode;

C. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nstruct Node* temp = head;\nwhile(temp->next != NULL) { temp = temp->next; }\ntemp->next = newNode;

D. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\nnewNode->data = 40;\nnewNode->next = NULL;\nstruct Node* temp = head;\nwhile(temp != NULL) { temp = temp->next; }\ntemp->next = newNode;

Solution

1. Step 1: Create new node with data 40 and next NULL

   This prepares the new node to be added at the end.

2. Step 2: Traverse list to last node

   Using while(temp->next != NULL) moves temp to last node (30).

3. Step 3: Link last node's next to newNode

   temp->next = newNode correctly attaches new node at end.

4. Final Answer:

   Traverse to last node with while(temp->next != NULL), then temp->next = newNode -> Option C

5. Quick Check:

   Traverse to tail, then temp->next = newNode [OK]

Hint: Traverse to last node, then link new node at next [OK]

Common Mistakes:

• Setting newNode->next to head (inserts at front)
• Not updating last node's next pointer
• Loop condition allowing temp to become NULL