Insert at Beginning Head Insert in DSA Go - Execution Trace

Concept Flow - Insert at Beginning Head Insert

Create new node

↓

New node.next = head

↓

head = new node

↓

Done: new node is new head

Insert a new node by making it point to the current head, then update head to this new node.

Execution Sample

DSA Go

func InsertAtBeginning(head *Node, val int) *Node {
    newNode := &Node{data: val}
    newNode.next = head
    head = newNode
    return head
}

This code inserts a new node with value val at the start of the linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list 10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null	head points to node with 10	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head
2	Create new node with data 5	10 -> 20 -> 30 -> null	newNode created with data 5, next = null	newNode: ┌────────┐ │ data:5 │ │ next:∅ │ └────────┘
3	Set newNode.next = head	10 -> 20 -> 30 -> null	newNode.next points to node with 10	newNode: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │──→ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘
4	Update head = newNode	5 -> 10 -> 20 -> 30 -> null	head points to newNode with data 5	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │──→ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
5	Return new head	5 -> 10 -> 20 -> 30 -> null	head unchanged	Final list: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │──→ │ data:10│──→ │ data:20│──→ │ data:30│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head

💡 Insertion complete, new node is now the head of the list.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
head	points to node 10	points to node 10	points to node 10	points to newNode (5)	points to newNode (5)
newNode	nil	points to node 5 (next=null)	points to node 5 (next=10)	points to node 5 (next=10)	points to node 5 (next=10)
List Nodes	10 -> 20 -> 30 -> null	10 -> 20 -> 30 -> null	5 -> 10 -> 20 -> 30 -> null (newNode linked)	5 -> 10 -> 20 -> 30 -> null	5 -> 10 -> 20 -> 30 -> null

Key Moments - 3 Insights

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

Because we want the new node to point to the old first node before head changes. See execution_table step 3 where newNode.next points to node 10, preserving the list.

What happens if the original list is empty (head is null)?

The new node's next will be null, and head will point to the new node. This is the same process as steps 2-4, but head starts as null.

Why does head change only after setting newNode.next?

Changing head first would lose the reference to the old list. Step 4 updates head after newNode.next is set to keep the list connected.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does newNode.next point to?

A Node with data 10

B Node with data 5

C Null

D Node with data 20

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3 in execution_table.

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

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Pointer Changes' column to see when head changes in execution_table.

If the original list was empty, what would newNode.next be after insertion?

A Point to itself

B Null

C Point to old head node

D Point to node with data 10

💡 Hint

Refer to key_moments explanation about empty list scenario.

Concept Snapshot

Insert at Beginning (Head Insert):
- Create new node with data
- Set newNode.next = current head
- Update head = newNode
- New node becomes first element
- Works even if list is empty

Full Transcript

To insert a node at the beginning of a linked list, first create a new node with the desired data. Then, set the new node's next pointer to the current head of the list. Finally, update the head pointer to this new node. This makes the new node the first element. If the list was empty, the new node's next will be null. This process preserves the existing list by linking the new node to the old head before changing the head pointer.

Practice

1. What does the "Insert at Beginning" operation do in a singly linked list?

easy

A. Adds a new node at the end of the list

B. Searches for a node at the beginning

C. Deletes the first node of the list

D. Adds a new node at the start of the list, making it the new head

Solution

1. Step 1: Understand the head pointer role

   The head pointer points to the first node in the list.

2. Step 2: Insert at beginning changes head

   Inserting at beginning means creating a new node and making it the new head, linking it to the old head.

3. Final Answer:

   Adds a new node at the start of the list, making it the new head -> Option D

4. Quick Check:

   Insert at beginning = new head node [OK]

Hint: New node becomes head, old head moves next [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes
• Assuming it searches nodes

2. Which of the following Go code snippets correctly inserts a new node with value 10 at the beginning of a singly linked list?

easy

A. newNode := &Node{data: 10, next: head}
head = newNode

B. head.next = &Node{data: 10}
head = head.next

C. newNode := &Node{data: 10}
head.next = newNode

D. head = &Node{data: 10}
head.next = nil

Solution

1. Step 1: Create new node pointing to current head

   newNode is created with data 10 and next pointing to current head.

2. Step 2: Update head to new node

   Assign head to newNode so it becomes the first node.

3. Final Answer:

   newNode := &Node{data: 10, next: head}\nhead = newNode -> Option A

4. Quick Check:

   New node points to old head, head updated [OK]

Hint: New node's next = old head; head = new node [OK]

Common Mistakes:

• Not linking new node to old head
• Changing head.next instead of head
• Forgetting to update head pointer

3. What will be the output linked list after executing this Go code snippet?

package main
import "fmt"

type Node struct {
  data int
  next *Node
}

func main() {
  head := &Node{data: 5, next: nil}
  newNode := &Node{data: 3, next: head}
  head = newNode
  newNode2 := &Node{data: 1, next: head}
  head = newNode2

  // Print list
  current := head
  for current != nil {
    fmt.Print(current.data, " -> ")
    current = current.next
  }
  fmt.Print("null")
}

medium

A. 1 -> 3 -> 5 -> null

B. 5 -> 3 -> 1 -> null

C. 3 -> 1 -> 5 -> null

D. null

Solution

1. Step 1: Insert 3 at beginning

   New node with 3 points to 5, head updated to 3.

2. Step 2: Insert 1 at beginning

   New node with 1 points to 3, head updated to 1.

3. Step 3: Print list from head

   Traverse from head: 1 -> 3 -> 5 -> null.

4. Final Answer:

   1 -> 3 -> 5 -> null -> Option A

5. Quick Check:

   Head insert order reversed list [OK]

Hint: New nodes become head, so list order reverses insert order [OK]

Common Mistakes:

• Printing in insertion order instead of head order
• Confusing next pointers
• Not updating head after insert

4. Identify the error in this Go code that tries to insert a new node with value 7 at the beginning of a linked list:

type Node struct {
  data int
  next *Node
}

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

medium

A. The function should not return head

B. head should not be reassigned inside the function

C. newNode.next should point to head, not head.next

D. newNode is not initialized correctly

Solution

1. Step 1: Check newNode.next assignment

   It incorrectly points to head.next instead of head, skipping the current head node.

2. Step 2: Correct pointer to head

   newNode.next must point to head to insert before it.

3. Final Answer:

   newNode.next should point to head, not head.next -> Option C

4. Quick Check:

   Link new node to head, not head.next [OK]

Hint: New node's next = head, not head.next [OK]

Common Mistakes:

• Linking new node to head.next skipping head
• Not updating head pointer correctly
• Ignoring return value of updated head

5. Given a singly linked list with nodes containing integer values, write a Go function to insert multiple values at the beginning in order, so the final list reflects the insertion order. Which approach correctly achieves this?

hard

A. Insert each new value at the end one by one.

B. Insert each new value at the beginning but reverse the input slice before inserting.

C. Insert each new value at the beginning one by one.

D. Insert each new value at the end but reverse the input slice before inserting.

Solution

1. Step 1: Understand insertion order at beginning

   Inserting at beginning reverses order because new nodes become head.

2. Step 2: Reverse input slice before inserting

   Reversing input before inserting at beginning restores original order in final list.

3. Final Answer:

   Insert each new value at the beginning but reverse the input slice before inserting. -> Option B

4. Quick Check:

   Reverse input + head insert = original order [OK]

Hint: Reverse input before head inserts to keep order [OK]

Common Mistakes:

• Inserting at beginning without reversing input
• Inserting at end without reversing input
• Confusing insert at beginning with insert at end