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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting 10 at the beginning?

Consider a doubly linked list initially containing 20 -> 30 -> 40 -> null. We insert 10 at the beginning. 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 insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) head.prev = newNode;
        head = 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) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.head = new Node(20);
        Node second = new Node(30);
        Node third = new Node(40);
        dll.head.next = second;
        second.prev = dll.head;
        second.next = third;
        third.prev = second;

        dll.insertAtBeginning(10);
        dll.printList();
    }
}

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

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

C 10 -> 30 -> 40 -> null

D 10 -> 20 -> 30 -> 40 -> null

💡 Hint

Remember to update the previous pointer of the old head node.

Inserting at the beginning means the new node becomes the head. The new node's next points to the old head, and the old head's prev points back to the new node.

❓ Predict Output

intermediate

What is the output after inserting 5 at the beginning of an empty list?

We start with an empty doubly linked list. We insert 5 at the beginning. 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 insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) head.prev = newNode;
        head = 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) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtBeginning(5);
        dll.printList();
    }
}

A 0 -> 5 -> null

B 5 -> null

C 5 -> 5 -> null

D null

💡 Hint

Inserting into an empty list sets the new node as head with no next or prev.

Since the list is empty, the new node becomes the head and points to null next and prev.

🔧 Debug

advanced

Why does this insertion code cause a NullPointerException?

Given the code below, inserting at the beginning sometimes causes a NullPointerException. Identify the cause.

DSA Java

void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head.next;
    if (head != null) head.prev = newNode;
    head = newNode;
}

A Because head is assigned after setting newNode.next, causing head to be null

B Because head.prev is set before checking if head is null

C Because newNode.next is set to head.next instead of head, causing wrong linkage

D Because newNode.prev is not set to null explicitly

💡 Hint

Check what newNode.next should point to when inserting at beginning.

The new node's next should point to the current head, not head.next. Setting newNode.next = head.next skips the head node and can cause null pointer errors.

🧠 Conceptual

advanced

What pointers must be updated when inserting at the beginning of a doubly linked list?

When inserting a new node at the beginning of a doubly linked list, which pointers must be updated to maintain list integrity?

A New node's next, old head's prev, and head pointer

B New node's prev, old head's next, and tail pointer

C Only new node's next and head pointer

D Old head's prev and tail pointer only

💡 Hint

Think about how the new node connects to the old head and how the head pointer changes.

The new node's next points to the old head, the old head's prev points back to the new node, and the head pointer is updated to the new node.

❓ Predict Output

expert

What is the output after multiple insertions at beginning?

Starting with an empty doubly linked list, we insert 3, then 2, then 1 at the beginning. 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 insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null) head.prev = newNode;
        head = 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) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtBeginning(3);
        dll.insertAtBeginning(2);
        dll.insertAtBeginning(1);
        dll.printList();
    }
}

A 1 -> 2 -> 3 -> null

B 1 -> 3 -> 2 -> null

C 3 -> 1 -> 2 -> null

D 3 -> 2 -> 1 -> null

💡 Hint

Each new insertion at beginning becomes the new head.

Inserting 3 first makes list: 3 -> null. Then inserting 2 at beginning: 2 -> 3 -> null. Then inserting 1 at beginning: 1 -> 2 -> 3 -> null.

Practice

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

easy

A. To add a new node after the tail node

B. To reverse the entire list

C. To delete the first node of the list

D. To add a new node before the current head node

Solution

1. Step 1: Understand the position of insertion

   Inserting at the beginning means placing the new node before the current head node.

2. Step 2: Identify the effect on the list

   The new node becomes the new head, and its next pointer points to the old head.

3. Final Answer:

   To add a new node before the current head node -> Option D

4. Quick Check:

   Insert at beginning = add before head [OK]

Hint: Beginning insertion means new node becomes the head [OK]

Common Mistakes:

• Confusing beginning with end insertion
• Thinking insertion deletes nodes
• Mixing up singly and doubly linked list behavior

2. Which of the following is the correct syntax to create a new node in Java for a doubly linked list?

easy

A. Node newNode = Node(data); newNode.prev = null; newNode.next = null;

B. Node newNode = new Node(data); newNode.prev = null; newNode.next = null;

C. Node newNode = new Node(); newNode.data = data; newNode.prev = null; newNode.next = null;

D. Node newNode = new Node(data); newNode.prev = data; newNode.next = data;

Solution

1. Step 1: Understand Java object creation syntax

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

2. Step 2: Check node initialization

   The node's previous and next pointers should be set to null initially.

3. Final Answer:

   Node newNode = new Node(data); newNode.prev = null; newNode.next = null; -> Option B

4. Quick Check:

   Java new object = new Constructor() [OK]

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

Common Mistakes:

• Omitting 'new' keyword
• Assigning data to prev or next pointers
• Using incorrect constructor syntax

3. What will be the output of the doubly linked list after inserting 10 at the beginning of the list containing nodes 20 <-> 30?

medium

A. 10 <-> 20 <-> 30

B. 20 <-> 30 <-> 10

C. 30 <-> 20 <-> 10

D. 10 <-> 30 <-> 20

Solution

1. Step 1: Identify current list order

   The list currently is 20 <-> 30, with 20 as head and 30 as tail.

2. Step 2: Insert 10 at beginning

   New node 10 becomes head, its next points to 20, and 20's prev points to 10.

3. Final Answer:

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

4. Quick Check:

   Insert at beginning adds node before head [OK]

Hint: New node at start shifts old head right [OK]

Common Mistakes:

• Appending instead of prepending
• Not updating previous pointer of old head
• Reversing node order incorrectly

4. Given the following code snippet for inserting at the beginning of a doubly linked list, what is the error?

void insertAtBeginning(int data) {
  Node newNode = new Node(data);
  newNode.next = head;
  head.prev = newNode;
  head = newNode;
}

medium

A. No error, code works correctly

B. head should be updated before setting newNode.next

C. head.prev = newNode; causes NullPointerException if list is empty

D. newNode.next should be null

Solution

1. Step 1: Analyze code for empty list case

   If the list is empty, head is null, so head.prev causes NullPointerException.

2. Step 2: Identify fix

   Check if head is not null before setting head.prev = newNode.

3. Final Answer:

   head.prev = newNode; causes NullPointerException if list is empty -> Option C

4. Quick Check:

   Null head means head.prev causes error [OK]

Hint: Check for null head before accessing head.prev [OK]

Common Mistakes:

• Ignoring empty list case
• Assuming head is never null
• Misordering pointer updates

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25. You want to insert a new node with value 1 at the beginning and then reverse the list. What will be the final list after these operations?

hard

A. 25 <-> 15 <-> 5 <-> 1

B. 1 <-> 5 <-> 15 <-> 25

C. 1 <-> 25 <-> 15 <-> 5

D. 5 <-> 15 <-> 25 <-> 1

Solution

1. Step 1: Insert 1 at beginning

   List becomes 1 <-> 5 <-> 15 <-> 25 after insertion.

2. Step 2: Reverse the list

   Reversing swaps head and tail, so list becomes 25 <-> 15 <-> 5 <-> 1.

3. Final Answer:

   25 <-> 15 <-> 5 <-> 1 -> Option A

4. Quick Check:

   Insert at start then reverse flips order [OK]

Hint: Insert first, then reverse flips entire list [OK]

Common Mistakes:

• Reversing before insertion
• Not updating prev pointers when reversing
• Confusing node order after reverse