Node Structure and Pointer Design in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of a singly linked list after insertions

What is the printed state of the singly linked list after inserting nodes with values 10, 20, and 30 in that order?

DSA Typescript

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

class SinglyLinkedList {
  head: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  printList() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new SinglyLinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.printList();

A 30 -> 20 -> 10 -> null

B 10 -> 20 -> 30 -> null

C 10 -> 30 -> 20 -> null

D null

💡 Hint

Remember that insertion adds nodes at the end of the list.

Nodes are inserted at the end, so the list prints in the order 10, 20, 30 followed by null.

❓ Predict Output

intermediate

Output of doubly linked list after forward and backward traversal

Given a doubly linked list with nodes 1, 2, 3 inserted in order, what is the output of forward and backward traversal?

DSA Typescript

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

class DoublyLinkedList {
  head: DNode | null = null;
  tail: DNode | null = null;

  insert(value: number) {
    const newNode = new DNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

  printForward() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }

  printBackward() {
    let current = this.tail;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.prev;
    }
    result += 'null';
    console.log(result);
  }
}

const dlist = new DoublyLinkedList();
dlist.insert(1);
dlist.insert(2);
dlist.insert(3);
dlist.printForward();
dlist.printBackward();

A

Forward: null
Backward: null

B

Forward: 3 -> 2 -> 1 -> null
Backward: 1 -> 2 -> 3 -> null

C

Forward: 1 -> 3 -> 2 -> null
Backward: 2 -> 3 -> 1 -> null

D

Forward: 1 -> 2 -> 3 -> null
Backward: 3 -> 2 -> 1 -> null

💡 Hint

Forward traversal starts at head, backward at tail.

Insertion adds nodes at tail, so forward prints 1 to 3, backward prints 3 to 1.

🔧 Debug

advanced

Identify the error in circular linked list insertion

What error occurs when running this circular linked list insertion code?

DSA Typescript

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

class CircularLinkedList {
  head: CNode | null = null;

  insert(value: number) {
    const newNode = new CNode(value);
    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head;
    } else {
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next!;
      }
      current.next = newNode;
      newNode.next = this.head;
    }
  }

  printList() {
    if (!this.head) {
      console.log('null');
      return;
    }
    let current = this.head;
    let result = '';
    do {
      result += current.value + ' -> ';
      current = current.next!;
    } while (current !== this.head);
    result += '(head)';
    console.log(result);
  }
}

const clist = new CircularLinkedList();
clist.insert(5);
clist.insert(10);
clist.insert(15);
clist.printList();

A TypeError: Cannot read property 'next' of null

B Runtime error: infinite loop in printList

C No error; output: 5 -> 10 -> 15 -> (head)

D SyntaxError: Unexpected token '!'

💡 Hint

Check how the loop in printList stops.

The do-while loop stops when current returns to head, so no infinite loop occurs.

❓ Predict Output

advanced

Output after reversing a singly linked list

What is the printed state of the singly linked list after reversing it? Initial list: 1 -> 2 -> 3 -> null

DSA Typescript

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

class SinglyLinkedList {
  head: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  reverse() {
    let prev: Node | null = null;
    let current = this.head;
    while (current) {
      const nextTemp = current.next;
      current.next = prev;
      prev = current;
      current = nextTemp;
    }
    this.head = prev;
  }

  printList() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    result += 'null';
    console.log(result);
  }
}

const list = new SinglyLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.reverse();
list.printList();

A 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> null

C null

D 1 -> 3 -> 2 -> null

💡 Hint

Reversing changes the direction of next pointers.

After reversal, the list order is reversed: 3 -> 2 -> 1 -> null.

🧠 Conceptual

expert

Pointer design in a skip list node

In a skip list node structure, which pointer design best supports efficient multi-level traversal?

A Multiple 'forward' pointers in an array, each pointing to nodes at different levels ahead

B A single 'next' pointer to the immediate next node only

C A 'prev' pointer only to the previous node at the same level

D A 'child' pointer to a nested linked list node

💡 Hint

Skip lists use multiple levels to skip nodes efficiently.

Skip list nodes have multiple forward pointers to nodes at different levels, enabling fast traversal.

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