Insert at Beginning of Doubly Linked List in DSA Go

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 has a label pointing to the next and previous book. You place the new book first and update the labels accordingly.

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

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

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

Step 2: Set new node's next pointer to current head (node 1)

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

Why: New node should point forward to the old first node

Step 3: Set current head's previous pointer to new node

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

Why: Old first node must point back to new node

Step 4: Update head pointer to new node

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

Why: Head must now point to the new first node

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

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

type DoublyLinkedList struct {
	head *Node
}

func (dll *DoublyLinkedList) InsertAtBeginning(value int) {
	newNode := &Node{val: value}
	if dll.head == nil {
		dll.head = newNode
		return
	}
	newNode.next = dll.head // link new node forward to old head
	dll.head.prev = newNode // link old head back to new node
	dll.head = newNode      // update head to new node
}

func (dll *DoublyLinkedList) PrintList() {
	curr := dll.head
	for curr != nil {
		fmt.Printf("%d", curr.val)
		if curr.next != nil {
			fmt.Print(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println(" -> null")
}

func main() {
	dll := &DoublyLinkedList{}
	dll.InsertAtBeginning(3)
	dll.InsertAtBeginning(2)
	dll.InsertAtBeginning(1)
	fmt.Print("Before insertion: ")
	dll.PrintList()

	dll.InsertAtBeginning(0)
	fmt.Print("After insertion at beginning: ")
	dll.PrintList()
}

newNode := &Node{val: value}

create new node with given value

if dll.head == nil { dll.head = newNode return }

handle empty list by setting head to new node

newNode.next = dll.head

link new node forward to old head

dll.head.prev = newNode

link old head back to new node

dll.head = newNode

update head pointer to new node

Output

Before insertion: 1 ↔ 2 ↔ 3 -> null

After insertion at beginning: 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 only one new node is created regardless of list size

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 Go

if dll.head == nil {
	dll.head = newNode
	return
}

single element list

new node links to old head and old head links back to new node

DSA Go

newNode.next = dll.head

When to Use This Pattern

When you need to add an element quickly at the start of a list, use insert at beginning in doubly linked list to update pointers efficiently.

Common Mistakes

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

Mistake: Not handling empty list case causing nil pointer errors
Fix: Check if head is nil and set head to new node before linking

Summary

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

Use when you want to quickly add elements to the front without traversing the list.

The key is to link the new node forward to old head and old head back to new node, then update head.

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