Insert at Beginning of Doubly Linked List in DSA Go - 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 Go

func InsertAtBeginning(head *Node, data int) *Node {
    newNode := &Node{data: data}
    newNode.next = head
    if head != nil {
        head.prev = newNode
    }
    head = newNode
    return head
}

This function inserts a new node with given data 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=5	Empty	newNode created	∅ (empty list)
2	Set newNode.next = head (head is null)	Empty	newNode.next = ∅	newNode(data:5) next:∅ prev:∅
3	Check if head != null	Empty	head is ∅, skip head.prev update	newNode(data:5) next:∅ prev:∅
4	Set head = newNode	1 node	head → newNode(data:5)	┌───────────┐ │ data: 5 │ │ prev: ∅ │ │ next: ∅ │ └───────────┘ head
5	Return new head	1 node	head points to newNode	┌───────────┐ │ data: 5 │ │ prev: ∅ │ │ next: ∅ │ └───────────┘ head

💡 Insertion complete, new node is now head of list

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
head	∅	∅	∅	∅	newNode(data:5)	newNode(data:5)
newNode	∅	Node(data:5)	Node(data:5)	Node(data:5)	Node(data:5)	Node(data:5)

Key Moments - 3 Insights

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

Because we need the new node to point to the old head before head changes. See execution_table step 2 and 4 where newNode.next is set to old head (which is null here) before head points to newNode.

Why do we check if head != null before setting head.prev?

If the list is empty (head is null), there is no old head to update. Skipping prevents errors. See execution_table step 3 where head is null, so head.prev update is skipped.

What happens to the prev pointer of the new head?

It remains null because the new head has no previous node. This is shown in the visual state at step 4 where newNode.prev is ∅.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is newNode.next pointing to?

A null (∅)

B head node with data

C newNode itself

D previous node

💡 Hint

Refer to execution_table row 2 under Pointer Changes and Visual State

At which step does head start pointing to the new node?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check execution_table step 4 Pointer Changes and Visual State

If the list was not empty, what additional pointer change would happen?

A newNode.prev would point to old head

B head.prev would point to newNode

C newNode.next would be null

D head.next would point to newNode

💡 Hint

See execution_table step 3 explanation about head.prev update

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node
- Set newNode.next = current head
- If head exists, set head.prev = newNode
- Update head to newNode
- New node prev pointer is always null
- List size increases by 1

Full Transcript

This visual trace shows how to insert a new node at the beginning of a doubly linked list. First, a new node is created with the given data. Then, its next pointer is set to the current head of the list. If the list is not empty, the old head's previous pointer is updated to point back to the new node. Finally, the head pointer is updated to the new node, making it the first node in the list. The new node's previous pointer remains null because it is now the first node. The execution table tracks each step, showing pointer changes and the visual state of the list. Key moments clarify why pointer assignments happen in this order and why null checks are necessary. The quiz tests understanding of pointer assignments and list state changes during insertion.

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 delete the first node of 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 and updating pointers.

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: Beginning means before the head node [OK]

Common Mistakes:

• Confusing beginning with end insertion
• Thinking insertion deletes nodes
• Assuming insertion reverses list

2. Which of the following Go code snippets correctly updates the previous pointer of the old head node when inserting a new node at the beginning?

easy

A. newNode.prev = oldHead

B. oldHead.prev = newNode

C. newNode.next = oldHead.prev

D. oldHead.next = newNode

Solution

1. Step 1: Identify pointer to update

   When inserting at beginning, old head's previous pointer must point to new node.

2. Step 2: Correct assignment

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

3. Final Answer:

   oldHead.prev = newNode -> Option B

4. Quick Check:

   Old head prev points to new node [OK]

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

Common Mistakes:

• Assigning newNode.prev incorrectly
• Mixing next and prev pointers
• Updating oldHead.next instead of prev

3. Consider this Go code inserting nodes at the beginning of a doubly linked list:

type Node struct {
  data int
  prev *Node
  next *Node
}

func insertAtBeginning(head **Node, data int) {
  newNode := &Node{data: data}
  newNode.next = *head
  if *head != nil {
    (*head).prev = newNode
  }
  *head = newNode
}

func main() {
  var head *Node
  insertAtBeginning(&head, 10)
  insertAtBeginning(&head, 20)
  insertAtBeginning(&head, 30)
  // Print list from head
  curr := head
  for curr != nil {
    fmt.Print(curr.data, " -> ")
    curr = curr.next
  }
  fmt.Print("null")
}

What is the printed output?

medium

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

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

C. null

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Trace insertions order

   Nodes inserted in order: 10, then 20 at beginning, then 30 at beginning.

2. Step 2: List after insertions

   After all insertions, list is 30 (head) -> 20 -> 10 -> null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option D

4. Quick Check:

   Last inserted node is new head [OK]

Hint: Last inserted node becomes new head [OK]

Common Mistakes:

• Assuming insertion adds at end
• Confusing order of nodes
• Ignoring pointer updates

4. The following Go function attempts to insert a node at the beginning of a doubly linked list but causes a runtime panic:

func insertAtBeginning(head *Node, data int) {
  newNode := &Node{data: data}
  newNode.next = head
  head.prev = newNode
  head = newNode
}

What is the main error causing the panic?

medium

A. head is nil and head.prev causes nil pointer dereference

B. newNode.next is not assigned correctly

C. head = newNode does not update original head pointer

D. data field is not initialized

Solution

1. Step 1: Check nil pointer usage

   If head is nil, accessing head.prev causes runtime panic (nil pointer dereference).

2. Step 2: Identify cause of panic

   Function does not check if head is nil before head.prev = newNode, causing panic.

3. Final Answer:

   head is nil and head.prev causes nil pointer dereference -> Option A

4. Quick Check:

   Accessing prev on nil head causes panic [OK]

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

Common Mistakes:

• Ignoring nil check before pointer access
• Thinking assignment head = newNode updates caller
• Assuming data field causes panic

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

hard

A. 15 -> 10 -> 5 -> 3 -> null

B. 5 -> 10 -> 15 -> 3 -> null

C. 3 -> 5 -> 10 -> 15 -> null

D. 3 -> 15 -> 10 -> 5 -> null

Solution

1. Step 1: Understand insertion at beginning

   New node with value 3 is added before current head (5).

2. Step 2: Update pointers and traverse

   After insertion, list is 3 (head) -> 5 -> 10 -> 15 -> null.

3. Final Answer:

   3 -> 5 -> 10 -> 15 -> null -> Option C

4. Quick Check:

   New node becomes new head [OK]

Hint: New node becomes new head, old head shifts right [OK]

Common Mistakes:

• Inserting at end instead of beginning
• Reversing node order incorrectly
• Not updating head pointer