Why Doubly Linked List Structure and Node Design in DSA Javascript?

The Big Idea

What if you could move through your data like flipping pages forward and backward in a book, not just one way?

The Scenario

Imagine you have a long chain of paper clips linked together. You want to add or remove clips from anywhere in the chain, but you can only move forward along the chain, one clip at a time.

This makes it hard to quickly find a clip or go back to a previous one.

The Problem

Using a simple chain where you can only move forward means you must start at the beginning every time you want to find or change something near the end.

This wastes time and can cause mistakes if you lose track of where you are.

The Solution

A doubly linked list is like a chain where each paper clip connects to both the next and the previous clip.

This lets you move forward or backward easily, making adding, removing, or finding clips faster and less confusing.

Before vs After

✗ Before

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

✓ After

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

What It Enables

It enables easy navigation in both directions, making data management more flexible and efficient.

Real Life Example

Think of a music playlist where you want to go to the next song or quickly jump back to the previous one without starting over.

Key Takeaways

Doubly linked lists let you move forward and backward through data.

Each node stores links to both next and previous nodes.

This design makes adding and removing items easier anywhere in the list.

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