Why Doubly Linked List Over Singly Linked List in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Main advantage of doubly linked list over singly linked list

Which of the following is the main advantage of using a doubly linked list instead of a singly linked list?

A It allows traversal in both forward and backward directions easily.

B It uses less memory because it stores only one pointer per node.

C It is simpler to implement because it has fewer pointers.

D It always has faster insertion at the end compared to singly linked list.

💡 Hint

Think about how nodes are connected and how you can move through the list.

A doubly linked list stores two pointers per node: one to the next node and one to the previous node. This allows easy traversal in both directions, unlike singly linked lists which only allow forward traversal.

❓ Predict Output

intermediate

Output after inserting nodes in doubly linked list

What is the printed state of the doubly linked list after these insertions?

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;

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

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

const dll = new DoublyLinkedList();
dll.insertAtEnd(10);
dll.insertAtEnd(20);
dll.insertAtEnd(30);
dll.printList();

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

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

C 10 -> 20 -> 30 -> null

D null

💡 Hint

Check how nodes are linked when inserted at the end.

Nodes are inserted at the end, so the list prints from head to tail: 10 <-> 20 <-> 30 <-> null.

🔧 Debug

advanced

Identify the bug in backward traversal of doubly linked list

What error will this code produce when trying to print the list backward?

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;

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

  printBackward() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' <-> ';
      current = current.prev;
    }
    result += 'null';
    console.log(result);
  }
}

const dll = new DoublyLinkedList();
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.printBackward();

A Prints '3 <-> 2 <-> 1 <-> null'

B Prints 'null'

C Infinite loop or runtime error

D Prints '1 <-> null'

💡 Hint

Check which node is used to start backward traversal.

Backward traversal should start from the tail, but this code starts from head. Since head.prev is null, it prints only the head value and stops.

📝 Syntax

advanced

Identify the syntax error in doubly linked list node insertion

Which option contains the syntax error when inserting a new node at the beginning of a doubly linked list?

DSA Typescript

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

A Assigning 'this.tail = newNode;' inside else block

B Using 'newNode.next = this.head;' instead of 'this.head.next = newNode;'

C Missing semicolon after 'this.head.prev = newNode'

D Using 'const newNode = Node(value);' instead of 'new Node(value);'

💡 Hint

Look carefully at line endings and punctuation.

In TypeScript, missing semicolons can cause syntax errors or unexpected behavior. The line 'this.head.prev = newNode' is missing a semicolon.

🚀 Application

expert

Choosing data structure for undo-redo feature

You want to implement an undo-redo feature in a text editor. Which data structure is best suited and why?

A Singly linked list, because it uses less memory and supports forward traversal.

B Doubly linked list, because it allows moving backward and forward through changes easily.

C Array, because it allows random access to all changes quickly.

D Stack, because it supports only undo operations efficiently.

💡 Hint

Think about how you move back and forth between states.

Undo-redo requires moving backward and forward through changes. Doubly linked lists allow easy traversal in both directions, making them ideal for this feature.

Practice

1. Why might you choose a doubly linked list over a singly linked list in a program?

easy

A. Because it uses less memory per node

B. Because it allows traversal in both directions easily

C. Because it is simpler to implement

D. Because it only stores one pointer per node

Solution

1. Step 1: Understand traversal capabilities

   A singly linked list allows moving forward only, while a doubly linked list allows moving forward and backward.

2. Step 2: Compare memory and complexity

   Doubly linked lists use more memory and are more complex but provide two-way traversal.

3. Final Answer:

   Because it allows traversal in both directions easily -> Option B

4. Quick Check:

   Two-way traversal = A [OK]

Hint: Doubly means two directions, singly means one [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing simplicity with singly linked lists
• Assuming singly linked lists allow backward traversal

2. Which of the following is the correct way to declare a node in a doubly linked list in TypeScript?

easy

A. class Node { value: number; next: Node; }

B. class Node { value: number; prev: Node; }

C. class Node { value: number; next: Node | null; prev: Node | null; }

D. class Node { value: number; next: Node | null; }

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have both next and prev pointers, which can be null if no neighbor exists.

2. Step 2: Check TypeScript syntax for nullable pointers

   Using Node | null correctly allows for the end nodes to have null pointers.

3. Final Answer:

   class Node { value: number; next: Node | null; prev: Node | null; } -> Option C

4. Quick Check:

   Doubly linked node needs next and prev with nulls [OK]

Hint: Doubly linked nodes have next and prev pointers [OK]

Common Mistakes:

• Omitting the prev pointer
• Not allowing null for next or prev
• Using only one pointer like singly linked list

3. Consider this TypeScript code snippet for a doubly linked list node insertion at the front:

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

class DoublyLinkedList {
  head: Node | null = null;
  insertFront(value: number) {
    const newNode = new Node(value);
    if (this.head) {
      newNode.next = this.head;
      this.head.prev = newNode;
    }
    this.head = newNode;
  }
}

const list = new DoublyLinkedList();
list.insertFront(10);
list.insertFront(20);
list.insertFront(30);

let current = list.head;
const result = [];
while (current) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

What will be printed?

medium

A. [10, 30, 20]

B. [10, 20, 30]

C. [20, 30, 10]

D. [30, 20, 10]

Solution

1. Step 1: Trace insertFront calls

   First insert 10: list is 10. Then insert 20 at front: list is 20 -> 10. Then insert 30 at front: list is 30 -> 20 -> 10.

2. Step 2: Traverse from head to next

   Starting at head (30), next is 20, then 10, then null. So collected values are [30, 20, 10].

3. Final Answer:

   [30, 20, 10] -> Option D

4. Quick Check:

   Insert front reverses order = [30, 20, 10] [OK]

Hint: Insert front adds new node before head [OK]

Common Mistakes:

• Assuming insertion appends at end
• Mixing order of traversal
• Ignoring prev pointer effects

4. This TypeScript code tries to delete the last node from a doubly linked list but has a bug:

deleteLast() {
  if (!this.head) return;
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  current.prev.next = null;
}

What is the bug here?

medium

A. It does not handle the case when list has only one node

B. It incorrectly sets current.next to null instead of current.prev.next

C. It causes infinite loop in the while

D. It deletes the head node instead of the last node

Solution

1. Step 1: Analyze deletion logic

   The code moves to the last node by following next pointers. Then it sets current.prev.next = null to remove last node.

2. Step 2: Check edge case for single node list

   If list has only one node, current.prev is null, so current.prev.next causes error.

3. Final Answer:

   It does not handle the case when list has only one node -> Option A

4. Quick Check:

   Single node list needs special case [OK]

Hint: Check for single node before accessing prev [OK]

Common Mistakes:

• Ignoring single node edge case
• Assuming prev is always non-null
• Confusing next and prev pointers

5. You want to implement a feature that requires frequent backward traversal from any node in a list. Which data structure is best and why? Options: A) Singly linked list because it uses less memory B) Circular singly linked list because it loops infinitely C) Array because it supports random access D) Doubly linked list because it allows backward traversal efficiently

hard

A. Doubly linked list because it allows backward traversal efficiently

B. Circular singly linked list because it loops infinitely

C. Array because it supports random access

D. Singly linked list because it uses less memory

Solution

1. Step 1: Understand backward traversal need

   Backward traversal means moving from a node to its previous nodes efficiently.

2. Step 2: Compare data structures for backward traversal

   Singly linked lists do not have backward pointers. Arrays allow random access but not linked traversal. Circular singly linked lists loop but do not support backward traversal. Doubly linked lists have prev pointers for efficient backward moves.

3. Final Answer:

   Doubly linked list because it allows backward traversal efficiently -> Option A

4. Quick Check:

   Backward traversal needs prev pointers [OK]

Hint: Backward moves need prev pointers, only doubly linked lists have them [OK]

Common Mistakes:

• Choosing singly linked list for backward traversal
• Confusing arrays with linked lists
• Thinking circular singly linked lists support backward moves