Insert at End Tail Insert in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes at the tail

What is the printed linked list after inserting 10, 20, and 30 at the tail in order?

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtTail(10);
        list.insertAtTail(20);
        list.insertAtTail(30);
        list.printList();
    }
}

A 10 -> 20 -> 30 -> null

B 30 -> 20 -> 10 -> null

C 10 -> 20 -> null

D null

💡 Hint

Remember that inserting at tail adds new nodes at the end of the list.

The insertAtTail method adds nodes at the end. After inserting 10, 20, and 30, the list is 10 -> 20 -> 30 -> null.

❓ Predict Output

intermediate

Output after inserting into an initially empty list

What is the output after inserting a single node with value 5 at the tail of an empty linked list?

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtTail(5);
        list.printList();
    }
}

A 5

B null

C 5 -> null

D 0 -> 5 -> null

💡 Hint

Inserting into an empty list sets the head to the new node.

Since the list was empty, the new node with value 5 becomes the head, so the list prints as '5 -> null'.

🔧 Debug

advanced

Identify the bug in tail insertion

What error will occur when running this code that inserts nodes at the tail?

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next == null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtTail(1);
        list.insertAtTail(2);
    }
}

A Compilation error: missing semicolon

B NullPointerException due to infinite loop

C No error, code runs correctly

D ArrayIndexOutOfBoundsException

💡 Hint

Check the while loop condition carefully.

The condition 'while (temp.next == null)' causes an infinite loop when temp.next is null, leading to NullPointerException.

❓ Predict Output

advanced

Output after multiple tail insertions and one print

What is the output after inserting 1, 2, 3, 4 at tail and then printing the list?

DSA Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insertAtTail(1);
        list.insertAtTail(2);
        list.insertAtTail(3);
        list.insertAtTail(4);
        list.printList();
    }
}

A null

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

C 1 -> 2 -> 3 -> null

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

💡 Hint

Tail insertion adds nodes at the end in order.

Nodes are added at the tail, so the list prints in insertion order: 1 -> 2 -> 3 -> 4 -> null.

🧠 Conceptual

expert

Time complexity of tail insertion in singly linked list without tail pointer

What is the time complexity of inserting a node at the tail of a singly linked list when you do NOT maintain a tail pointer?

A O(n), because you must traverse the entire list to find the tail

B O(log n), because of binary search to find the tail

C O(1), because insertion at tail is always constant time

D O(n^2), because each insertion requires traversing the list multiple times

💡 Hint

Think about how you find the last node without a tail pointer.

Without a tail pointer, you must start at head and traverse all nodes to reach the tail, which takes O(n) time per insertion.

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 first node of the list

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

D. Searches for a node with a specific value

Solution

1. Step 1: Understand the operation

   Insert at End means adding a new node after the last node of the list.

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 always adds after the last node [OK]

Common Mistakes:

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

2. Which of the following is the correct Java syntax to create a new node with value 10 for a singly linked list?

easy

A. Node newNode = new Node(10);

B. Node newNode = Node(10);

C. newNode = new Node(10);

D. Node newNode = new Node(); newNode.value = 10;

Solution

1. Step 1: Recall Java object creation syntax

   In Java, new objects are created using the 'new' keyword followed by the constructor.

2. Step 2: Match syntax for node creation

   Correct syntax is: Node newNode = new Node(10); assuming Node class has a constructor taking value.

3. Final Answer:

   Node newNode = new Node(10); -> Option A

4. Quick Check:

   Use 'new' keyword and constructor for object creation [OK]

Hint: Use 'new' keyword with constructor to create objects [OK]

Common Mistakes:

• Omitting 'new' keyword
• Calling constructor without 'new'
• Not assigning to a variable

3. What will be the output linked list after executing the following code?

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

public class Test {
  public static void main(String[] args) {
    Node head = new Node(1);
    head.next = new Node(2);
    Node tail = head.next;
    Node newNode = new Node(3);
    tail.next = newNode;
    tail = newNode;
    printList(head);
  }
  static void printList(Node node) {
    while(node != null) {
      System.out.print(node.data + " -> ");
      node = node.next;
    }
    System.out.print("null");
  }
}

medium

A. 3 -> 1 -> 2 -> null

B. 1 -> 3 -> 2 -> null

C. 1 -> 2 -> 3 -> null

D. 1 -> 2 -> null

Solution

1. Step 1: Trace initial list creation

   head points to node 1, head.next points to node 2, tail points to node 2.

2. Step 2: Insert new node at end and update tail

   New node with data 3 is created, tail.next points to newNode, tail updated to newNode.

3. Step 3: Print list

   List nodes in order: 1 -> 2 -> 3 -> null.

4. Final Answer:

   1 -> 2 -> 3 -> null -> Option C

5. Quick Check:

   Tail insert adds node 3 at end [OK]

Hint: Tail always points to last node; new node added after tail [OK]

Common Mistakes:

• Not updating tail after insertion
• Confusing node order
• Printing incomplete list

4. Identify the error in the following code snippet for inserting a node at the end of a singly linked list:

public void insertAtEnd(int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
  } else {
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp = newNode;
  }
}

medium

A. The while loop condition should be 'temp != null'

B. The line 'temp = newNode;' does not link the new node to the list

C. The head is not updated when list is empty

D. The newNode is not created properly

Solution

1. Step 1: Analyze the while loop and insertion

   The loop finds the last node (temp.next == null). After loop, temp points to last node.

2. Step 2: Check how new node is linked

   Assigning 'temp = newNode;' only changes temp variable, not the last node's next pointer.

3. Step 3: Correct linking

   Should assign 'temp.next = newNode;' to link new node at end.

4. Final Answer:

   The line 'temp = newNode;' does not link the new node to the list -> Option B

5. Quick Check:

   Link new node by setting lastNode.next = newNode [OK]

Hint: Assign newNode to last node's next, not to temp variable [OK]

Common Mistakes:

• Assigning newNode to temp instead of temp.next
• Not updating head when list is empty
• Wrong loop condition

5. You have a singly linked list with nodes: 5 -> 10 -> 15 -> null. You want to insert a new node with value 20 at the end. Which sequence of steps correctly updates the list?

hard

A. Create new node with 20, set new node's next to null, but do not link it to list

B. Create new node with 20, set head to new node, set new node's next to old head

C. Create new node with 20, set new node's next to head, set head to new node

D. Create new node with 20, traverse to last node, set last node's next to new node

Solution

1. Step 1: Create new node with value 20

   Use constructor to create new node with data 20 and next as null.

2. Step 2: Traverse to last node

   Start from head, move through nodes until node.next is null (node with 15).

3. Step 3: Link new node at end

   Set last node's next pointer to new node, extending list to 5 -> 10 -> 15 -> 20 -> null.

4. Final Answer:

   Create new node with 20, traverse to last node, set last node's next to new node -> Option D

5. Quick Check:

   Insert at end = link new node after last node [OK]

Hint: Traverse to last node, then link new node's next as null [OK]

Common Mistakes:

• Setting head to new node incorrectly
• Not linking new node to list
• Inserting at beginning instead of end