Node Structure and Pointer Design in DSA Typescript

Mental Model

A node holds data and points to the next node, linking pieces like train cars.

Analogy: Imagine a train where each car carries cargo and hooks to the next car, forming a chain.

Node1[data|next] -> Node2[data|next] -> Node3[data|null]

Dry Run Walkthrough

Input: Create a linked list with nodes holding values 10, 20, 30 linked in order

Goal: Build nodes that connect in sequence so we can move from first to last

Step 1: Create first node with value 10 and next pointer null

[10|null]

Why: Start with a single node that holds data and no next node yet

Step 2: Create second node with value 20 and next pointer null

[10|null]   [20|null]

Why: Prepare next node separately before linking

Step 3: Set first node's next pointer to second node

[10|->] -> [20|null]

Why: Link first node to second so we can traverse from first to second

Step 4: Create third node with value 30 and next pointer null

[10|->] -> [20|null]   [30|null]

Why: Prepare third node before linking

Step 5: Set second node's next pointer to third node

[10|->] -> [20|->] -> [30|null]

Why: Complete chain so traversal can reach third node

Result:

[10|->] -> [20|->] -> [30|null]

Annotated Code

DSA Typescript

class Node {
  value: number;
  next: Node | null;

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

function buildLinkedList(values: number[]): Node | null {
  if (values.length === 0) return null;

  const head = new Node(values[0]);
  let current = head;

  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }

  return head;
}

function printList(head: Node | null): void {
  let current = head;
  let output = '';
  while (current !== null) {
    output += current.value + ' -> ';
    current = current.next;
  }
  output += 'null';
  console.log(output);
}

const values = [10, 20, 30];
const linkedList = buildLinkedList(values);
printList(linkedList);

const head = new Node(values[0]);

Create the first node as the start of the list

current.next = new Node(values[i]);

Create a new node and link it to the current node's next pointer

current = current.next;

Move current pointer forward to the newly created node

while (current !== null) {

Traverse nodes until the end of the list

output += current.value + ' -> ';

Add current node's value to output string

current = current.next;

Advance to next node in the list

Output

10 -> 20 -> 30 -> null

Complexity Analysis

Time: O(n) because we create and link each of the n nodes once

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

vs Alternative: Compared to arrays, linked nodes allow easy insertion without shifting elements but require extra memory for pointers

Edge Cases

Empty input array

Returns null indicating no nodes created

DSA Typescript

if (values.length === 0) return null;

Single element array

Creates one node with next pointer null

DSA Typescript

const head = new Node(values[0]);

When to Use This Pattern

When you need a chain of connected elements that can grow or shrink easily, think of node structures with pointers to link them.

Common Mistakes

Mistake: Forgetting to set the next pointer to null for the last node
Fix: Initialize next as null in the node constructor to mark list end

Mistake: Not updating the current pointer after linking a new node
Fix: Move current to current.next after linking to continue building the list

Summary

It creates linked nodes where each holds data and points to the next node.

Use it when you want a flexible chain of elements that can be easily connected or disconnected.

The key is each node stores a pointer to the next, forming a chain like train cars hooked together.

Practice

1. What does the next pointer in a singly linked list node represent?

easy

A. It points to the previous node in the list

B. It stores the data value of the node

C. It holds the size of the list

D. It points to the next node in the list

Solution

1. Step 1: Understand the role of next in singly linked list

   The next pointer is used to link the current node to the following node in the list.

2. Step 2: Differentiate from other pointers

   Unlike prev which points backward, next always points forward to the next node.

3. Final Answer:

   It points to the next node in the list -> Option D

4. Quick Check:

   next pointer = next node [OK]

Hint: Remember: next means forward link in singly linked list [OK]

Common Mistakes:

• Confusing next with previous pointer
• Thinking next stores data instead of address
• Assuming next holds list size

2. Which of the following is the correct TypeScript syntax to define a node class with a data property and a next pointer?

easy

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

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

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

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

Solution

1. Step 1: Check property types and initialization

   The next pointer should allow null to represent the end of the list, so its type must be Node | null.

2. Step 2: Verify constructor assigns values correctly

   The constructor takes data and sets next to null initially.

3. Final Answer:

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

4. Quick Check:

   Allow null for next pointer = class Node { data: number; next: Node | null; constructor(data: number) { this.data = data; this.next = null; } } [OK]

Hint: Next pointer must allow null to mark list end [OK]

Common Mistakes:

• Not allowing next to be null
• Forgetting to initialize next in constructor
• Using wrong types for next pointer

3. Given the following TypeScript code, what will be the output when printing the linked list data values?

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

const head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);

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

medium

A. [10, 20, 30]

B. [10, 20]

C. [20, 30]

D. []

Solution

1. Step 1: Trace node creation and linking

   Nodes are created with data 10, 20, and 30. The next pointers link 10 -> 20 -> 30 -> null.

2. Step 2: Follow the while loop to collect data

   The loop starts at head (10), adds 10, moves to 20, adds 20, moves to 30, adds 30, then stops at null.

3. Final Answer:

   [10, 20, 30] -> Option A

4. Quick Check:

   Traverse all nodes = [10, 20, 30] [OK]

Hint: Traverse until next is null to collect all nodes [OK]

Common Mistakes:

• Stopping traversal too early
• Not linking nodes correctly
• Confusing data values with pointers

4. Identify the error in the following TypeScript code for a singly linked list node and fix it:

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

medium

A. Data property should be optional

B. The constructor should not assign null to next

C. The type of next should be 'Node | null' to allow null assignment

D. Class should not have a constructor

Solution

1. Step 1: Analyze the type of next pointer

   The next property is typed as Node but assigned null, which is invalid.

2. Step 2: Correct the type to allow null

   Change the type to Node | null so it can hold either a node or null.

3. Final Answer:

   The type of next should be 'Node | null' to allow null assignment -> Option C

4. Quick Check:

   Allow null in next type = The type of next should be 'Node | null' to allow null assignment [OK]

Hint: Next pointer must allow null for list end [OK]

Common Mistakes:

• Not allowing null in next type
• Removing constructor unnecessarily
• Making data optional without reason

5. You want to design a doubly linked list node in TypeScript that stores a number and has pointers to both previous and next nodes. Which of the following class definitions correctly implements this with proper pointer types and initialization?

hard

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

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

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

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

Solution

1. Step 1: Check pointer types for doubly linked list

   Both prev and next pointers must allow null to represent ends of the list.

2. Step 2: Verify constructor initializes pointers to null

   Constructor correctly sets prev and next to null initially.

3. Final Answer:

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

4. Quick Check:

   Doubly linked list pointers allow null = class Node { data: number; prev: Node | null; next: Node | null; constructor(data: number) { this.data = data; this.prev = null; this.next = null; } } [OK]

Hint: Both prev and next pointers must allow null [OK]

Common Mistakes:

• Not allowing null for prev or next
• Setting pointer types incorrectly
• Initializing pointers to wrong values