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

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Is list empty?

↓

Set head = new

↓

Set head.prev = new

↓

Set head = new

↓

Done

Start by creating a new node. If the list is empty, set head to new node. Otherwise, link new node before current head and update head pointer.

Execution Sample

DSA Javascript

function insertAtBeginning(head, data) {
  const newNode = { data, prev: null, next: head };
  if (head) head.prev = newNode;
  return newNode;
}

This code inserts a new node at the start of a doubly linked list and returns the new head.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	∅	newNode: data=10, prev=null, next=null	No nodes yet
2	Check if list is empty	∅	head=null (empty list)	List is empty
3	Set head = newNode	10	head → newNode	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘ head
4	Insert another node with data=20 at beginning	10	Create newNode2: data=20, prev=null, next=head(10)	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ prev:∅ │ │ prev: ?│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ newNode2 head
5	Set head.prev = newNode2	10	head(10).prev → newNode2(20)	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ newNode2 head
6	Update head = newNode2	20 → 10	head → newNode2(20)	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
7	Insert node with data=30 at beginning	20 → 10	Create newNode3: data=30, prev=null, next=head(20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev: ?│ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘
8	Set head.prev = newNode3	20 → 10	head(20).prev → newNode3(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘
9	Update head = newNode3	30 → 20 → 10	head → newNode3(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │ │ prev:──┼──→ │ prev:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
10	End of insertions	30 → 20 → 10	No pointer changes	Final list: 30 ⇄ 20 ⇄ 10

💡 No more insertions, operation complete

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	Final
head	null	node(10)	node(20)	node(30)	node(30)
newNode	null	node(10)	node(20)	node(30)	node(30)
list size	0	0	1	2	3

Key Moments - 3 Insights

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

Because newNode must point to the current first node before head changes, as shown in steps 4 and 7 in the execution_table.

Why do we update head.prev to newNode?

To maintain the backward link in the doubly linked list, so the old head knows its previous node is the new node (see steps 5 and 8).

What happens if the list is empty when inserting?

We simply set head to the new node with prev and next as null, as in steps 1-3.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what does head point to?

A Node with data 10

B Node with data 20

C Node with data 30

D Null

💡 Hint

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

At which step does the list first have two nodes?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Look at the 'Nodes in List' column to see when count changes from 1 to 2.

If we skip setting head.prev = newNode, what breaks in the list?

A Head pointer will be null

B Forward links will be broken

C Backward links will be broken

D List size will be incorrect

💡 Hint

Refer to steps 5 and 8 where head.prev is set to maintain backward links.

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node with data
- Set newNode.next = current head
- If head exists, set head.prev = newNode
- Update head to newNode
- Handles empty list by setting head directly
- Maintains forward and backward links

Full Transcript

To insert at the beginning of a doubly linked list, first create a new node with the given data. If the list is empty, set the head pointer to this new node. If not empty, link the new node's next pointer to the current head, then update the current head's prev pointer to the new node. Finally, update the head pointer to the new node. This keeps the list connected in both directions. The execution table shows each step with pointer changes and the visual state of the list. Key moments clarify why we set pointers in this order and what happens when the list is empty.

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 before the current head node

B. To add a new node after the tail node

C. To remove the first node from the list

D. To reverse the entire list

Solution

1. Step 1: Understand the head node position

   The head node is the first node in the doubly linked list.

2. Step 2: Insert new node before head

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

3. Final Answer:

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

4. Quick Check:

   Insert at beginning = add before head [OK]

Hint: New node becomes new head in doubly linked list [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Thinking insertion removes nodes
• Mixing up head and tail nodes

2. Which of the following is the correct way to update the previous pointer of the old head node when inserting a new node at the beginning in JavaScript?

easy

A. oldHead.prev = newNode;

B. newNode.next = oldHead.prev;

C. newNode.prev = oldHead;

D. oldHead.next = newNode;

Solution

1. Step 1: Identify the old head's previous pointer

   The old head's previous pointer should point to the new node after insertion.

2. Step 2: Update old head's prev to new node

   Setting oldHead.prev = newNode links the old head back to the new node.

3. Final Answer:

   oldHead.prev = newNode; -> Option A

4. Quick Check:

   Old head prev points to new node [OK]

Hint: Old head's prev points to new node after insertion [OK]

Common Mistakes:

• Setting oldHead.next instead of prev
• Confusing newNode's pointers
• Assigning newNode.next incorrectly

3. What will be the printed state of the doubly linked list after inserting a node with value 10 at the beginning of the list 5 <-> 15 <-> 20?

medium

A. 5 <-> 15 <-> 20 <-> 10

B. 10 <-> 15 <-> 20 <-> 5

C. 10 <-> 5 <-> 15 <-> 20

D. 5 <-> 10 <-> 15 <-> 20

Solution

1. Step 1: Insert 10 before current head (5)

   The new node with value 10 becomes the new head, pointing next to 5.

2. Step 2: Link the rest of the list after 5

   The list continues as 5 <-> 15 <-> 20 unchanged after insertion.

3. Final Answer:

   10 <-> 5 <-> 15 <-> 20 -> Option C

4. Quick Check:

   New head 10 followed by old list [OK]

Hint: New node appears first, old list follows [OK]

Common Mistakes:

• Appending new node at end instead of beginning
• Swapping nodes incorrectly
• Ignoring pointer updates

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

function insertAtBeginning(head, data) {
  const newNode = { data: data, prev: null, next: head };
  head.prev = newNode;
  head = newNode;
  return head;
}

medium

A. It incorrectly sets newNode.next to null

B. It does not handle empty list when head is null

C. It forgets to update newNode.prev to head

D. It returns the old head instead of new head

Solution

1. Step 1: Check for empty list case

   If head is null, head.prev causes error because head is null.

2. Step 2: Missing null check before setting head.prev

   Code should check if head exists before setting head.prev = newNode.

3. Final Answer:

   It does not handle empty list when head is null -> Option B

4. Quick Check:

   Null head requires special handling [OK]

Hint: Always check if head is null before accessing its properties [OK]

Common Mistakes:

• Ignoring empty list case
• Assuming head is never null
• Not returning updated head

5. You have a doubly linked list with nodes: 7 <-> 14 <-> 21. You want to insert a new node with value 3 at the beginning. After insertion, what will be the correct sequence of node values when traversing from head to tail and tail to head?

hard

A. Head to tail: 21 <-> 14 <-> 7 <-> 3; Tail to head: 3 <-> 7 <-> 14 <-> 21

B. Head to tail: 7 <-> 14 <-> 21 <-> 3; Tail to head: 3 <-> 21 <-> 14 <-> 7

C. Head to tail: 3 <-> 7 <-> 14 <-> 21; Tail to head: 3 <-> 7 <-> 14 <-> 21

D. Head to tail: 3 <-> 7 <-> 14 <-> 21; Tail to head: 21 <-> 14 <-> 7 <-> 3

Solution

1. Step 1: Insert 3 before current head 7

   The new node 3 becomes the head, pointing next to 7.

2. Step 2: Traverse forward and backward

   Forward traversal: 3 -> 7 -> 14 -> 21; backward traversal reverses this order.

3. Final Answer:

   Head to tail: 3 <-> 7 <-> 14 <-> 21; Tail to head: 21 <-> 14 <-> 7 <-> 3 -> Option D

4. Quick Check:

   New head first, tail last, pointers reversed backward [OK]

Hint: Head to tail is forward order; tail to head is reverse [OK]

Common Mistakes:

• Mixing forward and backward traversal order
• Appending new node at tail instead of head
• Incorrect pointer updates causing wrong traversal