Doubly Linked List Structure and Node Design in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

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;

  insertEnd(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    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.insertEnd(10);
dll.insertEnd(20);
dll.insertEnd(30);
dll.printList();

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

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

C 10 -> 20 -> 30 -> null

D null

💡 Hint

Remember that insertEnd adds nodes at the tail, so the order is the same as insertion.

Nodes are inserted at the end, so the list grows as 10 <-> 20 <-> 30 <-> null.

❓ Predict Output

intermediate

State of Doubly Linked List after Deletion

Given a doubly linked list with nodes 5 <-> 15 <-> 25 <-> 35 <-> null, what is the list after deleting the node with value 25?

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;

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

  deleteValue(value: number) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        if (current.prev) {
          current.prev.next = current.next;
        } else {
          this.head = current.next;
        }
        if (current.next) {
          current.next.prev = current.prev;
        } else {
          this.tail = current.prev;
        }
        return;
      }
      current = current.next;
    }
  }

  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.insertEnd(5);
dll.insertEnd(15);
dll.insertEnd(25);
dll.insertEnd(35);
dll.deleteValue(25);
dll.printList();

A 5 <-> 15 <-> 35 <-> null

B 5 <-> 15 <-> 25 <-> 35 <-> null

C 5 <-> 35 <-> null

D 15 <-> 25 <-> 35 <-> null

💡 Hint

Deleting 25 removes it and links 15 directly to 35.

Node with value 25 is removed, so 15's next points to 35 and 35's prev points to 15.

🔧 Debug

advanced

Identify the Bug in Node Insertion at Head

What error will occur when running this code that inserts a node at the head of a 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;

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

const dll = new DoublyLinkedList();
dll.insertHead(100);
dll.insertHead(200);
console.log(dll.head!.prev!.value);

A 100

B undefined

C 200

D TypeError: Cannot read property 'value' of null

💡 Hint

Check what happens to the prev pointer of the head node after insertions.

After inserting 200 at head, dll.head.prev is null, so accessing .value causes TypeError.

🧠 Conceptual

advanced

Understanding Node Connections in Doubly Linked List

In a doubly linked list, which statement about the 'prev' and 'next' pointers of the head and tail nodes is correct?

A Head node's next is null; tail node's prev is null

B Head node's prev is null; tail node's next is null

C Both head and tail nodes have prev and next as null

D Head node's prev points to tail; tail node's next points to head

💡 Hint

Think about the start and end of the list and what nodes they connect to.

Head has no previous node, so prev is null; tail has no next node, so next is null.

❓ Predict Output

expert

Output After Complex Insertions and Deletions

What is the printed state of the doubly linked list after these operations? 1. Insert 1 at end 2. Insert 2 at end 3. Insert 3 at head 4. Delete node with value 2 5. Insert 4 at end 6. Delete node with value 3

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;

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

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

  deleteValue(value: number) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        if (current.prev) {
          current.prev.next = current.next;
        } else {
          this.head = current.next;
        }
        if (current.next) {
          current.next.prev = current.prev;
        } else {
          this.tail = current.prev;
        }
        return;
      }
      current = current.next;
    }
  }

  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.insertEnd(1);
dll.insertEnd(2);
dll.insertHead(3);
dll.deleteValue(2);
dll.insertEnd(4);
dll.deleteValue(3);
dll.printList();

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

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

C 1 <-> 4 <-> null

D 4 <-> 1 <-> null

💡 Hint

Track each operation carefully and update head and tail pointers.

After all operations, nodes 3 and 2 are deleted, leaving 1 and 4 connected.

Practice

1. What is the main difference between a doubly linked list node and a singly linked list node?

easy

A. A doubly linked list node has pointers to both the previous and next nodes.

B. A doubly linked list node stores data in a different format.

C. A doubly linked list node can only point to the next node.

D. A doubly linked list node does not store any data.

Solution

1. Step 1: Understand node pointers in singly linked list

   A singly linked list node has only one pointer to the next node.

2. Step 2: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the previous node and one to the next node.

3. Final Answer:

   A doubly linked list node has pointers to both the previous and next nodes. -> Option A

4. Quick Check:

   Doubly linked list nodes have two pointers [OK]

Hint: Remember: doubly linked means two directions [OK]

Common Mistakes:

• Thinking doubly linked nodes only point forward
• Confusing data storage with pointer structure
• Assuming doubly linked nodes do not store data

2. Which of the following is the correct TypeScript syntax to define a doubly linked list node class with data of type number?

easy

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

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

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

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

Solution

1. Step 1: Check property types for next and prev

   Since next and prev can be null initially, their types must allow null (Node | null).

2. Step 2: Verify constructor initializes all properties

   The constructor sets data and initializes next and prev to null correctly.

3. Final Answer:

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

4. Quick Check:

   Allow null for next and prev in TypeScript [OK]

Hint: Use 'Node | null' for nullable pointers [OK]

Common Mistakes:

• Not allowing next and prev to be null
• Forgetting to initialize next and prev in constructor
• Setting next and prev types incorrectly

3. What will be the output of the following TypeScript code snippet?

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

const node1 = new Node(10);
const node2 = new Node(20);
node1.next = node2;
node2.prev = node1;

console.log(node1.next?.data);
console.log(node2.prev?.data);

medium

A. Error at runtime

B. 10\n20

C. undefined\nundefined

D. 20\n10

Solution

1. Step 1: Trace node1.next and node2.prev assignments

   node1.next points to node2, so node1.next.data is 20. node2.prev points to node1, so node2.prev.data is 10.

2. Step 2: Check console.log outputs

   console.log(node1.next?.data) prints 20, console.log(node2.prev?.data) prints 10.

3. Final Answer:

   20 10 -> Option D

4. Quick Check:

   next and prev pointers give 20 and 10 respectively [OK]

Hint: Follow next and prev pointers to get data [OK]

Common Mistakes:

• Confusing which node data is printed
• Ignoring optional chaining and assuming errors
• Mixing up prev and next pointers

4. Identify the error in the following TypeScript code for a doubly linked list node and select the fix.

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

medium

A. Change data type from number to any.

B. Remove the constructor to fix the error.

C. Change next and prev types to 'Node | null' to allow null assignment.

D. Initialize next and prev with new Node() instead of null.

Solution

1. Step 1: Analyze type declarations and assignments

   next and prev are typed as Node but assigned null, which is invalid in TypeScript.

2. Step 2: Fix type to allow null

   Changing next and prev types to 'Node | null' allows null assignment and fixes the error.

3. Final Answer:

   Change next and prev types to 'Node | null' to allow null assignment. -> Option C

4. Quick Check:

   Nullable pointers need 'Node | null' type [OK]

Hint: Allow null in pointer types to avoid errors [OK]

Common Mistakes:

• Leaving next and prev as non-nullable types
• Trying to assign new Node() without data
• Removing constructor unnecessarily

5. You want to insert a new node with data 30 between two existing nodes in a doubly linked list: nodeA and nodeB, where nodeA.next = nodeB and nodeB.prev = nodeA. Which sequence of pointer updates correctly inserts the new node?

hard

A. nodeA.next = newNode; nodeB.prev = newNode; newNode.next = nodeB; newNode.prev = nodeA;

B. newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode;

C. newNode.next = nodeA; newNode.prev = nodeB; nodeA.prev = newNode; nodeB.next = newNode;

D. nodeA.prev = newNode; nodeB.next = newNode; newNode.prev = nodeB; newNode.next = nodeA;

Solution

1. Step 1: Set newNode pointers to link between nodeA and nodeB

   newNode.prev must point to nodeA and newNode.next must point to nodeB to fit between them.

2. Step 2: Update nodeA and nodeB pointers to include newNode

   nodeA.next should point to newNode and nodeB.prev should point to newNode to complete the insertion.

3. Final Answer:

   newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode; -> Option B

4. Quick Check:

   Link newNode between nodeA and nodeB correctly [OK]

Hint: Link newNode pointers first, then update neighbors [OK]

Common Mistakes:

• Mixing up prev and next pointers
• Updating neighbors before setting newNode pointers
• Reversing nodeA and nodeB in assignments