Creating a Singly Linked List from Scratch in DSA Typescript - Debugging & Practice

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this linked list after insertions?

Consider a singly linked list where we insert nodes with values 10, 20, and 30 at the end. What will be the printed state of the list?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

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

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

const list = new LinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.print();

A 30 -> 20 -> 10 -> null

B 10 -> 20 -> 30 -> null

C 10 -> 30 -> 20 -> null

D null

💡 Hint

Remember, inserting at the end means the first inserted node stays at the head.

Nodes are inserted at the end, so the order is 10, then 20, then 30, followed by null.

❓ Predict Output

intermediate

What is the output after deleting the head node?

Given a singly linked list with nodes 5 -> 15 -> 25 -> null, if we delete the head node, what will be the new printed state?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

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

  deleteHead() {
    if (this.head) {
      this.head = this.head.next;
    }
  }

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

const list = new LinkedList();
list.insert(5);
list.insert(15);
list.insert(25);
list.deleteHead();
list.print();

A 15 -> 25 -> null

B 5 -> 15 -> 25 -> null

C 25 -> 15 -> null

D null

💡 Hint

Deleting the head means the second node becomes the new head.

After deleting the head (5), the list starts from 15 and continues to 25.

🔧 Debug

advanced

Why does this linked list insertion code cause an infinite loop?

Examine the following code for inserting a node at the end of a singly linked list. Why does it cause an infinite loop?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = current; // Problem here
  }
}

A The newNode is never linked to the list, so the list remains unchanged.

B The while loop condition should be 'current.next === null' to stop correctly.

C The line 'current.next = current;' creates a cycle by pointing a node to itself, causing infinite traversal.

D The head is not updated after insertion, causing the list to lose nodes.

💡 Hint

Check what 'current.next = current;' does to the list structure.

Assigning 'current.next = current;' makes the node point to itself, creating a loop that never ends.

🧠 Conceptual

advanced

What is the time complexity of inserting a node at the end of a singly linked list without a tail pointer?

If a singly linked list does not maintain a tail pointer, what is the time complexity of inserting a new node at the end?

A O(1) because insertion is always constant time

B O(n^2) because each insertion requires traversing the list multiple times

C O(log n) because of binary search on the list

D O(n) because we must traverse the entire list to find the end

💡 Hint

Think about how you find the last node without a tail pointer.

Without a tail pointer, you must start at the head and move through all nodes to reach the end, which takes linear time.

🚀 Application

expert

After these operations, what is the final linked list?

Start with an empty singly linked list. Perform these operations in order: 1. Insert 1 at the end 2. Insert 2 at the end 3. Insert 3 at the end 4. Delete the head node 5. Insert 4 at the end 6. Delete the head node What is the printed state of the list now?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

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

  deleteHead() {
    if (this.head) {
      this.head = this.head.next;
    }
  }

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

const list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.deleteHead();
list.insert(4);
list.deleteHead();
list.print();

A 3 -> 4 -> null

B 2 -> 3 -> 4 -> null

C 1 -> 2 -> 3 -> 4 -> null

D 4 -> null

💡 Hint

Track the head node carefully after each deletion.

After first deletion, head moves from 1 to 2; after second deletion, head moves from 2 to 3; list ends with nodes 3 and 4.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements in a sequence where each element points to the next one

B. To store elements with keys and values for fast lookup

C. To store elements in a sorted array for quick access

D. To store elements in a tree-like hierarchy

Solution

1. Step 1: Understand the structure of a singly linked list

   A singly linked list stores elements in nodes where each node points to the next node in the sequence.

2. Step 2: Compare with other data structures

   Unlike key-value stores or trees, singly linked lists maintain a simple linear chain of elements.

3. Final Answer:

   To store elements in a sequence where each element points to the next one -> Option A

4. Quick Check:

   Singly Linked List = sequence with next pointers [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing linked lists with arrays
• Thinking linked lists store key-value pairs
• Assuming linked lists are hierarchical like trees

2. Which of the following is the correct TypeScript syntax to define a node class for a singly linked list?

easy

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

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

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

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check the type of the next pointer

   The next pointer should be either another Node or null if it is the last node.

2. Step 2: Verify constructor initialization

   The constructor sets the value and initializes next to null, which is correct for a new node.

3. Final Answer:

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

4. Quick Check:

   next can be Node or null = class Node { value: number; next: Node | null; constructor(value: number) { this.value = value; this.next = null; } } [OK]

Hint: Use union type for next: Node | null [OK]

Common Mistakes:

• Forgetting to allow next to be null
• Setting next to undefined instead of null
• Using any type for next which loses type safety

3. What will be the output after running this TypeScript code that creates a singly linked list with values 10, 20, 30 and prints it?

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

class LinkedList {
  head: Node | null = null;

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

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

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.print();

medium

A. 30 -> 20 -> 10 -> null

B. null

C. 10 -> 20 -> null

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Append nodes in order

   Nodes with values 10, 20, and 30 are appended in that order, so the list is 10 -> 20 -> 30.

2. Step 2: Print the list

   The print method traverses from head to end, concatenating values with ' -> ' and ending with 'null'.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Appending preserves order = 10 -> 20 -> 30 -> null [OK]

Hint: Append adds at end; print shows sequence [OK]

Common Mistakes:

• Assuming append adds at head instead of tail
• Forgetting to add 'null' at the end
• Printing values in reverse order

4. Identify the error in this TypeScript code snippet that tries to append a node to a singly linked list:

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

class LinkedList {
  head: Node | null = null;

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

const list = new LinkedList();
list.append(5);
list.append(10);
console.log(list.head.next.value);

medium

A. Error: head is undefined

B. Error: Cannot read property 'value' of null

C. No error; output will be 10

D. Error: next property is missing in Node

Solution

1. Step 1: Check append logic

   The append method correctly adds the first node as head and subsequent nodes at the end.

2. Step 2: Verify output of console.log

   After appending 5 and 10, head.next points to the node with value 10, so accessing value is valid.

3. Final Answer:

   No error; output will be 10 -> Option C

4. Quick Check:

   Proper append and access = 10 [OK]

Hint: Check if head and next are properly assigned before access [OK]

Common Mistakes:

• Forgetting to return after setting head in append
• Accessing next.value when next is null
• Not initializing next to null in Node

5. You want to create a method reverse() in your singly linked list class that reverses the list in place. Which approach correctly reverses the links between nodes?

hard

A. Create a new list and append nodes from the original list in reverse order

B. Iterate through the list, for each node set its next to the previous node, updating previous and current pointers

C. Swap the values of the first and last nodes repeatedly until the middle is reached

D. Remove all nodes and re-insert them at the head one by one

Solution

1. Step 1: Understand in-place reversal

   Reversing links means changing each node's next pointer to point to the previous node, not creating new nodes.

2. Step 2: Identify correct method

   Iterating with previous and current pointers and updating next links reverses the list efficiently in place.

3. Final Answer:

   Iterate through the list, for each node set its next to the previous node, updating previous and current pointers -> Option B

4. Quick Check:

   In-place reversal = update next pointers backward [OK]

Hint: Reverse by redirecting next pointers, not swapping values [OK]

Common Mistakes:

• Swapping node values instead of links
• Creating a new list instead of reversing in place
• Removing and re-adding nodes unnecessarily