Node Structure and Pointer Design in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a node in data structures?

A node is a basic unit that holds data and references (pointers) to other nodes, helping to build structures like linked lists and trees.

beginner

What does a pointer in a node represent?

A pointer is a reference inside a node that points to another node, showing the connection or link between nodes.

intermediate

Explain the difference between single and double pointers in node design.

Single pointer nodes link to the next node only (like in singly linked lists). Double pointer nodes have two references: one to the next node and one to the previous node (like in doubly linked lists).

beginner

Why is it important to initialize pointers in a node?

Initializing pointers prevents errors by ensuring they either point to a valid node or null, avoiding unexpected behavior or crashes.

beginner

Show a simple TypeScript node structure for a singly linked list.

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

What does the 'next' pointer in a singly linked list node point to?

A The head node

B The next node in the list

C The last node in the list

D The previous node in the list

In singly linked lists, the 'next' pointer always points to the next node in the sequence.

In a doubly linked list node, how many pointers are there?

A One

B Three

C Two

D None

Doubly linked list nodes have two pointers: one to the next node and one to the previous node.

What should a pointer be set to if it does not point to any node?

A It should point to itself

B Undefined

C Zero

D Null

Pointers should be set to null to clearly indicate they do not point to any node.

Which of these is NOT part of a typical node structure?

A Index number

B Data

C Pointer

D Reference to another node

Nodes usually contain data and pointers, but not an index number.

Why do we use pointers in node structures?

A To link nodes together

B To store data

C To perform calculations

D To sort data

Pointers link nodes together to form data structures like lists and trees.

Describe the components of a node in a linked list and their roles.

Think about what each node holds and how it connects to others.

Explain how pointers help in designing linked data structures.

Consider how nodes find each other.

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