Insert at Beginning of Doubly Linked List in DSA Java

Mental Model

Add a new node at the start by linking it before the current first node and updating the head pointer.

Analogy: Imagine adding a new book at the front of a shelf where each book is connected to the next and previous one. You place the new book first and connect it to the old first book.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 0 at beginning

Goal: Add a new node with value 0 at the start of the doubly linked list

Step 1: Create new node with value 0

newNode(0) null ← 1 ↔ 2 ↔ 3 -> null
↑head

Why: We need a new node to insert at the beginning

Step 2: Set newNode.next to current head (node 1)

newNode(0) -> 1 ↔ 2 ↔ 3 -> null
↑head

Why: Link new node forward to old first node

Step 3: Set current head.prev to newNode

newNode(0) ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: Link old first node back to new node

Step 4: Update head pointer to newNode

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: New node is now the first node in the list

Result:

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Annotated Code

DSA Java

class DoublyLinkedList {
    static class Node {
        int data;
        Node prev, next;
        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    Node head;

    // Insert at beginning
    void insertAtBeginning(int data) {
        Node newNode = new Node(data); // create new node
        if (head == null) {
            head = newNode; // empty list, new node is head
            return;
        }
        newNode.next = head; // link new node forward to old head
        head.prev = newNode; // link old head back to new node
        head = newNode; // update head to new node
    }

    // Print list forward
    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) System.out.print(" ↔ ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        // Create initial list 1 ↔ 2 ↔ 3
        dll.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        dll.head.next = second;
        second.prev = dll.head;
        second.next = third;
        third.prev = second;

        System.out.print("Before insertion: ");
        dll.printList();

        dll.insertAtBeginning(0); // insert 0 at beginning

        System.out.print("After insertion: ");
        dll.printList();
    }
}

Node newNode = new Node(data); // create new node

create new node with given data

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

handle empty list by making new node the head

newNode.next = head; // link new node forward to old head

point new node's next to current head

head.prev = newNode; // link old head back to new node

point old head's prev to new node

head = newNode; // update head to new node

update head pointer to new node

Output

Before insertion: 1 ↔ 2 ↔ 3 -> null

After insertion: 0 ↔ 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(1) because insertion at beginning only changes a few pointers without traversal

Space: O(1) because no extra space is used except the new node

vs Alternative: Compared to inserting at the end which requires traversal O(n), this is faster and simpler

Edge Cases

empty list

new node becomes the head with no next or prev

DSA Java

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

single element list

new node links before the single node, updating pointers correctly

DSA Java

newNode.next = head; // link new node forward to old head

When to Use This Pattern

When you need to add an element quickly at the start of a doubly linked list, use insert at beginning to avoid traversal and keep pointers consistent.

Common Mistakes

Mistake: Forgetting to update the old head's prev pointer to the new node
Fix: Always set head.prev = newNode after linking newNode.next = head

Mistake: Not updating the head pointer to the new node
Fix: Set head = newNode at the end to make new node the first element

Summary

Adds a new node at the start of a doubly linked list by adjusting pointers.

Use when you want to quickly insert an element at the front without traversing the list.

The key is linking the new node before the current head and updating the head pointer.

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