Insert at Beginning of Doubly Linked List in DSA Java - Execution Trace

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Set new_node.next = head

↓

If head != null

↓

Set head.prev = new_node

↓

Set head = new_node

↓

Done

The new node is created and linked before the current head. If the list is not empty, the old head's previous pointer is updated. Finally, head points to the new node.

Execution Sample

DSA Java

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

// Insert new node at beginning
void insertAtBeginning(int data) {
  Node new_node = new Node(data);
  new_node.next = head;
  if (head != null) {
    head.prev = new_node;
  }
  head = new_node;
}

This code creates a new node and inserts it at the start of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=5	∅	new_node: data=5, prev=∅, next=∅	List is empty
2	Set new_node.next = head (head is ∅)	∅	new_node.next = ∅	new_node (5) → ∅
3	Check if head != null (head is ∅)	∅	No change	No prev pointer update needed
4	Set head = new_node	5	head → new_node (5)	┌────────┐ │ data:5 │ │ prev:∅ │ │ next:∅ │ └────────┘ head
5	Insert another node with data=10	5	Create new_node: data=10, prev=∅, next=∅	List before insertion: ┌────────┐ │ data:5 │ │ prev:∅ │ │ next:∅ │ └────────┘ head
6	Set new_node.next = head (node 5)	5	new_node.next → node 5	new_node (10) → node (5)
7	Since head != null, set head.prev = new_node	5	node 5.prev → new_node (10)	node (5) prev → new_node (10)
8	Set head = new_node (10)	10 → 5	head → new_node (10)	┌────────┐ ┌────────┐ │ data:10│ │ data:5 │ │ prev:∅ │←── │ prev:10│ │ next:5 │──→ │ next:∅ │ └────────┘ └────────┘ head
9	Insert another node with data=15	10 → 5	Create new_node: data=15, prev=∅, next=∅	List before insertion: ┌────────┐ ┌────────┐ │ data:10│ │ data:5 │ │ prev:∅ │←── │ prev:10│ │ next:5 │──→ │ next:∅ │ └────────┘ └────────┘ head
10	Set new_node.next = head (node 10)	10 → 5	new_node.next → node 10	new_node (15) → node (10)
11	Since head != null, set head.prev = new_node	10 → 5	node 10.prev → new_node (15)	node (10) prev → new_node (15)
12	Set head = new_node (15)	15 → 10 → 5	head → new_node (15)	┌────────┐ ┌────────┐ ┌────────┐ │ data:15│ │ data:10│ │ data:5 │ │ prev:∅ │←── │ prev:15│←── │ prev:10│ │ next:10│──→ │ next:5 │──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
13	End of insertions	15 → 10 → 5	No change	Final list state

💡 No more insertions, list head points to newest node 15

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	Final
head	∅	∅	Node(5)	Node(10)	Node(15)
new_node	∅	Node(5)	Node(10)	Node(15)	Node(15)
list size	0	0	1	2	3

Key Moments - 3 Insights

Why do we set new_node.next = head before changing head?

Because new_node must point to the old first node before head is updated, as shown in execution_table step 6 and 10.

Why do we update head.prev to new_node only if head is not null?

If head is null, the list is empty and no previous node exists to update. This is shown in step 3 where no update happens.

How does the prev pointer help in a doubly linked list?

It allows backward traversal and proper linking when inserting at the beginning, as seen in steps 7 and 11 where head.prev is updated.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what does the head pointer reference?

A Node with data 5

B Null

C Node with data 10

D Node with data 15

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 8.

At which step does the list first have two nodes linked?

A Step 4

B Step 8

C Step 6

D Step 12

💡 Hint

Look for when head points to new_node and new_node.next points to old head.

If the list was initially empty, which step shows the first node insertion?

A Step 4

B Step 1

C Step 5

D Step 9

💡 Hint

Check when head changes from null to a node for the first time.

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node
- Set new_node.next = head
- If head not null, set head.prev = new_node
- Update head = new_node
- List grows at front, prev and next pointers updated accordingly

Full Transcript

To insert a node at the beginning of a doubly linked list, first create the new node. Then set its next pointer to the current head. If the list is not empty, update the old head's prev pointer to the new node. Finally, update the head pointer to the new node. This process ensures the list is correctly linked in both directions. The execution table shows step-by-step how nodes and pointers change, starting from an empty list and adding nodes with data 5, 10, and 15 at the beginning. The variable tracker follows the head pointer and list size changes. Key moments clarify why pointer updates happen in a specific order. The visual quiz tests understanding of pointer references and list state at different steps.

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