Insert at Beginning of Doubly Linked List in DSA Go - Time & Space Complexity

Time Complexity: Insert at Beginning of Doubly Linked List

O(1)

Understanding Time Complexity

We want to understand how long it takes to add a new item at the start of a doubly linked list.

How does the time needed change as the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert new node at the beginning
func InsertAtBeginning(head **Node, data int) {
    newNode := &Node{data: data}
    newNode.next = *head
    if *head != nil {
        (*head).prev = newNode
    }
    *head = newNode
}
    

This code adds a new node at the start of a doubly linked list by adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Assigning pointers to link the new node.
• How many times: This happens only once per insertion, no loops or recursion.

How Execution Grows With Input

Adding a node at the start takes the same steps no matter how big the list is.

Input Size (n)	Approx. Operations
10	4 pointer assignments
100	4 pointer assignments
1000	4 pointer assignments

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means adding at the start takes a fixed amount of time, no matter how big the list is.

Common Mistake

[X] Wrong: "Inserting at the beginning takes longer as the list grows because we have to move all nodes."

[OK] Correct: We only change a few pointers at the start; we do not move or visit other nodes.

Interview Connect

Knowing that insertion at the start is quick helps you explain efficient list operations clearly and confidently.

Self-Check

"What if we had to insert at the end of the doubly linked list without a tail pointer? How would the time complexity change?"

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