Create and Initialize Doubly Linked List in DSA Javascript - Execution Trace

Concept Flow - Create and Initialize Doubly Linked List

Create new node with data

↓

Set node.prev = null

↓

Set node.next = null

↓

Set head = node

↓

Set tail = node

↓

Done

Create a new node with data, set its prev and next pointers to null, then set both head and tail to this node to initialize the doubly linked list.

Execution Sample

DSA Javascript

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

let head = new Node(10);
let tail = head;

This code creates a doubly linked list with a single node containing data 10, where head and tail both point to this node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	Node(10)	node.prev = null, node.next = null	null <- [10] -> null
2	Set head = node	Node(10)	head points to Node(10)	head -> [10] -> null
3	Set tail = node	Node(10)	tail points to Node(10)	head -> [10] <- tail
4	Initialization complete	Node(10)	head and tail both point to Node(10)	null <- head/tail -> [10] -> null

💡 List initialized with one node; head and tail point to the same node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
node.data	undefined	10	10	10	10
node.prev	undefined	null	null	null	null
node.next	undefined	null	null	null	null
head	null	null	Node(10)	Node(10)	Node(10)
tail	null	null	null	Node(10)	Node(10)

Key Moments - 3 Insights

Why do we set both head and tail to the new node when initializing?

Because the list has only one node, that node is both the start (head) and end (tail) of the list, as shown in execution_table step 4.

Why are node.prev and node.next set to null initially?

Because the new node is alone in the list, it has no previous or next nodes, so both pointers must be null (see execution_table step 1).

What does the visual state 'null <- [10] -> null' mean?

It shows the node with data 10 has no previous node (null on left) and no next node (null on right), matching the doubly linked list structure at step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what does the head pointer point to?

A null

B Node with data 0

C Node with data 10

D Undefined

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 2 in execution_table.

At which step do both head and tail point to the same node?

A Step 1

B Step 4

C Step 2

D Step 3

💡 Hint

Look at the 'Pointer Changes' column and 'Visual State' at step 4 in execution_table.

If node.next was not set to null initially, what would be the visual state after step 1?

A null <- [10] -> undefined

B null <- [10] -> null

C undefined <- [10] -> null

D undefined <- [10] -> undefined

💡 Hint

Refer to the 'Pointer Changes' for node.next at step 1 in variable_tracker.

Concept Snapshot

Create a new node with data.
Set node.prev = null and node.next = null.
Set head and tail pointers to this node.
This initializes a doubly linked list with one node.
Head and tail point to the same node when list has one element.

Full Transcript

To create and initialize a doubly linked list, first create a new node with the given data. Set its previous and next pointers to null because it is the only node. Then set both the head and tail pointers of the list to this new node. This means the list starts and ends at this single node. The visual state shows the node with data 10 having null on both sides, indicating no neighbors. This process is complete when head and tail both point to this node, representing a list with one element.

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