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

Time Complexity: Insert at Beginning of Doubly Linked List

O(1)

Understanding Time Complexity

We want to know how the time to insert a new node at the start of a doubly linked list changes as the list grows.

How does the number of steps needed grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

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

This code creates a new node and inserts it at the start of a doubly linked list, updating pointers accordingly.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating a new node and updating a few pointers.
• How many times: This happens once per insertion, no loops or recursion involved.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	4-5 steps
100	4-5 steps
1000	4-5 steps

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

Final Time Complexity

Time Complexity: O(1)

This means inserting at the beginning takes a constant amount of time no matter how large the list is.

Common Mistake

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

[OK] Correct: We only change a few pointers at the start; no need to move or touch other nodes.

Interview Connect

Knowing that insertion at the start is quick helps you choose the right data structure and shows you understand efficient pointer updates.

Self-Check

"What if we changed this 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 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