Doubly Linked List Structure and Node Design in DSA Javascript - Execution Trace

Concept Flow - Doubly Linked List Structure and Node Design

Create new node

↓

Set node.data, node.prev, node.next

↓

If list empty?

Yes→head = node, tail = node

No↓

Link new node with tail

↓

Update tail to new node

↓

Done

Shows how a new node is created and linked in a doubly linked list, updating pointers for both previous and next nodes.

Execution Sample

DSA Javascript

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

Defines a doubly linked list node with data and two pointers: prev and next.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node with data=10	None	node.prev=null, node.next=null	null <- [10] -> null
2	List empty? Yes	None	head=node, tail=node	[10]
3	Create node with data=20	[10]	node.prev=null, node.next=null	[10]
4	List empty? No	[10]	tail.next=node, node.prev=tail	[10] <-> [20]
5	Update tail to new node	[10] <-> [20]	tail=node	[10] <-> [20]
6	Create node with data=30	[10] <-> [20]	node.prev=null, node.next=null	[10] <-> [20]
7	List empty? No	[10] <-> [20]	tail.next=node, node.prev=tail	[10] <-> [20] <-> [30]
8	Update tail to new node	[10] <-> [20] <-> [30]	tail=node	[10] <-> [20] <-> [30]
9	End of insertion	[10] <-> [20] <-> [30]	No changes	[10] <-> [20] <-> [30]

💡 All nodes inserted, list updated with correct prev and next pointers.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	Final
head	null	[10]	[10]	[10]	[10]
tail	null	[10]	[10]	[20]	[30]
node	null	[10]	[20]	[30]	null

Key Moments - 3 Insights

Why do we set node.prev to tail before updating tail?

Because the new node must point back to the current tail before tail moves to the new node, as shown in steps 4 and 7 in the execution_table.

What happens if the list is empty when inserting the first node?

The head and tail both point to the new node, making it the only node in the list, as shown in step 2.

Why do we set node.next to null when creating a new node?

Because the new node is added at the end, so it has no next node yet, as shown in steps 1, 3, and 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what pointer changes happen?

A new node.prev and new node.next both point to null

B tail.next points to new node, new node.prev points to tail

C head points to new node, new node.next points to head

D tail is set to null

💡 Hint

Check the 'Pointer Changes' column at step 4 in the execution_table.

At which step does the tail pointer update to the new node for the second time?

A Step 8

B Step 5

C Step 7

D Step 9

💡 Hint

Look at the 'Pointer Changes' column for tail updates in the execution_table.

If the list was empty, what would be the visual state after inserting the first node?

A [10] <-> [20] <-> [30]

B [10] <-> [20]

C null <- [10] -> null

D null

💡 Hint

Refer to step 1 and 2 visual states in the execution_table.

Concept Snapshot

Doubly Linked List Node:
- Has data, prev, next pointers
- prev points to previous node or null
- next points to next node or null
Insertion:
- Create node with data
- If empty, head and tail = node
- Else, link node.prev to tail, tail.next to node
- Update tail to new node

Full Transcript

This visual trace shows how a doubly linked list node is created and inserted at the end of the list. Each node has three parts: data, prev pointer, and next pointer. When the list is empty, the new node becomes both head and tail. For subsequent insertions, the new node's prev pointer links to the current tail, and the current tail's next pointer links to the new node. Then the tail pointer updates to the new node. The visual states show the list growing step by step with arrows indicating prev and next links.

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