Doubly Linked List Structure and Node Design in DSA Javascript - 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 Javascript

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(value) {
    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.append(10);
dll.append(20);
dll.append(30);
dll.printList();

A null

B 10 -> 20 -> 30 -> null

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

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

💡 Hint

Remember that append adds nodes at the end, so the order is the same as insertion.

Appending nodes adds them to the tail, so the list prints from head to tail as 10 <-> 20 <-> 30 <-> null.

❓ Predict Output

intermediate

Output after Removing Head Node

Given a doubly linked list with nodes 5 <-> 15 <-> 25 <-> null, what is the printed list after removing the head node?

DSA Javascript

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(value) {
    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;
  }

  removeHead() {
    if (!this.head) return;
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
      return;
    }
    this.head = this.head.next;
    this.head.prev = null;
  }

  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.append(5);
dll.append(15);
dll.append(25);
dll.removeHead();
dll.printList();

A 15 <-> 25 <-> null

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

C 25 <-> 15 <-> null

D null

💡 Hint

Removing head moves the head pointer to the next node and updates prev to null.

After removing the head (5), the new head is 15, and the list is 15 <-> 25 <-> null.

🔧 Debug

advanced

Identify the Bug in Node Insertion at Head

What error will occur when running this code that inserts a new node at the head of a doubly linked list?

DSA Javascript

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  insertAtHead(value) {
    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;
    }
  }

  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.insertAtHead(1);
dll.insertAtHead(2);
dll.insertAtHead(3);
dll.printList();
console.log(dll.tail.prev.value);

A TypeError: Cannot read property 'value' of null

B Output: 1 <-> 2 <-> 3 <-> null and 2

C ReferenceError: dll is not defined

D Output: 3 <-> 2 <-> 1 <-> null and 2

💡 Hint

Check how tail and prev pointers are updated during insertions at head.

The list after insertions is 3 <-> 2 <-> 1 <-> null. The tail is 1, and tail.prev is 2, so dll.tail.prev.value is 2.

❓ Predict Output

advanced

Output after Reversing a Doubly Linked List

What is the printed state of the doubly linked list after reversing it? Initial list: 1 <-> 4 <-> 7 <-> null

DSA Javascript

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  append(value) {
    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;
  }

  reverse() {
    let current = this.head;
    let temp = null;
    while (current) {
      temp = current.prev;
      current.prev = current.next;
      current.next = temp;
      current = current.prev;
    }
    if (temp) {
      this.head = temp.prev;
    }
  }

  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.append(1);
dll.append(4);
dll.append(7);
dll.reverse();
dll.printList();

A 1 <-> 4 <-> 7 <-> null

B 7 <-> 4 <-> 1 <-> null

C null

D TypeError: Cannot read property 'prev' of null

💡 Hint

Reversing swaps next and prev pointers and updates head to the last node.

After reversing, the list order is reversed: 7 <-> 4 <-> 1 <-> null.

🧠 Conceptual

expert

Understanding Node Connections in Doubly Linked List

In a doubly linked list, if a node's next pointer is null but its prev pointer is not null, which node is it most likely to be?

A The tail node

B The head node

C A middle node

D An isolated node not in the list

💡 Hint

Think about which node has no next node but has a previous node.

The tail node has no next node (next is null) but has a previous node (prev not null).

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 does not store any data.

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 has pointers to both the next and previous nodes.

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 next node and one to the previous node.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list nodes have two pointers [OK]

Hint: Remember: doubly means two pointers, singly means one [OK]

Common Mistakes:

• Thinking doubly linked list nodes store data differently
• Confusing the number of pointers in singly vs doubly linked nodes
• Assuming doubly linked nodes do not store data

2. Which of the following is the correct way to define a doubly linked list node class in JavaScript?

easy

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

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

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

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

Solution

1. Step 1: Check for data property in constructor

   The node must store data, so constructor should assign this.data = data.

2. Step 2: Check for both next and prev pointers

   A doubly linked list node must have this.next and this.prev initialized to null.

3. Final Answer:

   class Node { constructor(data) { this.data = data; this.next = null; this.prev = null; } } -> Option B

4. Quick Check:

   Doubly linked list node has data, next, and prev [OK]

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

Common Mistakes:

• Omitting the prev pointer
• Not initializing next or prev to null
• Forgetting to assign data in constructor

3. Given the following code, what will be the output after inserting nodes 10 and 20 into an empty doubly linked list?

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
  }
  insert(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
    newNode.prev = current;
  }
  print() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.data + ' <-> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new DoublyLinkedList();
list.insert(10);
list.insert(20);
list.print();

medium

A. 10 <-> 20 <-> null

B. 20 <-> 10 <-> null

C. 10 -> 20 -> null

D. null

Solution

1. Step 1: Insert 10 into empty list

   Since head is null, head becomes node with data 10.

2. Step 2: Insert 20 at the end

   Traverse to last node (10), set its next to new node 20, and new node's prev to 10.

3. Step 3: Print list

   Traverse from head: 10 <-> 20 <-> null is printed.

4. Final Answer:

   10 <-> 20 <-> null -> Option A

5. Quick Check:

   Insertion appends nodes in order [OK]

Hint: Insertion appends nodes at end, so order is insertion order [OK]

Common Mistakes:

• Confusing order of nodes after insertion
• Using single arrow -> instead of double <->
• Printing null instead of list contents

4. Identify the error in the following doubly linked list insertion method and select the correct fix:

insert(data) {
  const newNode = new Node(data);
  if (!this.head) {
    this.head = newNode;
    return;
  }
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  current.next = newNode;
  // Missing line here
}

medium

A. Add 'newNode.prev = current;' after 'current.next = newNode;'

B. Add 'current.prev = newNode;' after 'current.next = newNode;'

C. Add 'this.head.prev = newNode;' after 'current.next = newNode;'

D. No fix needed; code is correct

Solution

1. Step 1: Understand pointer updates in insertion

   When adding newNode after current, newNode.prev must point back to current.

2. Step 2: Identify missing pointer assignment

   Code sets current.next = newNode but does not set newNode.prev = current, breaking backward link.

3. Final Answer:

   Add 'newNode.prev = current;' after 'current.next = newNode;' -> Option A

4. Quick Check:

   Backward link must be set for doubly linked list [OK]

Hint: Always set newNode.prev to current when inserting at end [OK]

Common Mistakes:

• Forgetting to set newNode.prev
• Setting current.prev instead of newNode.prev
• Assuming no fix needed

5. You want to implement a method to delete a node with a given value from a doubly linked list. Which of the following steps is NOT necessary for correctly removing the node?

hard

A. Update the previous node's next pointer to skip the deleted node.

B. Update the next node's prev pointer to skip the deleted node.

C. Traverse the list backwards from tail to find the node.

D. Set the deleted node's next and prev pointers to null.

Solution

1. Step 1: Understand deletion pointer updates

   To remove a node, update previous node's next and next node's prev to bypass it.

2. Step 2: Check necessity of clearing deleted node pointers

   Setting deleted node's next and prev to null helps garbage collection and avoids dangling pointers.

3. Step 3: Analyze traversal direction

   Traversing backwards from tail is not necessary; forward traversal from head suffices to find node.

4. Final Answer:

   Traverse the list backwards from tail to find the node. -> Option C

5. Quick Check:

   Forward traversal is enough to find node for deletion [OK]

Hint: Deletion needs pointer updates, not backward traversal [OK]

Common Mistakes:

• Thinking backward traversal is required
• Ignoring pointer updates on neighbors
• Not clearing deleted node pointers