Insert at End of Doubly Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting 5 at the end?

Consider a doubly linked list initially containing nodes with values 1, 2, 3. We insert a new node with value 5 at the end. What is the printed list after this operation?

DSA Java

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

class DoublyLinkedList {
    Node head;

    void insertAtEnd(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;
        newNode.prev = temp;
    }

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

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtEnd(1);
        dll.insertAtEnd(2);
        dll.insertAtEnd(3);
        dll.insertAtEnd(5);
        dll.printList();
    }
}

A 1 -> 2 -> 3 -> 5

B 1 -> 2 -> 3 -> 5 -> null

C 1 -> 2 -> 3 -> null

D 5 -> 1 -> 2 -> 3 -> null

💡 Hint

Remember, inserting at the end means the new node comes after the last node.

The insertAtEnd method traverses to the last node and links the new node after it. So the list becomes 1 -> 2 -> 3 -> 5 -> null.

❓ Predict Output

intermediate

What is the output after inserting into an empty list?

We start with an empty doubly linked list and insert a node with value 10 at the end. What is the printed list?

DSA Java

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

class DoublyLinkedList {
    Node head;

    void insertAtEnd(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;
        newNode.prev = temp;
    }

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

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtEnd(10);
        dll.printList();
    }
}

A null -> 10

B null

C 10

D 10 -> null

💡 Hint

When the list is empty, the new node becomes the head.

Since the list is empty, the new node with value 10 becomes the head and the only node. The print shows 10 -> null.

🔧 Debug

advanced

Why does this insertAtEnd method cause a NullPointerException?

This insertAtEnd method sometimes throws a NullPointerException. Identify the cause.

DSA Java

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

A newNode is not initialized properly

B temp.next is always null, so loop never runs

C head is null, so temp is null and temp.next causes NullPointerException

D newNode.prev is assigned incorrectly

💡 Hint

What happens if the list is empty and head is null?

If head is null, temp is null. Accessing temp.next causes NullPointerException. The method must handle empty list case.

🧠 Conceptual

advanced

What is the time complexity of inserting at the end in a doubly linked list without a tail pointer?

If a doubly linked list does not maintain a tail pointer, what is the time complexity of inserting a new node at the end?

A O(n), because we must traverse from head to the last node

B O(1), because insertion is always at the end

C O(log n), because of binary search on nodes

D O(n^2), because of nested loops

💡 Hint

Without a tail pointer, how do you find the last node?

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

❓ Predict Output

expert

What is the output after multiple insertions at the end?

Given the following code inserting 4, 7, 9 at the end of an initially empty doubly linked list, what is the printed list?

DSA Java

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

class DoublyLinkedList {
    Node head;

    void insertAtEnd(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;
        newNode.prev = temp;
    }

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

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtEnd(4);
        dll.insertAtEnd(7);
        dll.insertAtEnd(9);
        dll.printList();
    }
}

A 4 -> 7 -> 9 -> null

B 4 -> 7 -> null

C 9 -> 7 -> 4 -> null

D null

💡 Hint

Nodes are inserted at the end, so order is preserved.

Nodes 4, 7, 9 are inserted one after another at the end, so the list prints 4 -> 7 -> 9 -> null.

Practice

1. What is the main purpose of inserting a node at the end of a doubly linked list?

easy

A. To reverse the list

B. To remove the first node

C. To add a new element after the last node

D. To find the middle node

Solution

1. Step 1: Understand the structure of a doubly linked list

   A doubly linked list has nodes connected both forward and backward, allowing traversal in both directions.

2. Step 2: Purpose of insertion at the end

   Inserting at the end means adding a new node after the current last node, updating pointers accordingly.

3. Final Answer:

   To add a new element after the last node -> Option C

4. Quick Check:

   Insert at end = Add after last node [OK]

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

Common Mistakes:

• Confusing insertion at end with deletion
• Thinking insertion at end reverses the list
• Assuming insertion at end finds middle node

2. Which of the following is the correct way to update the 'next' pointer of the last node when inserting a new node at the end in Java?

easy

A. last.next = newNode;

B. newNode.next = last;

C. last.prev = newNode;

D. newNode.prev = null;

Solution

1. Step 1: Identify the last node's next pointer

   The last node's 'next' pointer should point to the new node being inserted.

2. Step 2: Correct assignment for insertion

   Assigning 'last.next = newNode;' correctly links the last node to the new node.

3. Final Answer:

   last.next = newNode; -> Option A

4. Quick Check:

   Last node's next points to new node [OK]

Hint: Last node's next must point to new node [OK]

Common Mistakes:

• Assigning newNode.next to last instead of last.next to newNode
• Changing last.prev instead of last.next
• Setting newNode.prev to null incorrectly

3. What will be the output of the following code snippet after inserting 40 at the end of the doubly linked list?

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

class DoublyLinkedList {
  Node head;
  void insertEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node last = head;
    while (last.next != null) last = last.next;
    last.next = newNode;
    newNode.prev = last;
  }
  void printList() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " <-> ");
      temp = temp.next;
    }
    System.out.println("null");
  }
}

public class Main {
  public static void main(String[] args) {
    DoublyLinkedList dll = new DoublyLinkedList();
    dll.insertEnd(10);
    dll.insertEnd(20);
    dll.insertEnd(30);
    dll.insertEnd(40);
    dll.printList();
  }
}

medium

A. 10 <-> 20 <-> 30 <-> 40 <-> null

B. 40 <-> 10 <-> 20 <-> 30 <-> null

C. 10 <-> 20 <-> 30 <-> null

D. null

Solution

1. Step 1: Trace insertions in order

   Nodes 10, 20, 30, then 40 are inserted at the end, so list grows as 10 <-> 20 <-> 30 <-> 40.

2. Step 2: Print list traversal

   Print starts at head (10) and moves forward printing each node's data followed by ' <-> ', ending with 'null'.

3. Final Answer:

   10 <-> 20 <-> 30 <-> 40 <-> null -> Option A

4. Quick Check:

   Insertion at end appends nodes in order [OK]

Hint: Insertion order matches printed list [OK]

Common Mistakes:

• Assuming new node is added at start
• Forgetting to update newNode.prev
• Printing list incorrectly or missing null

4. Identify the error in the following insertEnd method for a doubly linked list:

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

medium

A. last.next should be set to head

B. The while loop condition should be last.prev != null

C. head should be updated to newNode when list is empty

D. newNode.next should be set to null, not last

Solution

1. Step 1: Analyze pointer assignments after loop

   After finding last node, last.next is set to newNode correctly, but newNode.next is wrongly set to last (previous node).

2. Step 2: Correct pointer for newNode.next

   Since newNode is last, its next should be null, and newNode.prev should point to last.

3. Final Answer:

   newNode.next should be set to null, not last -> Option D

4. Quick Check:

   Last node's next = newNode; newNode.next = null [OK]

Hint: Last node's next points newNode; newNode.next is null [OK]

Common Mistakes:

• Setting newNode.next to last instead of null
• Not updating newNode.prev to last
• Incorrect loop condition in while

5. Given a doubly linked list with nodes 5 <-> 15 <-> 25, write the sequence of pointer updates needed to insert a new node with value 35 at the end. Which of the following correctly describes the steps?

hard

A. Set newNode.prev and newNode.next to null, head to newNode

B. Set newNode.prev to last node, last.next to newNode, newNode.next to null

C. Set newNode.next to last node, last.prev to newNode, newNode.prev to null

D. Set last.next to null, newNode.prev to null, newNode.next to last

Solution

1. Step 1: Identify last node and new node pointers

   The last node is 25; newNode is 35. For insertion at end, newNode.prev must point to last node, and last.next must point to newNode.

2. Step 2: Set newNode.next to null

   Since newNode is now last, its next pointer must be null to mark list end.

3. Final Answer:

   Set newNode.prev to last node, last.next to newNode, newNode.next to null -> Option B

4. Quick Check:

   Insert at end updates prev and next pointers correctly [OK]

Hint: New node prev = last; last next = new node; new node next = null [OK]

Common Mistakes:

• Swapping prev and next pointers incorrectly
• Not setting newNode.next to null
• Changing head pointer unnecessarily