Create and Initialize Doubly Linked List in DSA Javascript

Mental Model

A doubly linked list is a chain of nodes where each node knows the one before and the one after it.

Analogy: Imagine a train where each carriage is connected to the one before and after it, so you can move forward or backward easily.

null ← [head] 1 ↔ 2 ↔ 3 -> null
Each arrow shows links to previous and next nodes.

Dry Run Walkthrough

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

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

Step 1: Create first node with value 1; head and tail point here

null ← [head/tail] 1 -> null

Why: Start the list with the first node; it has no previous or next yet

Step 2: Create second node with value 2; link it after first node

null ← 1 ↔ [tail] 2 -> null

Why: Add second node and connect it to first node both ways

Step 3: Create third node with value 3; link it after second node

null ← 1 ↔ 2 ↔ [tail] 3 -> null

Why: Add third node and connect it to second node both ways

Result:

null ← 1 ↔ 2 ↔ 3 -> null

Annotated Code

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; // link current tail to new node
    newNode.prev = this.tail; // link new node back to current tail
    this.tail = newNode; // update tail to new node
  }

  printList() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + (curr.next ? ' ↔ ' : ' -> null');
      curr = curr.next;
    }
    console.log('null ← ' + result);
  }
}

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

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

Initialize head and tail when list is empty

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

Connect current tail's next pointer to new node

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

Connect new node's prev pointer back to current tail

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

Update tail reference to new node

while (curr) { result += curr.value + (curr.next ? ' ↔ ' : ' -> null'); curr = curr.next; }

Traverse list from head to tail to build string representation

Output

null ← 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(n) to build the list with n nodes because each append adds one node in constant time, but printing traverses all nodes once

Space: O(n) because we store n nodes in memory

vs Alternative: Compared to singly linked list, doubly linked list uses extra space for prev pointers but allows backward traversal

Edge Cases

Empty list before any append

Head and tail are null; first append sets both to new node

DSA Javascript

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

Appending only one node

List has one node with null prev and next

DSA Javascript

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

When to Use This Pattern

When you need a list where you can move forward and backward easily, use a doubly linked list to keep track of both directions.

Common Mistakes

Mistake: Not updating the new node's prev pointer when appending
Fix: Set newNode.prev = this.tail before updating tail

Mistake: Not updating the tail pointer after adding a new node
Fix: Assign this.tail = newNode after linking nodes

Summary

Creates a doubly linked list where each node points to the next and previous nodes.

Use when you want to traverse a list forwards and backwards efficiently.

Remember to update both next and prev pointers and move the tail reference when adding nodes.

Practice

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

easy

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

B. A doubly linked list stores data in arrays instead of nodes.

C. A doubly linked list can only be traversed forward.

D. A doubly linked list does not use pointers at all.

Solution

1. Step 1: Understand node structure in doubly linked list

   Each node in a doubly linked list has two pointers: one to the next node and one to the previous node.

2. Step 2: Compare with singly linked list

   Singly linked list nodes have only one pointer to the next node, so they cannot go backward.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list = two pointers per node [OK]

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

Common Mistakes:

• Thinking doubly linked lists use arrays
• Believing doubly linked lists only go forward
• Confusing pointers with data storage

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

easy

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

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

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

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

Solution

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

   A doubly linked list node needs both 'prev' and 'next' pointers initialized to null.

2. Step 2: Check constructor parameters and properties

   class Node { constructor(data) { this.data = data; this.prev = null; this.next = null; } } correctly defines 'data', 'prev', and 'next' properties in the constructor.

3. Final Answer:

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

4. Quick Check:

   Node needs prev and next pointers [OK]

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

Common Mistakes:

• Omitting the prev pointer
• Using wrong pointer names like left/right
• Using different property names for data

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

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }
}

const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);

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

medium

A. []

B. [3, 2, 1]

C. [null, null, null]

D. [1, 2, 3]

Solution

1. Step 1: Append nodes 1, 2, 3 to the list

   Each append adds a new node at the tail, linking prev and next pointers correctly.

2. Step 2: Traverse from head to tail collecting data

   Starting at head (1), moving next collects 1, then 2, then 3, then stops at null.

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Traversal from head collects [1, 2, 3] [OK]

Hint: Traverse from head using next to get list order [OK]

Common Mistakes:

• Confusing traversal direction
• Not updating tail pointer on append
• Pushing null values instead of data

4. Identify the error in the following code that tries to append a node to a doubly linked list:

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail.prev = newNode;
      this.tail = newNode;
    }
  }
}

medium

A. The constructor is missing initialization of head and tail.

B. The newNode should not have prev or next pointers.

C. The line 'this.tail.prev = newNode;' should be 'newNode.prev = this.tail;'.

D. The append method should not update the tail pointer.

Solution

1. Step 1: Analyze pointer updates in append method

   When adding newNode, the previous tail's next should point to newNode, and newNode's prev should point to old tail.

2. Step 2: Identify incorrect pointer assignment

   The code incorrectly sets 'this.tail.prev = newNode;' which wrongly changes the old tail's prev pointer instead of newNode's prev pointer.

3. Final Answer:

   The line 'this.tail.prev = newNode;' should be 'newNode.prev = this.tail;'. -> Option C

4. Quick Check:

   Correct prev pointer must link newNode to old tail [OK]

Hint: Prev pointer goes from new node back to old tail [OK]

Common Mistakes:

• Swapping prev and next pointers
• Not updating newNode.prev correctly
• Forgetting to update tail pointer

5. You want to create a doubly linked list from an array of values [10, 20, 30] and then traverse it backward from tail to head. Which code snippet correctly initializes the list and prints the values backward?

hard

A. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.tail;
while (current) { console.log(current.data); current = current.prev; }

B. const list = new DoublyLinkedList();
for (let i = 2; i >= 0; i--) list.append([10, 20, 30][i]);
let current = list.head;
while (current) { console.log(current.data); current = current.next; }

C. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.head;
while (current) { console.log(current.data); current = current.prev; }

D. const list = new DoublyLinkedList();
for (const val of [10, 20, 30]) list.append(val);
let current = list.tail;
while (current) { console.log(current.data); current = current.next; }

Solution

1. Step 1: Append values in order to the list

   Using a for-of loop appends 10, then 20, then 30, building the list head to tail.

2. Step 2: Traverse backward from tail using prev pointer

   Starting at tail (30), moving prev prints 30, 20, 10 in reverse order.

3. Final Answer:

   const list = new DoublyLinkedList(); for (const val of [10, 20, 30]) list.append(val); let current = list.tail; while (current) { console.log(current.data); current = current.prev; } -> Option A

4. Quick Check:

   Backward traversal uses tail and prev pointer [OK]

Hint: Traverse backward from tail using prev pointer [OK]

Common Mistakes:

• Traversing backward from head
• Using next pointer to go backward
• Appending values in reverse order but traversing forward