Doubly Linked List Structure and Node Design in DSA Javascript

Mental Model

A doubly linked list is a chain of nodes where each node knows both its neighbor before and after it. This lets us move forward or backward easily.

Analogy: Imagine a train where each carriage has a connector to the carriage in front and the one behind. You can walk forward or backward along the train.

null ← 1 ↔ 2 ↔ 3 → null

Dry Run Walkthrough

Input: Create a doubly linked list with nodes 1, 2, 3 linked in order

Goal: Build the list so each node points to the next and previous nodes correctly

Step 1: Create node 1 with no previous or next

null ← [1] → null

Why: Start with the first node which has no neighbors yet

Step 2: Create node 2 and link it after node 1

null ← 1 ↔ [2] → null

Why: Node 2 connects forward from node 1 and node 1 points back to node 2

Step 3: Create node 3 and link it after node 2

null ← 1 ↔ 2 ↔ [3] → null

Why: Node 3 connects forward from node 2 and node 2 points back to node 3

Result:

null ← 1 ↔ 2 ↔ 3 → null

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null; // points to previous node
    this.next = null; // points to next node
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null; // first node
    this.tail = null; // last node
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode; // list empty, new node is head
      this.tail = newNode; // and tail
      return;
    }
    this.tail.next = newNode; // current tail points forward to new node
    newNode.prev = this.tail; // new node points back to current tail
    this.tail = newNode; // update tail to new node
  }

  printList() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value;
      if (curr.next) result += ' ↔ ';
      curr = curr.next; // move forward
    }
    result += ' → null';
    console.log(result);
  }
}

// Driver code
const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.printList();

this.tail.next = newNode; // current tail points forward to new node

link new node after current tail to maintain forward chain

newNode.prev = this.tail; // new node points back to current tail

link new node back to current tail to maintain backward chain

this.tail = newNode; // update tail to new node

move tail pointer to new last node

while (curr) { result += curr.value; if (curr.next) result += ' ↔ '; curr = curr.next; // move forward }

traverse list forward to build string representation

Output

1 ↔ 2 ↔ 3 → null

Complexity Analysis

Time: O(n) because appending requires constant time, but printing traverses all n nodes once

Space: O(n) because we store n nodes each with two pointers

vs Alternative: Compared to singly linked list, doubly linked list uses more space but allows backward traversal

Edge Cases

empty list

append sets head and tail to new node correctly

DSA Javascript

if (!this.head) {
  this.head = newNode;
  this.tail = newNode;
  return;
}

When to Use This Pattern

When you need to move both forward and backward through a list easily, use a doubly linked list structure because each node links both ways.

Common Mistakes

Mistake: Forgetting to update the new node's prev pointer when appending
Fix: Always set newNode.prev = this.tail before updating tail

Mistake: Not updating tail pointer after adding a new node
Fix: Set this.tail = newNode to keep tail accurate

Summary

It creates a chain of nodes where each node links to the next and previous nodes.

Use it when you want to move forward and backward through a list easily.

Remember each node has two pointers: one to the next node and one to the previous node.

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