Insert at Beginning of Doubly Linked List in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting 10 at the beginning?

Consider a doubly linked list initially containing nodes with values 20 and 30. We insert 10 at the beginning. What is the printed list?

DSA Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  insertAtBeginning(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  printList(): string {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' <-> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const dll = new DoublyLinkedList();
dll.insertAtBeginning(20);
dll.insertAtBeginning(30);
dll.insertAtBeginning(10);
console.log(dll.printList());

A 10 <-> 30 <-> 20 <-> null

B 20 <-> 30 <-> 10 <-> null

C 30 <-> 20 <-> 10 <-> null

D 10 <-> 20 <-> 30 <-> null

💡 Hint

Remember that inserting at the beginning adds the new node before the current head.

Inserting 10 at the beginning means 10 becomes the new head, followed by 30 and then 20. The code first inserts 20, then inserts 30 at the beginning (before 20), then 10 before 30.

❓ Predict Output

intermediate

What is the list after inserting 5 at the beginning of an empty list?

Start with an empty doubly linked list. Insert 5 at the beginning. What is the printed list?

DSA Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  insertAtBeginning(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  printList(): string {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' <-> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const dll = new DoublyLinkedList();
dll.insertAtBeginning(5);
console.log(dll.printList());

A 5

B null <-> 5

C null

D 5 <-> null

💡 Hint

When the list is empty, the new node is both head and tail.

Inserting 5 into an empty list creates a single node which is both head and tail. The print shows '5 <-> null'.

🔧 Debug

advanced

Why does this insertAtBeginning method cause a runtime error?

Identify the cause of the runtime error in this insertAtBeginning method for a doubly linked list.

DSA Typescript

insertAtBeginning(value: number) {
  const newNode = new Node(value);
  newNode.next = this.head;
  this.head.prev = newNode;
  this.head = newNode;
  if (!this.tail) {
    this.tail = newNode;
  }
}

A newNode.prev is not set causing broken links

B this.head is null initially, so this.head.prev causes a runtime error

C this.tail is assigned before this.head causing null reference

D newNode.next is assigned incorrectly causing infinite loop

💡 Hint

Check what happens when the list is empty and this.head is null.

If the list is empty, this.head is null. Accessing this.head.prev causes a runtime error because you cannot access a property of null.

🧠 Conceptual

advanced

What is the time complexity of inserting at the beginning of a doubly linked list?

Choose the correct time complexity for inserting a node at the beginning of a doubly linked list.

A O(1) constant time

B O(log n) logarithmic time

C O(n) linear time

D O(n^2) quadratic time

💡 Hint

Inserting at the beginning only changes a few pointers.

Insertion at the beginning requires updating only a few pointers and does not depend on the list size, so it is O(1).

❓ Predict Output

expert

What is the output after multiple insertions at the beginning?

Given the following code, what is the printed doubly linked list?

DSA Typescript

class Node {
  value: number;
  next: Node | null = null;
  prev: Node | null = null;
  constructor(value: number) {
    this.value = value;
  }
}

class DoublyLinkedList {
  head: Node | null = null;
  tail: Node | null = null;

  insertAtBeginning(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
  }

  printList(): string {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' <-> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const dll = new DoublyLinkedList();
dll.insertAtBeginning(1);
dll.insertAtBeginning(2);
dll.insertAtBeginning(3);
dll.insertAtBeginning(4);
dll.insertAtBeginning(5);
console.log(dll.printList());

A 1 <-> 5 <-> 4 <-> 3 <-> 2 <-> null

B 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null

C 5 <-> 4 <-> 3 <-> 2 <-> 1 <-> null

D 5 <-> 1 <-> 2 <-> 3 <-> 4 <-> null

💡 Hint

Each insertion adds a new node before the current head.

Inserting 5, then 4, then 3, then 2, then 1 at the beginning results in the list starting with 5 and ending with 1.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To reverse the entire list

B. To add a new node after the tail node

C. To delete the first node in the list

D. To add a new node before the current head node

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 D

4. Quick Check:

   Insert at beginning = add before head [OK]

Hint: Beginning means before the head node [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Thinking insertion deletes nodes
• Mixing up head and tail nodes

2. Which of the following TypeScript code snippets correctly creates a new node and inserts it at the beginning of a doubly linked list?

easy

A. newNode.next = head; if(head) head.prev = newNode; head = newNode;

B. newNode.prev = head; if(head) head.next = newNode; head = newNode;

C. newNode.next = null; head = newNode; newNode.prev = null;

D. head = newNode; newNode.next = head; newNode.prev = head;

Solution

1. Step 1: Set newNode.next to current head

   The new node's next pointer should point to the current head node.

2. Step 2: Update current head's prev to newNode if head exists

   If the list is not empty, the current head's prev pointer must point back to the new node.

3. Step 3: Update head to newNode

   Finally, the head pointer is updated to the new node.

4. Final Answer:

   newNode.next = head; if(head) head.prev = newNode; head = newNode; -> Option A

5. Quick Check:

   Set newNode.next=head, head.prev=newNode, head=newNode [OK]

Hint: newNode.next = head; head.prev = newNode; head = newNode [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating head pointer
• Setting newNode.prev incorrectly

3. Given the following TypeScript code for a doubly linked list insertion at beginning, what will be the printed list after insertion?

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

let head: Node | null = new Node(10);
head.next = new Node(20);
head.next.prev = head;

const newNode = new Node(5);
newNode.next = head;
head.prev = newNode;
head = newNode;

// Print list
let temp = head;
const result: number[] = [];
while(temp) {
  result.push(temp.data);
  temp = temp.next;
}
console.log(result);

medium

A. [5, 10, 20]

B. [10, 20, 5]

C. [20, 10, 5]

D. [5, 20, 10]

Solution

1. Step 1: Initial list before insertion

   List is 10 <-> 20, head points to 10.

2. Step 2: Insert newNode with data 5 at beginning

   newNode.next = head (10), head.prev = newNode, head = newNode (5).

3. Step 3: Traverse list from new head

   Traverse from 5: 5 -> 10 -> 20.

4. Final Answer:

   [5, 10, 20] -> Option A

5. Quick Check:

   New head 5 followed by 10 and 20 [OK]

Hint: New node becomes head, list order starts with new node [OK]

Common Mistakes:

• Not updating head to newNode
• Incorrectly linking prev pointers
• Printing list from old head

4. Identify the error in the following TypeScript code that attempts to insert a node at the beginning of a doubly linked list:

const newNode = new Node(15);
newNode.prev = null;
newNode.next = head;
head.prev = newNode;
head = newNode;

medium

A. newNode.prev should point to head

B. Missing check if head is null before accessing head.prev

C. head should be assigned before setting newNode.next

D. newNode.next should be null

Solution

1. Step 1: Check if head is null before accessing head.prev

   If the list is empty (head is null), accessing head.prev causes an error.

2. Step 2: Add condition to update head.prev only if head exists

   Use if(head) head.prev = newNode; to avoid runtime error.

3. Final Answer:

   Missing check if head is null before accessing head.prev -> Option B

4. Quick Check:

   Always check head before head.prev [OK]

Hint: Check if head exists before accessing its properties [OK]

Common Mistakes:

• Ignoring null head and causing runtime error
• Swapping next and prev pointers
• Assigning head too early

5. You have a doubly linked list with nodes containing values [30, 40, 50]. You want to insert a new node with value 20 at the beginning. After insertion, which of the following correctly represents the list and the pointers of the new head node?

hard

A. List: 20 <-> 30 <-> 40 <-> 50; new head prev points to 30, next = null

B. List: 30 <-> 40 <-> 50 <-> 20; new head prev = 50, next = null

C. List: 20 <-> 30 <-> 40 <-> 50; new head prev = null, next points to 30

D. List: 50 <-> 40 <-> 30 <-> 20; new head prev = null, next points to 40

Solution

1. Step 1: Insert new node with value 20 before current head 30

   New node becomes head, its prev is null, next points to old head (30).

2. Step 2: Update old head's prev to new node

   Old head (30) prev pointer updated to new node (20).

3. Step 3: Confirm list order and pointers

   List order is 20 <-> 30 <-> 40 <-> 50 with new head prev=null, next=30.

4. Final Answer:

   List: 20 <-> 30 <-> 40 <-> 50; new head prev = null, next points to 30 -> Option C

5. Quick Check:

   New head prev=null, next=old head [OK]

Hint: New head prev always null, next points to old head [OK]

Common Mistakes:

• Setting new head prev to old tail
• Reversing list order accidentally
• Not updating old head prev pointer