Doubly Linked List Structure and Node Design in DSA Typescript - 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→Set head and tail to new node

No↓

Link new node with existing nodes

↓

Update head or tail pointers

↓

Node inserted, list updated

Shows how a new node is created with data and pointers, then linked into the doubly linked list by updating previous and next pointers and adjusting head or tail.

Execution Sample

DSA Typescript

class Node {
  data: number;
  prev: Node | null;
  next: Node | null;

  constructor(data: number) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

Defines a doubly linked list node with data and pointers to previous and next nodes.

Execution Table

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

💡 All nodes inserted, list correctly linked with prev and next pointers.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
head	null	null	[10]	[10]	[10]	[10]	[10]	[10]	[10]	[10]
tail	null	null	[10]	[10]	[10]	[20]	[20]	[20]	[30]	[30]
node (new)	null	[10]	null	[20]	null	null	[30]	null	null	null
node.prev	null	null	null	null	[10]	null	null	[20]	null	null
node.next	null	null	null	null	null	null	null	null	null	null

Key Moments - 3 Insights

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

Because the new node is not linked yet, so both pointers start as null. See execution_table step 1 where node.prev and node.next are null.

Why do we update the tail pointer after linking the new node?

Because the new node becomes the last node in the list, so tail must point to it. See execution_table step 5 and 8 where tail is updated.

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

We set both head and tail to the new node since it is the only node. See execution_table step 2.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what pointers are changed?

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

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

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

D No pointers are changed

💡 Hint

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

At which step does the tail pointer first change from [10] to [20]?

A Step 3

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'tail' variable in variable_tracker after each step.

If we did not update the tail pointer after insertion, what would happen?

A The list would lose the head pointer

B The new node would not be linked

C The tail pointer would still point to the old last node

D The list would become empty

💡 Hint

Refer to key_moments about tail pointer updates and execution_table steps 5 and 8.

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 null pointers
- If empty, head and tail = node
- Else link node after tail
- Update tail to new node

Full Transcript

A doubly linked list node holds data and two pointers: prev and next. When creating a new node, both pointers start as null. If the list is empty, the new node becomes both head and tail. Otherwise, the new node is linked after the current tail by setting tail.next to the new node and new node.prev to the tail. Then, the tail pointer is updated to the new node. This process repeats for each insertion, maintaining the doubly linked structure where nodes link forward and backward.

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 has pointers to both the previous and next nodes.

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 does not store any data.

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 previous node and one to the next node.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list nodes have two pointers [OK]

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

Common Mistakes:

• Thinking doubly linked nodes only point forward
• Confusing data storage with pointer structure
• Assuming doubly linked nodes do not store data

2. Which of the following is the correct TypeScript syntax to define a doubly linked list node class with data of type number?

easy

A. class Node { data: number; next: Node | null; prev: Node | null; constructor(data: number) { this.data = data; this.next = null; this.prev = null; } }

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

C. class Node { data: number; next: Node; prev: Node; constructor(data: number) { this.data = data; } }

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

Solution

1. Step 1: Check property types for next and prev

   Since next and prev can be null initially, their types must allow null (Node | null).

2. Step 2: Verify constructor initializes all properties

   The constructor sets data and initializes next and prev to null correctly.

3. Final Answer:

   class Node { data: number; next: Node | null; prev: Node | null; constructor(data: number) { this.data = data; this.next = null; this.prev = null; } } -> Option A

4. Quick Check:

   Allow null for next and prev in TypeScript [OK]

Hint: Use 'Node | null' for nullable pointers [OK]

Common Mistakes:

• Not allowing next and prev to be null
• Forgetting to initialize next and prev in constructor
• Setting next and prev types incorrectly

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

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

const node1 = new Node(10);
const node2 = new Node(20);
node1.next = node2;
node2.prev = node1;

console.log(node1.next?.data);
console.log(node2.prev?.data);

medium

A. Error at runtime

B. 10\n20

C. undefined\nundefined

D. 20\n10

Solution

1. Step 1: Trace node1.next and node2.prev assignments

   node1.next points to node2, so node1.next.data is 20. node2.prev points to node1, so node2.prev.data is 10.

2. Step 2: Check console.log outputs

   console.log(node1.next?.data) prints 20, console.log(node2.prev?.data) prints 10.

3. Final Answer:

   20 10 -> Option D

4. Quick Check:

   next and prev pointers give 20 and 10 respectively [OK]

Hint: Follow next and prev pointers to get data [OK]

Common Mistakes:

• Confusing which node data is printed
• Ignoring optional chaining and assuming errors
• Mixing up prev and next pointers

4. Identify the error in the following TypeScript code for a doubly linked list node and select the fix.

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

medium

A. Change data type from number to any.

B. Remove the constructor to fix the error.

C. Change next and prev types to 'Node | null' to allow null assignment.

D. Initialize next and prev with new Node() instead of null.

Solution

1. Step 1: Analyze type declarations and assignments

   next and prev are typed as Node but assigned null, which is invalid in TypeScript.

2. Step 2: Fix type to allow null

   Changing next and prev types to 'Node | null' allows null assignment and fixes the error.

3. Final Answer:

   Change next and prev types to 'Node | null' to allow null assignment. -> Option C

4. Quick Check:

   Nullable pointers need 'Node | null' type [OK]

Hint: Allow null in pointer types to avoid errors [OK]

Common Mistakes:

• Leaving next and prev as non-nullable types
• Trying to assign new Node() without data
• Removing constructor unnecessarily

5. You want to insert a new node with data 30 between two existing nodes in a doubly linked list: nodeA and nodeB, where nodeA.next = nodeB and nodeB.prev = nodeA. Which sequence of pointer updates correctly inserts the new node?

hard

A. nodeA.next = newNode; nodeB.prev = newNode; newNode.next = nodeB; newNode.prev = nodeA;

B. newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode;

C. newNode.next = nodeA; newNode.prev = nodeB; nodeA.prev = newNode; nodeB.next = newNode;

D. nodeA.prev = newNode; nodeB.next = newNode; newNode.prev = nodeB; newNode.next = nodeA;

Solution

1. Step 1: Set newNode pointers to link between nodeA and nodeB

   newNode.prev must point to nodeA and newNode.next must point to nodeB to fit between them.

2. Step 2: Update nodeA and nodeB pointers to include newNode

   nodeA.next should point to newNode and nodeB.prev should point to newNode to complete the insertion.

3. Final Answer:

   newNode.prev = nodeA; newNode.next = nodeB; nodeA.next = newNode; nodeB.prev = newNode; -> Option B

4. Quick Check:

   Link newNode between nodeA and nodeB correctly [OK]

Hint: Link newNode pointers first, then update neighbors [OK]

Common Mistakes:

• Mixing up prev and next pointers
• Updating neighbors before setting newNode pointers
• Reversing nodeA and nodeB in assignments