Doubly Linked List Structure and Node Design in DSA Javascript - Build from Scratch

Doubly Linked List Structure and Node Design

📖 Scenario: Imagine you are building a music playlist app. Each song in the playlist is connected to the previous and next songs, allowing users to move forward or backward easily.

🎯 Goal: You will create the basic structure of a doubly linked list by designing the Node class and the DoublyLinkedList class with an empty list.

📋 What You'll Learn

Create a Node class with value, next, and prev properties

Create a DoublyLinkedList class with head and tail properties initialized to null

Ensure the Node constructor sets next and prev to null by default

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, web browsers, and other apps where users need to move back and forth through items easily.

💼 Career

Understanding doubly linked lists helps in building efficient data navigation features and is a common topic in coding interviews.

1

Create the Node class

Create a class called Node with a constructor that takes a parameter value. Inside the constructor, set this.value to value, and set this.next and this.prev to null.

DSA Javascript

# Your code here

Hint

Think of each node as a box holding a song. It needs to know the song's name (value) and links to the next and previous songs (next and prev).

2

Create the DoublyLinkedList class

Create a class called DoublyLinkedList with a constructor that sets this.head and this.tail to null.

DSA Javascript

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

# Your code here

Hint

The doubly linked list starts empty, so both head and tail should be null.

3

Add a method to check if the list is empty

Inside the DoublyLinkedList class, add a method called isEmpty that returns true if this.head is null, otherwise returns false.

DSA Javascript

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

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    
    # Your code here
}

Hint

This method helps us quickly know if the playlist has any songs or is empty.

4

Print if the list is empty

Create a new DoublyLinkedList object called playlist. Then print the result of calling playlist.isEmpty().

DSA Javascript

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

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

# Your code here

Hint

Since the list is new and empty, isEmpty() should print true.

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